基于网络最大流的MPLS流量工程动态路由算法

　　1 引言

　　动态路由算法是MPLS流量工程中最关键的技术之一[1，2]，建立有带宽保证的路由问题已经有大量的前期工作，其中代表性的路由算法主要有最小跳算法(min-hop aIgorithm，MHA)、最宽最短路径算法(widestshortest path，WSP)[3]、最短最宽路径算法(shortestest widest palh，SWP)[4,5]、以及最小干扰路径算法(minimuminterference routing algorithm，MIRA)[6，7]等。

　　MHA算法采用的是基于目的地最短路径路由,就是在网络源节点与目的节点之间查找一条具有最小跳数的可达路径。此算法会导致多条最短路径都选用同一条链路而发生拥塞。WSP与SWP算法基本相似,WSP算法是在多条跳数最小的侯选路径中选择一条可用带宽最多的一条路径：SWP是在多条可用带宽最大的路径中选择一条跳数最小的路径进行路由。这两种算法属于贪婪算法，并且对同一节点对产生多条最小跳或是最大带宽的几率并不是很大，因此算法的效果并不理想。比较复杂的影响力最大的算法包括最小干扰路由算法(MIRA)，主要思想是在为当前源、目的结点对选择LSP时尽量减少对未来节点对建立链接请求的影响,从而优化网络性能。但是从MIRA算法对关键链路的定义来看,此算法只定义了属于某节点对的最小割的链路为关键链路,并没有考虑非关键链路对未来建立链路请求的影响，并且算法复杂度高。

　　2 系统模型及算法描述

　　2.1 网络模型描述

　　网络路由算法研究通常借助图论描述网络模型,网络的拓扑结构以无向加权连通图G=(V,E，B)表示，V(|V|=N)表示路由节点集合：N表示节点数目，E(|E|=M)表示链路集合，M表示链路数目;B表示网络中链路容量的集合。用L表示可能产生建立LSP请求的进出路由器对的集合。需要建立LSP链接请求r(s。d，b)表示，s和d分别表示业务流的入口和出口节点。b表示需要链接的业务流(s,d)的需求带宽,R1表示链路I的剩余带宽。

　　2.2 算法描述

　　此前大多数有带宽保证的路由算法基本只考虑链路剩余带宽而没有考虑链路的带宽利用率,以至于其他条件都相同的情况下,带宽相同的两条链路同等对待,而实际上这两条链路的负载相差很大，因此建立链路之后对网络的影响截然不同。

　　定义：链路带宽利用率A1：对任意节点对(s，d)，接受请求带宽为b的链路请求之后的链路带宽利用率为：

　　链路带宽利用率反应链路当前的负载情况，也可反应建立LSP请求后的链路负载情况，A1的值越小说明建立链接对以后的LSP链接请求的影响越小，当A1 值接近为1时说明链路的负载非常重，接入新的链路请求的动态成本非常高。

　　MBGRA算法的核心思想是先计算各个链路的权重值，而后用最短路由算法查找权重最小的路径。此算法在计算链路权值时分为离线阶段和在线阶段。离线阶段计算的链路初始权值w(l)是静态的，在网络拓扑一定的条件下不发生变化，只有当网络拓扑发生变化时才需要重新计算。

　　2.2.1 离线阶段

　　对任意给定的网络拓扑结构，对任意LSP请求I(s,d,b)，首先计算(s,d)∈L的结点对之间的网络最大流为Fsd。由于网络最大流路径的选择不唯一，因此我们计算出网络最大流的所有可能组合，对任意的链路的使用无疑将改变网络最大流，因此用fsd1表示在离线状态下节点对(s,d)∈L之间的网络最大流中通过链路L的流量,我们定义此链路对(s，d)∈L之间的网络最大流的贡献量为,此值反映了链路L对将要建立的(s,d)∈L之间的链路请求的相对重要程度。计算单个链路I相对结点对(s，d)∈L的链路权值为：

　　其中，Fsd代表路由节点对(s，d)之间的网络最大流，fsd1表示路由出入节点(s，d)∈E之间的网络最大流中通过链路I的部分，n表示在路由结点对(s，d)之间的网络最大流路由数目.m表示这n种网络路由数目中通过链路I的次数。计算链路I的初始权值W(I)为：

　　2.2.2 在线阶段

　　对于给定的网络拓扑,在离线阶段已经计算出单条链路的初始权值W(I)，定义单条链路的及时权值为：

