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

基于网络最大流的MPLS流量工程动向路由算法要点基于网络最大流的MPLS流量工程动向路由算法要点/基于网络最大流的MPLS流量工程动向路由算法要点基于网络最大流的MPLS流量工程动向路由算法基于网络最大流的MPLS流量工程动向路由算法种类：通信网络1序言动向路由算法是MPLS流量工程中最要点的技术之一[1，2]，建立有带宽保证的路由问题已经有大量的先期工作，其中代表性的路由算法主要有最小跳算法(min-hopaIgorithm，MHA)、最宽最短路径算法(widestshortestpath，WSP)[3]、最短最宽路径算法(shortestestwidestpalh，SWP)[4,5]、以及最小搅乱路径算法(minimuminterferenceroutingalgorithm，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)是静态的，在网络拓扑必然的条件下不发生变化，只有当网络拓扑发生变化时才需要重新计算。离线阶段对任意给定的网络拓扑结构，对任意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，∈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<b的链路，获取预留网络G'：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做一次数据统计。在网络负载较低时,三种算法的路由性能没有明显差异,但当链接数目增加到3000时MHA算法的拒绝率从零开始上升,而MIRA算法和MBGRA算法是在5000次央求今后才开始有拒绝链接。在7000次路由今后MBGRA算法的性能开始优于MIRA算法,在12000次时MHA算法的性能明显低于后两种算法,并且依照图形走势有连续恶化的趋势。由图2明显看出MBGRA算法在路由性能上明显好于MHA算法,并在高负载情况下性能优于MIRA算法,因此更有利于均衡网络负载。为了更进一步考据MBGRA算法的性能,直接在MIRAnet网络中加载5500个LSP央求,连续做20次试验,记录三种算法的拒绝数目,从图3可以直观的看出MHA算法的拒绝数目向来处于最高,而MBGRA算法的拒绝数目向来处于最低层,性能高于MIRA算法。动向链接上面通过仿真试考据明在静态网络中MBGRA算法优化网络资源的优越性．在本节我们将在动向接人条件下仿真MBGRA算法的性能。假设LSP到达以均匀速率为R的泊松分布到达每一个节点对,连续时间切合I/Q的指数分布。加载1000000LSP在MIRAnet网络中,并且假设R/Q=1500。经过图4的统计数据显示,在MIRAnet网络动向央求过程中MHA算法的拒绝率明显最高,MIRA算