MPLS網絡中的QoS路由粒度研究

摘 要:研究了基于約束的路由決策粒度對MPLS網絡中QoS路由可靠性和阻塞性能的影響。為實現成本效益的可測量性，這里在現有粒度方案的基礎上，提出了使用混合粒度方案:每對/流粒度方案和每對/類粒度方案。有每對/流粒度的每對流方案增加了P緩存和O緩存作為路由緩沖，完成了低阻塞率。有每對/類粒度的每對類方案將流匯聚到幾條路由路徑，從而允許數據包在有限的緩存規模內被標簽轉發。仿真結果表明，混合粒度方案減少了路由緩存規模，適合于MPLS網絡。關鍵詞:MPLS; QoS; 粒度方案; 路由緩存

中圖分類號:TN915-34文獻標識碼:A

文章編號:1004-373X(2010)18-0079-04

Study of QoS Routing Granularity in MPLS Network

PENG Ying1， WEN Ping-geng1， JI Fei2

(1.Yueyang Vocational Technical College， Yueyang 414000， China;2.Yueyang Civil Affairs Bureau， Yueyang 414000， China)

Abstract: The impact of constraint-based routing decision granularity on the scalability and blocking performance of QoS routing in MPLS network is studied. To achieve scalability of cost-effective， this study proposes using hybrid granularity schemes:the per-pair/flow scheme and the per-pair/class scheme. The per-pair flow scheme with per-pair/flow granularity adds a P-cache (per-pair) and an O-cache (per-flow) as the routing cache， and performs low blocking probability. The per-pair class scheme with per-pair/class granularity groups the flows into several routing paths， thus allowing packets to be label-forwarded with a bounded cache size. This scheme reduces the routing cache size and is suitable for MPLS networks.Keywords: MPLS; QoS; granularity scheme; routing cache

0 引 言

隨著Internet的快速發展，網絡擁塞問題變得越來越嚴重。網絡資源不足或不平均的業務分配都可能引起網絡擁塞。目前使用的動態路由協議RIP和OSPF總是選擇最短路徑來轉發數據包，會引起不平均的業務分配。要解決這個問題，就需要QoS路由技術和流量工程(traffic engineering，TE)。

QoS路由是在一定的可用網絡資源下求解滿足單個流QoS要求(如帶寬、時延、時延抖動等)的路由問題。而TE路由具有更加廣泛的目標，它不僅要從個體上考慮即滿足特定流的QoS要求，還要從全網的角度上考慮即優化網絡性能，均衡負載分布，使網絡處于良好的運行狀態。關于TE路由問題，正引起人們的關注，目前已經提出了一些算法，如最寬最短路徑算法(widest shortest path，WSP)[1]、最小干涉路由算法(minimum interference routing algorithm，MIRA)、基于輪廓的路由算法(profile based routing，PBR)等。這些算法都是以均衡負載分布和減小請求阻塞率為目標，在具體選路過程中又轉化成不同的限制條件。

MPLS作為一種先進的轉發機制為TE的實施提供了便利，很多流量工程都可以由MPLS有效地完成。MPLS將標簽交換轉發范例與網絡層路由結合起來[2]，在MPLS網絡的入口處賦予數據包一個固定長度的標記，這樣做的依據是轉發同等類(forwarding equivalence classes，FEC)的概念。在MPLS域內部，使用標記作轉發決定，通常不需要求助于原來數據包的信頭。在這里，標簽可以用來表現不同粒度的路由，范圍從每目標網絡這樣的粗粒度到每單個流這樣的細粒度。粗粒度，如每目的地粒度，存儲要求低、上層計算要求低，但僅適用于盡力而為的流量。細粒度，如每流粒度，提供了低阻塞率，但需要大量的狀態信息和高計算成本[3]。

為了在不影響QoS需求的情況下減少阻塞可能性，提出了混合粒度路由方案。

1 混合粒度方案

(1) 已有的最短路徑算法基礎

假定用基于鏈路狀態和直接路由的體系結構。鏈路狀態QoS路由協議用洪泛來交換鏈路狀態信息，讓所有的路由器能建立相同的鏈路狀態數據庫(LSDB)。給定完整的拓撲信息和資源的可用狀態，每個有QoS能力的路由器找到代價最小的路徑，同時滿足流的資源需求。

混合粒度方案以兩個基于命令的最短路徑計算探索法[4]作為基礎。

