一种基于MPLS流量工程的动态路由算法
2009-06-22
作者：王 红，李丽丹，张丽平
摘 要：MPLS流量工程的问题最终可以归结为数据流传输的路径确定问题，即显式路径的确立问题。通过对XUE算法的分析，提出了一种新的基于链路和路径的动态路由算法—LPR。依据网络链路平均利用率的取值范围对网络进行裁剪，在选路由时优先选择轻度占用的链路，避开重度占用的链路；从路径的角度出发，计算每条路径中的各链路带宽利用率相对于网络中链路带宽利用率均值的方差。用C++语言完成了该算法的实现，同时验证了该算法较SPF算法及XUE算法的有效性。
关键词：MPLS流量工程；动态路由；链路路径；SPF；XUE
1 XUE算法
XUE[1]算法即基于带宽和跳数的流量工程动态路由选择算法，是一种最为典型的基于约束路由选择算法（CSPF）[2]。XUE算法采用利用率阀值激活方式，与现有路由算法兼容，以带宽和跳数作为约束，目标函数是使跳数最少。适时激活该算法，根据路由结果建立一条或多条显式路径，将部分流量转移到这些路径上，其时间复杂度与Dijkstra算法相当，是一种有效可行的动态路由算法。但是此算法仅考虑了网络带宽的当前利用状况，虽然在一定程度上避免了链路瓶颈的发生[3]，却忽略了网络资源的均衡分布[4]。由此本文针对XUE算法未考虑的问题给出解决方案，提出了一种新的动态路由算法-LPR。
2 LPR算法实现
2.1 算法描述
该算法从链路和路径两方面考虑。链路的带宽利用率反映链路的负载情况，所有链路的负载状况都可以反映整个网络的流量均衡程度[5]。显然，当网络中所有链路的负载都较轻时，网络不会出现拥塞，所有用户的QoS都能得到保证。在本算法中定义两个常量：j，k （0
2.2 数学定义
在网络算法研究中，实际的MPLS[6]网络域运用图论抽象为物理拓扑：一个由V个节点E条边的无向连通加权图G（V，E）表示网络（|V|=n，|E|=m），V表示网络中n个路由器节点的集合，E表示路由器之间m条链路的集合，每条边的链路带宽容量C表示能够通过该条边的业务量的最大值。在本算法中，首先给出了如下几个数学定义：
假设网络的链路数为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表示源节点，d表示目的节点，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为算法流程图。
算法的关键步骤是入口与出口节点之间的可选路径计算，网络中计算最短路径的复杂度是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算法的有效性及其优越性，针对图2所示的网络拓扑进行了两组实验仿真。假设现行网络正在运行，每个节点了解整个网络拓扑和链路状态信息，网络中所有链路均为双向对称链路，链路上的数字表示剩余带宽/最大可预留带宽(×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算法更加有效：
（1）LPR算法是XUE算法的补充，对于缓解由于流量对资源竞争引起的包丢失具有显著的效果；
（2）LPR算法更加有效地降低了资源利用率，避免瓶颈链路的产生；
（3）LPR算法能更好地调节流量在整个网络上的分布，使网络资源得到均衡分布；
（4）LPR算法大大提高了连接请求的通过率，增加了网络的吞吐量。
参考文献：
[1] 薛希俊，孙雨耕，刘振肖．基于带宽和跳数的流量工程动态路由选择算法研究[J]．电子学报，2002，30(2):274-278．
[2] 贾艳萍，孟相如．基于MPLS流量工程的多路径约束负载均衡方法[J]．计算机应用，2008，27(3)：522-524．
[3] 朱明英，叶梧． 基于最小干扰机制的MPLS流量工程动态路由算法[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．