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