① 最寬最短路徑探索法:QoS對開放式最短路徑優先(QOSPF)的擴展使用最寬最短路徑(WSP)選擇標準來選擇最小跳數(最短)路徑。如果有幾條這樣的路徑，選擇有最大帶寬(最寬)的那條。這個算法迭代地識別從它本身s到任何其他節點d的最優(最寬)路徑。然后，WSP選擇到節點d的所有可能的最短路徑中的最寬σ作為有最小跳數的路由路徑。

② 約束的最短路徑探索法:顯示另一種探索法即約束的最短路徑(CSP)。使用“有充足帶寬的最小延遲”作為選擇標準來為流F找到最短路徑。

(2) 有每對/流粒度的啟發式方案

這里使用的路由在源路由中無環路，信號程序阻止數據包攜帶復雜的路由信息。在MPLS中，邊緣設備根據應用來辨別流，并依據網絡規則給數據包分類。用標簽集來區分目的地址、服務類、轉發路徑等。信號階段，如果有流請求，路徑查詢可以進行路徑計算，也可以從緩存中提取路徑。當查詢成功，源節點開始一跳一跳地發信號來建立轉發狀態，目的節點在路徑中沿每個鏈路返回并進行帶寬預定。從緩存中提取的路徑可能會誤導，也就是說，盡管存在有豐富資源的路徑，可能沿此路徑也找不到足夠的資源。這原因在于，同一源-目的地(S-D)對之間的所有流被緩存到同一路徑，而這路徑只是為第一個流計算的，可能不滿足后來流的帶寬需求。特別是當路徑鏈路成為瓶頸的時候，阻塞率迅速增加[5]。另一方面，就算這樣的誤導不發生在每流粒度的路由，由于細粒度的流狀態和路由緩存很大也導致可測量性很低。此外，細粒度路徑計算量大，在真實網絡中很難實現。因此，可執行路徑預運算，異步計算到目的地的可行路徑[6]。

在這里，將路由緩存在功能上分為三個部分，每對緩存(P緩存)，溢出的每流緩存(O緩存)，和每目的地緩存(D緩存)。

算法1:每對流粒度路由搜索

Per_Pair_Flow(F， s， d， b， D)

/*這里，流F從s到d，有帶寬需求b和延遲需求D，σ為路徑*/

{

如果在P緩存中查找失敗:

σ←尋找最小代價路徑(s， d， b， D)

if (找到路徑σ)

路徑存入P緩存， 標記流F并路由F通過路徑σ

else\"路徑未找到\"

如果在P緩存中查找成功:

if(σ的帶寬≥ b且σ的延遲≤D)

標記流F并路由F 通過路徑 s

else/* 溢出*/

{

σ←尋找最小代價路徑(s， d， b， D)

if (找到σ)

路徑存入O緩存， 標記流F并路由F 通過路徑σ

else\"路徑未找到\"

}

}

算法1顯示了每對流粒度方案。多約束路徑查詢在入口LSR執行，為了得到路由信息，查找P緩存。如果查找失敗，意味著沒有存儲相應的路徑。這種情況下，每對流粒度調用尋找最小代價路由函數找到一條QoS路徑σ。該路徑被存儲在P緩存中，流請求F直接通過σ。但如果找不到路徑σ，請求被阻塞[7]。如果在P緩存查找成功，為了確保流的QoS，必須依照最近鏈路狀態做資源可用性檢測。檢測成功，信號信息F依照P緩存路徑發送。如果檢測失敗，調用函數尋找最小代價路徑，在LSDB中的信息和剩余帶寬數據庫(RBDB)的基礎上，尋找路徑，找到的路徑σ被存儲在O緩存中，F的信號通過σ發送。如果找不到路徑σ，流被阻塞。

算法1中尋找最小代價路徑用WSP或CSP，按需求找到一條QoS路徑。其中鏈路代價函數可以依據網絡管理員的需要定義。

(3)有每對/類粒度的啟發式方案

在MPLS中，這個方案用路由標記作為標簽的一部分。當流請求達到邊緣路由器時，它被轉發到當前路由狀態接近最好的路徑，其中，最好路徑為代價最小的可行路徑。S-D對之間的流被路由到幾條不同的路徑，在源和邊緣路由器上相應地標記。相同路由路徑的流可能需要不同的QoS。MPLS域中的核心路由器使用標簽來決定數據包被轉發到哪一個出口，并決定服務的類。

算法2:每對類粒度路由搜索

