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