　　在我们的研究过程中发现，链路带宽利用率AL对链路权值的影响并没有预想的那样大，因此我们给Al开方来定义链路的及时权值。此定义链路权值不仅定量分析了单个链路对网络最大流的贡献量，并且考虑了单条链路的负载情况,因此MBGRA算法在选择路由路径的过程中可以更好的优化网络资源，建立更加合理的路由路径。

　　对到达的任意LSP链接请求r(s,d,b)表示，s和d分别表示业务流的入口和出口节点，b表示需要链接的业务流(s，d)的需求带宽，利用式(4)计算每条具体链路的链路权值,采用Diikstra's算法选择权值最小的路径建立LSP链接,并更新剩余网络带宽参数。

　　2.3 算法流程

　　对已经给定的网络拓扑，根据式(3)计算单个链路的初始权值w(I)对任意LSP链接请求，处理步骤如下：

　　STEP1：检测光路请求，如果光路请求为建立链路链接则执行STEP3，如果请求为拆除链路链接则执行STEP2：

　　STEP2：拆除LSP请求的链路，并更新网络剩余带宽：

　　STEP3：对于请求建立r(s,d,b)的路由路径请求，对于单个链路节点。确定链路剩余带宽R1，根据式(1)计算链路带宽利用率A1;

　　STEP4：删除网络中剩余带宽R1

　　STEP5：根据链路的初始权值以及链路带宽利用率计算每条链路I∈E的及时链路权值W(I);

　　STEP6：以W(I)作为链路J的权重，使用Dijkstra's算法查找权值最小的路径，建立链路链接;

　　SETP7：修改网络剩余带宽参数，准备处理下个LSP请求。

　　3 仿真分析研究

　　为了客观地分析MBGRA算法的性能，我们采用Kodialarn研究工作中使用的仿真网络拓扑图进行仿真分析[6].称为MIRAnet网络拓扑，结构如图1所示。

　　仿真中使用了15个节点的无向图网络拓扑，即每条链路都是双向的，为了更客观地反映实际网络结构.把网络拓扑中的链路容量分为两类，用细线标识的链路带宽容量为1200单位.代表OC-12，粗线标识的网络链路带宽容量为4800单位,代表OC-48。LSP链接请求的

　　入口路由器节点在S1-S4之间随机选择,出口路由器节点在D1-D4之间随机选择,请求带宽需求服从均匀分布。仿真过程分为静态链接请求和动态链接请求两种,在静态请求中成功建立链接的LSP的生命是永久性的,在动态请求中LSP的到达按泊松分布,持续时间按指数分布。

　　3.3.1 静态链接

　　在静态链接试验中每种路由算法做50次建立12000条LSP请求的试验,并且从零开始每增加500次LSP做一次数据统计,根据试验结果得出的LSP数目与链接拒绝率的曲线关系如图2。

　　从图中可以看出在网络负载较低时,三种算法的路由性能没有明显差别,但当链接数目增加到3000时MHA算法的拒绝率从零开始上升,而MIRA算法和MBGRA算法是在5000次请求之后才开始有拒绝链接。在7000次路由之后MBGRA算法的性能开始优于MIRA算法,在12000次时MHA算法的性能明显低于后两种算法,并且依据图形走势有继续恶化的趋势。由图2明显看出MBGRA算法在路由性能上明显好于MHA算法,并在高负载情况下性能优于MIRA算法,因此更有利于均衡网络负载。

　　为了更进一步验证MBGRA算法的性能,直接在MIRAnet网络中加载5500个LSP请求,连续做20次试验,记录三种算法的拒绝数目,从图3可以直观的看出MHA算法的拒绝数目一直处于最高,而MBGRA算法的拒绝数目一直处于最低层,性能高于MIRA算法。

　　3.3.2 动态链接

　　上面通过仿真试验证实在静态网络中MBGRA算法优化网络资源的优越性.在本节我们将在动态接人条件下仿真MBGRA算法的性能。假设LSP到达以平均速率为R的泊松分布到达每一个节点对,持续时间符合I/Q的指数分布。加载1000000 LSP在MIRAnet网络中,并且假设R/Q=1500。

　　通过图4的统计数据显示,在MIRAnet网络动态请求过程中MHA算法的拒绝率明显最高,MIRA算法比MHA算法性能好,但是拒绝率也高于MBGRA算法,MBGRA算法的拒绝率一直处于最低,因此此算法在减少网络拥塞率和优化网络资源上有优越的性能,并且链路复杂度低。

　　4 结束语

　　本文针对MPLS技术提出了一种高效能的有带宽保证的动态负载均衡路由算法MBGRA。通过静态链接以及动态链接的仿真试验表明MBGRA算法在均衡网络负载、优化网络资源方面的有良好的性能。