Per_Pair_Class(F， s， d， b， D)

/*這里，流F從s到d，有帶寬需求b和延遲需求D，∏(s， d)為緩存入口設置的從s到d的路由路徑，π為由緩存中提取的路徑，σ為由計算得到的可行路徑*/

{

初始化 路徑代價 ←∞

提取路徑 π ∈∏(s， d)要求π的代價是最小的且滿足約束{π的帶寬 ≥ b，π的延遲 ≤D， … }

case(沒找到路徑 π ):

尋找最小代價路徑(s， d， b， D)

if(沒找到路徑σ)then\"路徑未找到\"

將(插入或替換∏(s， d)，

標記流F并路由F通過σ

case(找到路徑 π):

if(π的利用率較輕) then

標記流F并路由F 通過π

endif

σ←尋找最小代價路徑(s， d， b， D)

if(沒找到路徑σ)then\"路徑未找到\"

if(σ的代價<π的代價)then/*σ更好*/

將σ插入或替換∏(s， d)，

標記流F并路由F通過路徑s

else /* π 更好*/

標記流F并路由F 通過路徑π

endif

}

算法2顯示，在流請求F下，每對類粒度算法首先試圖從路由緩沖中提取最小代價可行路徑π。如果提取失敗，則試圖計算最小代價可行路徑σ。如果找到σ，每對類粒度算法分配一個新的標記給σ， 將新標記插入路由緩存，然后將流請求F標簽/路由，直接通過σ。而如果找到π，且路徑僅被很少利用，每對類粒度算法標記流F并將它路由到路徑π。否則，流被阻塞。如果路徑的利用率σ(π)超過了預先制定的界限，每對類粒度算法將F路由到緩存中已有的一個π，或路由F通過一條新計算的路徑σ，任何一個都是代價最小。因此，流量流能被聚集到相同的轉發類(FEC)并在邊緣路由器上相應地標上標簽。相同FEC的流可能要求不同的服務類。從而，S-D對之間的流可能被路由到最多m條不同的路徑。其中m是路由類的最大值。在每對類粒度算法中，尋找最小代價路徑函數用CSP或WSP計算最小代價路徑。

2 算法評估

為在不影響每流QoS需求的情況下減少阻塞的可能性，從粒度方面提出了兩個路由方案。每對流方案增加了每對緩存(P緩存)和每流溢出緩存(O緩存)作為路由緩存。如果P緩存不能滿足帶寬需求，則該路徑上的流被分別路由，它們的路由決定溢出到O緩存。每對類方案將流聚集到一些轉發類。這里包在邊緣路由被打上標簽，快速轉發到核心網。這個方案減少了路由緩存規模，適合于MPLS網絡。

通過限制路由標簽的數目，路由算法可將每個S-D對之間的流沿有限的路徑路由，通過給相同流的數據包打上相同的標簽來強制執行。相對于每流粒度，路由器的轉發程序僅檢查標簽路由緩存的規模限制在O(n2m)。其中n是網絡節點的數目;m為標簽數。如果基于約束的路由分布在邊緣節點上，每個節點緩存到其他n-1個目的地的m條路徑，路由緩存的規模限制減小到O(nm)。

2.1 網絡和流量模型

仿真在Waxman模型的基礎上，有100節點的隨機圖1上運行。模型中n個節點在網格上隨機分布。在節點對u，γ之間引入邊緣，圖中節點的平均度在范圍[3.5，5]。假定每條鏈路有155 Mb/s的STM-1或OC-3。

假定有兩種類型的QoS流量:GS1平均速度為3 Mb/s，而GS2平均速度為1.5 Mb/s。流的到達在每節點上獨立，遵循Poisson模型。流的持續時間服從平均值為μ的指數分布。源路由器的相鄰鏈路的鏈路狀態立即更新，而其他鏈路周期性地接收鏈路狀態公告(LSA)。

2.2 仿真結果

仿真主要檢查在中等流量負載下(如， ρ= 0.7)流的行為，這里大部分阻塞率都不會超過20%。此外，95%的信心間隔在這里報道的所有統計的仿真平均的5%內。

圖1 阻塞率隨鏈路狀態更新周期變化比較

正如所料，大的更新周期增大了流的阻塞率。然而，當更新周期超過一個臨界值時，阻塞并不是越來越高。曲線的上升在流平均持續時間較長的情況下比流平均持續時間較短的情況下要慢。這種現象暗示，為了得到更正確的網絡狀態和更好的QoS路由性能，更新周期不應超過流的平均持續時間 。

結果還顯示，每對粒度路由比其他粒度的阻塞率高。純每對粒度的網絡中，流量往往形成瓶頸，比其他網絡更難平衡。相反，在每流粒度和每對流粒度網絡中，流量在大型網絡里更有機會得到選擇路徑。直觀地看，有最好粒度的每流粒度方案能得到最低的阻塞率。但在實驗中，這并不總是正確的。事實上，有CSP的每流粒度方案有最強的路徑計算功能;它能在重負載下找到可行路由，只是路徑更長。長路徑的流比短路徑的流利用更多的網絡資源。最后，網絡資源耗盡;新到來的流只有在其他流結束后才被接納。這就是每流粒度方案與提出的每對/流粒度和每對/類粒度方案類似或在某些方面更差的原因。

另外，由于有大的更新周期，鏈路狀態信息減小了每流粒度方案的路徑計算效果。可能將不可行路徑誤認為可行(樂觀的)，或將可行路徑誤認為不可行(悲觀的)。因而，在前一情形下會有更多的信號阻塞，在后者中有更多路由阻塞;兩者都是對每流路由的性能的否定。

顯然，將CSP和WSP作統計上的比較，在這個實驗中WSP比CSP表現更好。WSP用寬度優先搜索找到多個最短路徑，選出帶寬最寬的一條，達到某種程度上的負載均衡。但另一方面，流量更加集中在CSP計算網絡。

2.3 緩存規模

圖2顯示不管流量負載，每流，每對和每對類方案的緩存幾乎保持不變。另一方面，每對/流的緩存隨著流量負載的增加而增加。

圖2 每流的平均緩存數隨負載變化比較

每對的緩存規模被限制為(n-1)2 復雜度O(n2)。其中n為節點數。每對/類緩存被限制為(n-1)2m，復雜度為O(n2m)。其中m為類的數目。

在每流方案中，緩存規模隨著流數目的增長而動態增長。每對/流和每對類方案使用混合粒度，這兩個都很顯著地將緩存規模減小到約10%(輕負載)和20%~40%(重負載)，且阻塞率沒有增加。

3 結 語

本文研究了在MPLS網絡中粒度對基于約束的路由的影響，提出混合粒度方案來完成成本效益可測量性。有每對/流粒度的每對流方案增加了P緩存和O緩存作為路由緩沖，完成了低阻塞率。有每對/類粒度的每對類方案將流匯聚到幾條路由路徑，從而允許數據包在有限的緩存規模內被標簽轉發。

仿真結果顯示，每對粒度緩存路由阻塞率最高，因為粗粒度限制了網絡狀態的精確性。每對/流粒度加強了路徑選擇能力。而每對/類粒度在有限的路由緩存下有小的阻塞率。因此，這種方案適合在MPLS網絡中，基于約束的路由。

參考文獻

[1]張連俊，李春華.基于MPLS的IP-QoS機制研究[J].計算機工程與設計，2006，27(20):3783-3785.

[2]王必榮，孟昭鵬，范明君，等.MPLS流量工程提升IP網絡QoS性能的研究[J].電子與信息學報，2006，42(2):948-953.

[3]王勇智，劉利強.下一代因特網QoS路由機制的研究[J].計算機技術與發展，2006，16(4):105-118.

[4]林娜，宋利雪.一種改進的移動節點快速切換算法研究與仿真[J].小型微型計算機系統，2009，30(11):73-76.

[5]李彬，陳向東.基于MPLS流量工程的重路由算法研究[J].計算機工程與應用，2006，42(31):153-156.

[6]張連俊，王善斌. 基于MPLS的多類路由選擇機制研究[J]. 計算機工程與設計，2007，28(17):4143-4144.

[7]LEE Y， SEOL Y F， WANG Z. A constrained multipath traffic engineering scheme for MPLS Networks[C]//ICC′02. New York: IEEE， 2002: 2431 - 2436.

[8]蔣國明，魏仰蘇，孟兆航.MPLS的基于最小干涉的負載均衡算法研究[J].計算機工程與設計，2007，28(2):371-372.

[9]KUROSE J F， ROSS K W. Computer networking: a top-down approach featuring the imemet[M].北京:人民郵電出版社，2004.

[10]陳鳳，宋玲，馬強. 基于MPLS網絡的選播QoS路由算法[J].計算機工程，2008，24(2):274-278.