MPLS網絡中QoS路徑安排研究

孫尚 王萬龍

（中國人民解放軍66061 部隊 北京市 100144）

1 引言

近幾年，互聯網(Internet)的迅速發展及使用人數的遞增，帶寬不足將是往后互聯網所面臨到的一個重要問題，帶寬的競爭和沖突嚴重危害了整體網絡的傳輸性能。由于標簽交換技術的發展，許多優點因素證明其將發展為未來網絡技術的主流，尤其多重協議標簽交換技術(MultiprotocolLabel Switch, 簡稱MPLS)，它整合了目前各種交換式路由器技術的優點，其結合了非同步傳送模式(Asynchronous Transfer Mode, 簡稱ATM)的快速化、簡單傳輸的優點，以及傳統IP 的普遍性(ubiquity)、延展性(scalability)及彈性度(flexibility)優點。本文重點研究MPLS 網絡標簽交換技術中的路由路徑安排，并可以使得有足夠的帶寬分給不同類型服務，從而達到服務所需。

2 算法設計

2.1 LSP路由安排算法

本節將介紹如何安排有服務質量需求的數據的路由選擇方式，下面列舉兩項：Best-fit shortest path algorithm (BSP)和Worstshortest path algorithm (WSP)。

2.1.1 Best-fit shortest path algorithm (BSP)

Best-fit shortest path algorithm 是 由Dijkstra’s shortest path algorithm 演變而來，將最短路徑距離權重考慮成連接帶寬權重，來計算安排某一來源端(source)到目的端(destination)之間標簽交換路徑，LSP(s, d)，而此LSP(s, d)路徑所選擇的路徑，是為欲配置的LSP 路徑所連接帶寬剩余總和為最小者。

（1）相關符號定義與注解：

G(N, L, C)：圖形G 具有N 個節點及L 個連接

N：網絡節點數的集合

L：任兩節點間連接(Link)的集合

C：網絡所有連接帶寬權重的集合

s：欲安排LSP 起點(來源端)

t：欲安排LSP 終點(目的端)

b：欲安排LSP 所需帶寬權重

S：N 集合中的部分集合

Du：s 點到u 點的帶寬權重

duv：u 點到v 點之間連接的帶寬權重

duv*：u 點到v 點之間連接減去b 后的帶寬權重

G’：G(N, L)所有連接減去b 所行成的網絡圖形

圖1：網絡帶寬安排范例

圖2：彈性帶寬配置

（2）BSP 實行步驟簡述：

Step 1：網絡所有連接帶寬減去要配置給此LSP (s, d)的帶寬b；即G’(N, L, C-b)。

Step 2：在G’(N, L, C-b)中，利用Dijkstra’s algorithm 計算安排一最短路徑給 LSP(s,d)，此路徑所選擇經過的所有連接帶寬剩余總和為最小者；

Step3：更新網絡狀態，將原G 減去LSP (s, d)所分配的帶寬，即得網絡所剩余帶寬；然后回Step 1，安排下一條LSP。

2.1.2 Worst-shortest path algorithm (WSP)

Worst-shortest path algorithm 所計算路由方式和Best-fit shortest pathalgorithm 相似，兩者最大差異在于前者所選LSP 路徑其各Link所剩余資源為較多者，后者反之。

（1）相關符號定義與注解：

Du

hop：s 點到u 點的帶寬權重

hop：為s 點到u 點所經的hop 數

duv：u 點到v 點之間連接的帶寬權重

duv#：u 點到v 點之間連接減去b 后的帶寬權重

（2）WSP 實行步驟簡述：

Step1：網絡所有Links 帶寬減去要配置給(s, d)的帶寬b；即G’(N, L, C-b)。

Step2：在G’(N, L, C-b)中,計算安排一經過hop 數為最少的路徑給LSP(s, d)，此路徑所選擇經過的所有連接帶寬總和，在其他相同hop 數的路徑當中，其帶寬剩余總和值為最大者。

Step3：更新網絡狀態，將原G 減去LSP (s, d)所分配的帶寬，即得網絡所剩余帶寬；然后回Step 1，安排下一條LSP。

2.1.3 BSP 與WSP 的研究

BSP 算法所選擇LSP 是所有連接剩余帶寬和為最小者，此意思是說由利用BSP 算法所選擇的路徑將會是最接近其帶寬需求的LSP。主要采用此方式的原因是考慮保留較大的剩余帶寬給未來需求帶寬較大的LSP 使用。例如圖1 的網絡拓撲有三條LSP(S1, D1, 4Mb)、LSP(S2, D2, 3Mb) 以及LSP(S3, D3, 2Mb) 需建 立。假如三條LSP 建立需求順序為LSP(S3, D3,2Mb)-＞LSP(S2, D2, 3Mb)-＞LSP(S1, D1, 4Mb)，以最短路徑選擇的話，S3 到D3 將先選R3-R4-R9-R11、S2 到D2 將選R2-R4-R6-R9-R10、S1 到D1 將被拒絕。

