MPLS網(wǎng)絡(luò)中QoS路徑安排研究

孫尚 王萬(wàn)龍

（中國(guó)人民解放軍66061 部隊(duì) 北京市 100144）

1 引言

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

2 算法設(shè)計(jì)

2.1 LSP路由安排算法

本節(jié)將介紹如何安排有服務(wù)質(zhì)量需求的數(shù)據(jù)的路由選擇方式，下面列舉兩項(xiàng)：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 演變而來(lái)，將最短路徑距離權(quán)重考慮成連接帶寬權(quán)重，來(lái)計(jì)算安排某一來(lái)源端(source)到目的端(destination)之間標(biāo)簽交換路徑，LSP(s, d)，而此LSP(s, d)路徑所選擇的路徑，是為欲配置的LSP 路徑所連接帶寬剩余總和為最小者。

（1）相關(guān)符號(hào)定義與注解：

G(N, L, C)：圖形G 具有N 個(gè)節(jié)點(diǎn)及L 個(gè)連接

N：網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的集合

L：任兩節(jié)點(diǎn)間連接(Link)的集合

C：網(wǎng)絡(luò)所有連接帶寬權(quán)重的集合

s：欲安排LSP 起點(diǎn)(來(lái)源端)

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

b：欲安排LSP 所需帶寬權(quán)重

S：N 集合中的部分集合

Du：s 點(diǎn)到u 點(diǎn)的帶寬權(quán)重

duv：u 點(diǎn)到v 點(diǎn)之間連接的帶寬權(quán)重

duv*：u 點(diǎn)到v 點(diǎn)之間連接減去b 后的帶寬權(quán)重

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

圖1：網(wǎng)絡(luò)帶寬安排范例

圖2：彈性帶寬配置

（2）BSP 實(shí)行步驟簡(jiǎn)述：

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

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

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

2.1.2 Worst-shortest path algorithm (WSP)

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

（1）相關(guān)符號(hào)定義與注解：

Du

hop：s 點(diǎn)到u 點(diǎn)的帶寬權(quán)重

hop：為s 點(diǎn)到u 點(diǎn)所經(jīng)的hop 數(shù)

duv：u 點(diǎn)到v 點(diǎn)之間連接的帶寬權(quán)重

duv#：u 點(diǎn)到v 點(diǎn)之間連接減去b 后的帶寬權(quán)重

（2）WSP 實(shí)行步驟簡(jiǎn)述：

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

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

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

2.1.3 BSP 與WSP 的研究

BSP 算法所選擇LSP 是所有連接剩余帶寬和為最小者，此意思是說(shuō)由利用BSP 算法所選擇的路徑將會(huì)是最接近其帶寬需求的LSP。主要采用此方式的原因是考慮保留較大的剩余帶寬給未來(lái)需求帶寬較大的LSP 使用。例如圖1 的網(wǎng)絡(luò)拓?fù)溆腥龡lLSP(S1, D1, 4Mb)、LSP(S2, D2, 3Mb) 以及LSP(S3, D3, 2Mb) 需建 立。假如三條LSP 建立需求順序?yàn)長(zhǎng)SP(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 算法選擇路徑可達(dá)較佳狀況。

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

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

由于BSP 和WSP 算法，各有其所考慮因素及其缺點(diǎn)，故本論文將其分別應(yīng)用于不同服務(wù)數(shù)據(jù)流當(dāng)中，測(cè)試兩者使用在LSP 路由安排機(jī)制上情形，并將在往后章節(jié)作一研究其模擬結(jié)果。

2.2 伸縮限制帶寬的方法

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

3 結(jié)語(yǔ)

本文考慮不同服務(wù)類型數(shù)據(jù)的優(yōu)先次序，來(lái)做路徑選擇安排的比較，并得以保障高等級(jí)服務(wù)應(yīng)用的實(shí)現(xiàn)，且加入伸縮限制帶寬的配置方式，不僅可以提供大部分高優(yōu)先權(quán)服務(wù)的應(yīng)用，而且對(duì)于其他低優(yōu)先權(quán)服務(wù)也可以獲得實(shí)現(xiàn)，且同時(shí)能夠保障或達(dá)到使用者所要求服務(wù)的最低需求，換句話說(shuō)，在高優(yōu)先等級(jí)服務(wù)得以保障的同時(shí)，也希望較低優(yōu)先等級(jí)服務(wù)能得到其所需求的最低保障帶寬。