摘 要：MPLS流量工程的問(wèn)題最終可以歸結(jié)為數(shù)據(jù)流傳輸?shù)穆窂酱_定問(wèn)題，即顯式路徑的確立問(wèn)題。通過(guò)對(duì)XUE算法的分析，提出了一種新的基于鏈路和路徑的動(dòng)態(tài)路由算法—LPR。依據(jù)網(wǎng)絡(luò)鏈路平均利用率的取值范圍對(duì)網(wǎng)絡(luò)進(jìn)行裁剪，在選路由時(shí)優(yōu)先選擇輕度占用的鏈路，避開(kāi)重度占用的鏈路；從路徑的角度出發(fā)，計(jì)算每條路徑中的各鏈路帶寬利用率相對(duì)于網(wǎng)絡(luò)中鏈路帶寬利用率均值的方差。用C++語(yǔ)言完成了該算法的實(shí)現(xiàn)，同時(shí)驗(yàn)證了該算法較SPF算法及XUE算法的有效性。
關(guān)鍵詞：MPLS流量工程；動(dòng)態(tài)路由；鏈路路徑；SPF；XUE
?
1 XUE算法
XUE[1]算法即基于帶寬和跳數(shù)的流量工程動(dòng)態(tài)路由選擇算法，是一種最為典型的基于約束路由選擇算法（CSPF）[2]。XUE算法采用利用率閥值激活方式，與現(xiàn)有路由算法兼容，以帶寬和跳數(shù)作為約束，目標(biāo)函數(shù)是使跳數(shù)最少。適時(shí)激活該算法，根據(jù)路由結(jié)果建立一條或多條顯式路徑，將部分流量轉(zhuǎn)移到這些路徑上，其時(shí)間復(fù)雜度與Dijkstra算法相當(dāng)，是一種有效可行的動(dòng)態(tài)路由算法。但是此算法僅考慮了網(wǎng)絡(luò)帶寬的當(dāng)前利用狀況，雖然在一定程度上避免了鏈路瓶頸的發(fā)生[3]，卻忽略了網(wǎng)絡(luò)資源的均衡分布[4]。由此本文針對(duì)XUE算法未考慮的問(wèn)題給出解決方案，提出了一種新的動(dòng)態(tài)路由算法-LPR。
2? LPR算法實(shí)現(xiàn)
2.1? 算法描述
該算法從鏈路和路徑兩方面考慮。鏈路的帶寬利用率反映鏈路的負(fù)載情況，所有鏈路的負(fù)載狀況都可以反映整個(gè)網(wǎng)絡(luò)的流量均衡程度[5]。顯然，當(dāng)網(wǎng)絡(luò)中所有鏈路的負(fù)載都較輕時(shí)，網(wǎng)絡(luò)不會(huì)出現(xiàn)擁塞，所有用戶(hù)的QoS都能得到保證。在本算法中定義兩個(gè)常量：j，k （0
2.2 數(shù)學(xué)定義
在網(wǎng)絡(luò)算法研究中，實(shí)際的MPLS[6]網(wǎng)絡(luò)域運(yùn)用圖論抽象為物理拓?fù)洌阂粋€(gè)由V個(gè)節(jié)點(diǎn)E條邊的無(wú)向連通加權(quán)圖G（V，E）表示網(wǎng)絡(luò)（|V|=n，|E|=m），V表示網(wǎng)絡(luò)中n個(gè)路由器節(jié)點(diǎn)的集合，E表示路由器之間m條鏈路的集合，每條邊的鏈路帶寬容量C表示能夠通過(guò)該條邊的業(yè)務(wù)量的最大值。在本算法中，首先給出了如下幾個(gè)數(shù)學(xué)定義：
假設(shè)網(wǎng)絡(luò)的鏈路數(shù)為l，在任意時(shí)刻t，通過(guò)≈測(cè)量或者其他途徑可以得出每條鏈路的剩余可用帶寬R。
??? 該算法是以最小化路徑的均衡度為目標(biāo)函數(shù)，加之約束條件進(jìn)行路徑的選擇。
2.3 構(gòu)造算法的數(shù)學(xué)模型
??? 目標(biāo)：Min（Q(paths(s,d))），paths(s,d)包含于T(s,d)
??? 約束條件為：
hops(p(s,d))≤H?????????????? p(s,d)∈paths(s,d)
bandwidth(paths(s,d))≥B?? paths(s,d)包含于T(s,d)
num(paths(s,d))≤N????? paths(s,d)包含于T(s,d)
color(p(s,d))包含于COLOR????? p(s,d)∈paths(s,d)
其中，s表示源節(jié)點(diǎn)，d表示目的節(jié)點(diǎn)，p(s,d)表示s到d的一條路徑，T(s,d)表示s到d的所有路徑的集合，paths(s,d)表示T(s,d)的一個(gè)子集。bandwidth(paths(s,d))表示路徑p(s,d)的可預(yù)留帶寬；num(paths(s,d))表示組成路徑集的路徑條數(shù)。H、B、N都是常數(shù)，分別表示路徑的最大長(zhǎng)度（即最大跳數(shù)）、待轉(zhuǎn)移流量對(duì)帶寬的要求、所求路徑的最多條數(shù)；COLOR表示允許的顏色集合，可以由網(wǎng)絡(luò)管理員設(shè)定。color(p(s,d))表示組成路徑p(s,d)的所有鏈路的顏色集合。
2.4 算法流程圖及復(fù)雜度
圖1為算法流程圖。
的平均利用率，根據(jù)平均利用率的取值范圍對(duì)鏈路進(jìn)行再次裁剪 另外，在圖2所示的網(wǎng)絡(luò)拓?fù)鋱D中進(jìn)行了另一組實(shí)驗(yàn)，考察在最短路算法SPF、XUE算法和LPR算法下的路徑分布及由此帶來(lái)的丟包率和帶寬利用率等的變化。實(shí)驗(yàn)中所使用的數(shù)據(jù)源示于表1。 在實(shí)驗(yàn)中連接請(qǐng)求逐個(gè)先后到來(lái)，這3個(gè)請(qǐng)求在3種算法中選擇的路徑情況如表2所示。 圖4是在SPF和LPR算法下鏈路6-7帶寬的利用率情況。
算法的關(guān)鍵步驟是入口與出口節(jié)點(diǎn)之間的可選路徑計(jì)算，網(wǎng)絡(luò)中計(jì)算最短路徑的復(fù)雜度是O(n3)，計(jì)算第二最短路徑的復(fù)雜度是O(n4)，計(jì)算第M最短路徑的復(fù)雜度是O(nM+2)。綜合分析算法各步驟，其最終的計(jì)算復(fù)雜度取決于算法實(shí)現(xiàn)中所確定的，需要計(jì)算的第M條最短路徑的復(fù)雜度，即O(nM+2)。
2.5 LPR算法
createDN（GG，vexnum，arcnum,names,edges）;
//圖的初始化
PrintGP(names,vexnum);//界面顯示
createUDN(G,vexnum,arcnum,names,edges);
//臨時(shí)中間圖初始化用戶(hù)輸入請(qǐng)求；
for( i=0;i
????? u1=sum1/l1;//計(jì)算滿(mǎn)足帶寬請(qǐng)求的網(wǎng)絡(luò)拓?fù)渲墟溌?/P>
n=KShortestpath(G,city1,city2);//以裁剪后的網(wǎng)絡(luò)拓?fù)??
圖為基礎(chǔ)計(jì)算出K條最短路徑//各路徑方差的計(jì)算
for(i=0;i
t=SizeOf(Paths[i]);
for(j=0;j
MemberOf(Paths[i],j,x,y);
sum=sum+(ratio[x][y]-u2)*(ratio[x][y]-u2);
}
Q[i]=sum/t;
}
CopyBNQueue(Paths[k],P);
while(!EmptyQueue(P))//輸出最終路徑
{
DeQueue(P,t);
cout<<' '<<' '<
cout<
for(j=0;j
MemberOf(Paths[k],j,x,y);
GG．a(chǎn)rcs[x][y]．lwidth=GG．a(chǎn)rcs[x][y]．lwidth-B;
GG．a(chǎn)rcs[y][x]．lwidth=GG．a(chǎn)rcs[x][y]．lwidth;
ratio[x][y]=100-GG．a(chǎn)rcs[x][y]．lwidth*100/GG．a(chǎn)rcs[x][y]．cwidth;
ratio[y][x]=ratio[x][y];
}
3?仿真實(shí)驗(yàn)
為了證明LPR算法的有效性及其優(yōu)越性，針對(duì)圖2所示的網(wǎng)絡(luò)拓?fù)溥M(jìn)行了兩組實(shí)驗(yàn)仿真。假設(shè)現(xiàn)行網(wǎng)絡(luò)正在運(yùn)行，每個(gè)節(jié)點(diǎn)了解整個(gè)網(wǎng)絡(luò)拓?fù)浜玩溌窢顟B(tài)信息，網(wǎng)絡(luò)中所有鏈路均為雙向?qū)ΨQ(chēng)鏈路，鏈路上的數(shù)字表示剩余帶寬/最大可預(yù)留帶寬(×100 kb/s)。
首先，假設(shè)連接請(qǐng)求隨機(jī)產(chǎn)生，其請(qǐng)求范圍為隨機(jī)數(shù)50 kb/s～100 kb/s，仿真過(guò)程是逐漸增加連接請(qǐng)求數(shù)，每次增加10個(gè)，仿真內(nèi)容是實(shí)驗(yàn)隨著網(wǎng)絡(luò)中接入連接數(shù)的增多，鏈路的最大帶寬利用率的變化情況。本算法的運(yùn)行結(jié)果與XUE算法的比較如圖3所示。
由圖可見(jiàn)，網(wǎng)絡(luò)中的連接數(shù)少時(shí)，兩種算法的差別不大，但是隨著連接數(shù)的增多，最大帶寬利用率都在增大，但是在本算法中增加較小。
表3是在LPR和XUE兩種算法下，鏈路的利用率狀況(為直觀只列出所選路徑中涉及的鏈路)。
由仿真實(shí)驗(yàn)可知，LPR算法較SPF和XUE算法更加有效：
（1）LPR算法是XUE算法的補(bǔ)充，對(duì)于緩解由于流量對(duì)資源競(jìng)爭(zhēng)引起的包丟失具有顯著的效果；
?。?）LPR算法更加有效地降低了資源利用率，避免瓶頸鏈路的產(chǎn)生；
?。?）LPR算法能更好地調(diào)節(jié)流量在整個(gè)網(wǎng)絡(luò)上的分布，使網(wǎng)絡(luò)資源得到均衡分布；
?。?）LPR算法大大提高了連接請(qǐng)求的通過(guò)率，增加了網(wǎng)絡(luò)的吞吐量。
參考文獻(xiàn)：
[1]?薛?？?，孫雨耕，劉振肖．基于帶寬和跳數(shù)的流量工程動(dòng)態(tài)路由選擇算法研究[J]．電子學(xué)報(bào)，2002，30(2):274-278．
[2]?賈艷萍，孟相如．基于MPLS流量工程的多路徑約束負(fù)載均衡方法[J]．計(jì)算機(jī)應(yīng)用，2008，27(3)：522-524．
[3]?朱明英，葉梧． 基于最小干擾機(jī)制的MPLS流量工程動(dòng)態(tài)路由算法[J]．科學(xué)技術(shù)與工程，2008，8(19)：5394-5398．
[4]?HUANG He， LI Wei Qin． Optimization of MPLS traffic engineering architecture[J]． Journal of Beijing University of Aeronautics and Astronautics， 2003， 29(3):221-224．?
[5]?劉郁恒，張光昭．MPLS流量工程技術(shù)的研究[J]．?dāng)?shù)據(jù)通信，2000(2): 1-4．
[6]?WANG Y F， WANG Z． Explicit routing algorithms for internet traffic engineering[A]． IEEE ICCCN’99[C]． Boston， MA． 1999:582-588．