但假如采用BSP 方式選路S3 到D3 將選擇更其帶寬需求最接近 的R3-R4-R5-R7-R8-R9-R11(2Mb)、S2 到D2 選R2-R4-R6-R9-R10(3Mb)、S1 到D1 選R1-R4-R9-R12(4Mb)。在這種情形下，采用BSP 算法選擇路徑可達較佳狀況。

但是BSP 缺點是由于是選擇最接近其帶寬需求的路徑，所以沒有考慮到連接資源消耗的問題，如圖1 中LSP(S3, D3, 2Mb)所選的路徑將經過六個連接，然而其需求帶寬應用為2Mb，便使用了整體網絡12Mb 的帶寬。

WSP 算法選路原則是計算安排經過hop 數為最少且所經連接帶寬剩余總和值為最大的路徑。WSP 選擇路徑的考慮因素是為了企圖達到網絡負載平衡，也就是說，WSP 選擇路徑方式主要希望將網絡數據流盡量分布于網絡之中，其采用“經過hop 數為最少”的原因是考慮連接資源消耗的問題。但是其缺點為可能造成往后較大帶寬容量需求的LSP 無法配置情形發生。同樣以圖1 為例，三條LSP 建立需求順序為LSP(S3, D3, 2Mb)-＞LSP(S2, D2, 3Mb)-＞ LSP(S1, D1,4Mb)，采用WSP 方式選路卻可能發生跟最短路由方式相同的情形，S3 到D3 將先選R3-R4-R9-R11、S2 到D2 將選R2-R4-R6-R9-R10、而S1 到D1 將被拒絕。

由于BSP 和WSP 算法，各有其所考慮因素及其缺點，故本論文將其分別應用于不同服務數據流當中，測試兩者使用在LSP 路由安排機制上情形，并將在往后章節作一研究其模擬結果。

2.2 伸縮限制帶寬的方法

為了讓網絡中連接帶寬得以有效率地分配，本節提出伸縮限制帶寬(Elastic Constrained Bandwidth，ECB)的配置方式。此配置方式的主要目的是為避免或緩解高優先權路徑，因過于集中某些連接，而造成這些連接無法彈性利用，及促使其他低優先權重據的需求，可能因此無法傳送而需等待。在伸縮限制帶寬的配置方式中，本研究中訂定一彈性參數Ef來作為調節高優先權及低優先權路徑在使用連接時的使用率。我們將Ef的大小設置為介于0～1 之間。當網絡高優先權重據在作路徑安排動作時，網絡連接帶寬將根據彈性限制參數(Ef)而受到某程度的使用限制，致使高優先權路徑得以選擇其他連接，避免集中情形產生。對低優先權類型服務，則考慮其業務特性，讓低優先權類型數據可有彈性彌補網絡安排的LSP 的帶寬過多于實際傳送數據量使用的帶寬時，而造成的資源浪費，而大膽地將連接帶寬多分配比率給低優先權類型使用，以尋求改善。如采用伸縮限制帶寬方式來分配路徑，假設Ef值為0.25，則表示在高優先權重據使用連接帶寬時，將保留總連接帶寬的25%，作彈性調整。而低優先權重據使用連接帶寬時，將有以多于連接帶寬25%的帶寬，來作其彈性調整。例如圖2 所示，假設(S1,D1)、(S2, D2)之間，各有兩不同服務類型數據(GS 及CLS)需要傳送，傳送順序為高優先權重據(GS)優先，GS 類型所需帶寬為3Mb、CLS 類型為4Mb。假設所欲配置的LSP(S1, D1 ,3Mb ,GS)經由R1-R3-R4-R6-R7路徑傳送時，根據伸縮限制帶寬方式選路的話，R3-R4-R6 路段將只剩余1.5Mb(6×0.25-3=1.5)的帶寬來提供GS 類型數據流。所以另一LSP(S2, D2, 3Mb, GS)則將選擇另一路徑R2-R3-R5-R6-R8。如此依據伸縮限制帶寬方式選路，可避免其兩條GS 類型LSP 同時經過相同路段(R3-R4-R6)且占盡其所有資源。然而，在CLS 類型LSP 安排上，雖然連接帶寬無法達到其所需帶寬，但根據彈性參數作其連接的彈性調整，即整條連接將可分配7.5Mb (6+6×0.25=7.5)帶寬，故兩CLS 類型LSP 將也可以得到路徑分配。由此方式將兩高優先權重路徑分開，保留連接資源，對于將來使用亦可簡易調整或增大其所需帶寬，而減去作重新選路計算的動作。對于超額分配給低優先權服務的方式，則是主要考慮網絡整體資源能夠達到充分利用。

3 結語

本文考慮不同服務類型數據的優先次序，來做路徑選擇安排的比較，并得以保障高等級服務應用的實現，且加入伸縮限制帶寬的配置方式，不僅可以提供大部分高優先權服務的應用，而且對于其他低優先權服務也可以獲得實現，且同時能夠保障或達到使用者所要求服務的最低需求，換句話說，在高優先等級服務得以保障的同時，也希望較低優先等級服務能得到其所需求的最低保障帶寬。