一种多协议标签交换流量工程的k条最短路径的动态路由算法

一种多协议标签交换流量工程的k条最短路径的动态路由算法

1动态路由优化算法多协议身份验证（pms）是下一代网络技术的先进技术之一。基于mpl的商业设计主要基于mpl的面向连接和显式路径的特点，将网络流量基于适当的粒度分布到相应的标记交换路径（lps）。根据资源优化原则，维护所有lps物理路径，能够很好地控制网络中的流量分布，显著提高网络交换速度，减少网络复杂性，并提供有效的qos（quiu出口商）的保证。约束路由技术是流量工程的核心技术,研究者提出了许多动态路由算法,包括最短路径算法(CSPF)和最小干扰路由算法(MIRA)等,但都不能有效的解决链路使用不均衡问题.因此,本文提出了一种新的K路径标号算法(KPathLabelAlgorithm,简称KPLA).该算法首先利用扩展标号算法计算出K条最短路径,进一步考虑链路关键度和链路最大剩余带宽的影响,并结合预计算和在线计算减少计算复杂度.模拟结果表明,算法的性能与CSPF和MIRA等相比有较大提高.2最小干扰路由算法目前MPLS-TE的实现多使用最短路径算法(CSPF)选择路径.其核心思想是通过选择源到目的的最短路径,达到节省网络资源的目的.CSPF计算复杂度低,容易实现和部署,同时也是很多启发式路由算法的基础.但是CSPF未从全网的范围内考虑网络流量分配和性能优化,容易导致部分链路被过度使用而引起网络拥塞.Kodialam等首次利用了MPLS网络入出口节点对已知的性质,指出在这些入出口对之间存在着互相竞争使用网络链路的关系,并把这种现象命名为干扰现象.他们首次提出了最小干扰路由算法(MIRA),试图在寻路时使得各个入出口对之间的干扰最小,从而实现网络资源的优化利用.MIRA的关键思想是:在为当前请求选择LSP时,考虑将来可能存在的请求对链路的需求,该请求的LSP必须尽可能地避免干扰其他SD节点对满足将来需求的路由的建立.MIRA在性能上取得了显著的提高,是本领域中比较著名的研究工作.但是MIRA也存在一些缺点:一是某些被MIRA认为是非关键的链路有些情况下是非常重要的;二是MIRA有可能选择过长的路径,不利于节省网络资源;三是计算复杂度较高.因此,本文在MIRA基础上提出一种新的启发式算法KPLA,并针对MIRA的以上缺点进行了较完备的改进.3链路算法的高效快络本文提出K路径标号算法.算法首先基于扩展标号算法来计算K条最短路径集合,避免忽视掉重要的非关键链路,而同时将最大流计算映射为最短路径权值的计算降低了计算复杂度,然后综合考虑链路关键度和链路最大剩余带宽的影响,结合K值赋予不同的链路权值,避免选择过长的路径,并进一步结合预计算和在线计算减少计算复杂度,使得算法高效快捷.我们首先定义网络模型和介绍相关概念.3.1网络模型的建立我们使用图论工具来描述网络图拓扑模型.采用一个n个点m条边的无向加权连通图G(V,E,C)为网络的模型,其中,n表示节点个数,m表示链路数,V代表网络中路由器的集合,E为链路集合,C为链路带宽集.V中的子集(s,d)作为产生LSP请求的入口出口节点对集合,其中,s为入口节点,d为出口节点,(i,j)∈(s,d).R(l)表示任意时刻链路l的剩余带宽.3.2扩展标记算法由于传统的K-最短路径算法如二分扫除法等求出的K-最短路径无法保证是简单路径,可能存在回路,因此本文提出扩展标号算法以求出K条最短路径长度,算法对节点进行标号,消除了路径存在回路的可能性,确保求出无回路的K条最短路径.我们用链表LIST记录节点,对于V中的每一个顶点j,赋予两个标号:距离标号uj,记录从起点到该顶点的最短路径长度的上界;前趋标号predj,记录当起点s到该顶点j的一条路长取到该上界uj时,该条路中顶点j前面的那个直接前趋节点,wij为权值.具体步骤如下:1.设h1j1j,h2j2j,…,hkijjkijj分别为入口s到任意节点j的最短路径长度,次最短路径长度,…,次k短路径长度,距离标号u1j1j,u2j,…,ukj分别记录入口s到任意节点j的最短路径长度上界,次最短路径长度上界,…,次k短路径长度上界.前趋标号pred1j,pred2j,…,predkj分别记录当起点s到该顶点j的一条路长取到该上界uj时,该条路中顶点j前面的那个直接前趋节点,其中(j∈V).初始化所有hxj,令2.计算最短路径长度h1j,方法如下:(1)令链表LIST(1)记录已经求得最短权值距离的节点,LIST(1)={s},u1s=0,前趋标号pred1s=0,对所有其它节点j令u1j为无穷大.(2)如果LIST(1)=∅,则结束,u1j就是从起点s到节点j的最短路长,最短路通过前趋标号回溯获得,否则,进行下一步.(3)从LIST中删去一个节点i,对从i出发的每条弧(i,j)判断是否满足u1j>u1i+wij.如果是,则令u1j=u1j+wij,并令LIST(1)=LIST(1)∪{j}.当从i出发的所有弧都检查完以后,转步(2).3.利用已有的h1j计算次最短路径长度h2j,方法如下:(1)令链表LIST(2)记录已经求得次最短权值距离的节点,LIST(2)={s},u2s=0,前趋标号pred2s=0,对所有其它节点j令u2j为无穷大.(2)如果LIST(2)=∅,则结束,u2j就是从起点s到节点j的次最短路长,次最短路通过前趋标号回溯获得,否则,进行下一步.(3)从LIST(2)中删去一个节点i,对从i出发的每条弧(i,j)判断是否满足u2j>min{[u2j,u1i+wij,u2i+wij]/[u1j]},运算A/B表示集合A去掉集合B后形成的集合.如是,则令u2j=min{[u2j,u1i+wij,u2i+wij]/[u1j]},并令LIST(2)=LIST(2)∪{j}.当从i出发的所有弧都检查完以后,转步(2).4.利用已有的h1j,h2j,…hn-1j计算次n短路径长度hnj,方法如下:(1)令链表LIST(n)记录已经求得次n短权值距离的节点,LIST(n)={s},uns=0,前趋标号predns=0,对所有其它节点j令unj为无穷大.(2)如果LIST(n)=∅,则结束,unj就是从起点s到节点j的次n短路长,次n短路通过前趋标号回溯获得,否则,进行下一步.(3)从LIST(n)中删去一个节点i,对从i出发的每条弧(i,j)判断是否满足unj>min{[unj,u1i+wij,u2i+wij,…uni+wij]/[u1j,u2j,…,un-1j]}如果是,则令unj=min{[unj,u1i+wij,u2i+wij,…,uni+wij]/[u1j,u2j,…,un-1j]},并令LIST(n)=LIST(n)∪{j}.当从i出发的所有弧都检查完以后,转步(2).5.按照上述方法,直至n=k,即可计算次k最短路径长度hkj.分析以上算法我们可以得出结论:扩展标号算法对任何节点最多进行K次重新标号,重复执行扩展标号算法必定能够得出K条最短路径,且其复杂度为O(kmn).运用扩展标号算法来计算K条最短路径集合,能够避免忽视掉重要的非关键链路,而同时将最大流计算映射为最短路径权值的计算降低了计算复杂度.3.3链路关键度估计算本算法分为预计算和在线计算两个阶段.预计算阶段算法首先使用扩展标号算法来计算K条最短路径集合,然后删除网络中链路剩余带宽R(l)小于C的瓶颈链路,得到残留网G′,残留网中链路的权重不会改变.由于网络拓扑和链路结构较少发生改变,我们将定位关键链路部分放在预计算阶段进行.本文定义链路关键度的概念,它反映了任意链路在静态拓扑信息网络中链路可能的负载.链路关键度的引入有助于减少那些容易发生拥塞的路径的负载,其函数值如公式(1):式中α(l)表示链路l的链路的关键度,Fl(s,d)表示入/出节点对(s,d)之间的最大流中通过链路l的流量,m(x)表示所有节点对中通过链路l的最大流数量.α(l)即为链路l所占所有入/出节点对的网络最大流流量的平均值.3.4链路权重函数的合成在线计算阶段我们进一步设置链路权重以求出最短路径.该阶段网络提供的动态信息是最大剩余带宽R(l),R(l)代表了该路径上可用最大带宽,给我们提供了每个入/出节点对之间的不同路径的带宽利用情况,在本算法中剩余带宽越少的路径,被选择路由的可能性越小.我们针对不同K值的大小,将链路关键度和最大剩余带宽两个信息量合成链路权重函数β(l),公式如下:式中α(l)表示链路l的链路关键度,R(l)表示链路l的剩余带宽,β(l)即为路径l上的每一条链路的α(l)/R(l)比值和再加上K倍的权值系数λ.通过式(2)得出每条链路的成本后,选择β值最小的可行路径为最短路径路由带宽需求为c的当前LSP请求r(s,d,c),最后更新网络中链路的剩余带宽R(l).3.5残留网gKPLA算法的步骤如下:输入:G(V,E,C),LSP请求r(s,d,c).输出:在s和d之间有c单位带宽容量的一条路由.Step1.应用扩展标号算法求出K条最短路径Step2.删除网络中链路剩余带宽R(l)小于C的瓶颈链路,得到残留网G′;Step3.根据公式(1)计算链路关键度α.Step4.根据公式(2),计算出k条最短路径相应的链路权值β.Step5.选出β值最小的路径,如果该路径的每一条链路的剩余带宽都高于请求带宽,则该路径即为最短路径.Step6.否则选出β值次小的路径,如果该路径的每一条链路的剩余带宽都高于请求带宽,则该路径即为最短路径,否则进一步选出β值稍大的路径,直至β值最大的路径.Step7.如果每一条备选路径都没有选上,则拒绝该请求,返回到Step1,输入下一个请求.Step8.从s到d沿着最短路径路由带宽需求为c单位的LSP,更新链路剩余容量;Step9.返回到Step4,为下一个LSP请求做好准备.3.6算法复杂度的估计我们根据算法步骤来分析复杂度.Step1遍历一遍网络中所有链路,执行k次扩展标号算法,复杂度为O(kmn),Step2、Step3需O(m),Step4～9最多需O(kn2).因此,算法总的复杂度为O(kmn+kn2),实践中k通常取较小的常数,比MIRA的复杂度Ο((p-1)n2√m)要低.同时,由于实际网络中网络拓扑结构很少改变,Step1～3在预计算阶段进行,只有当网络拓扑结构改变时才重新计算,所以KPLA复杂度实际为在线阶段的复杂度O(kn2).因此我们可以得出:KPLA求出的LSP路径能够有效的进行LSP路由,并且算法高效快捷.4业务请求中三种算法间的比较本节我们通过模拟仿真实验来评价KPLA算法的性能表现.NS2是一种面向对象的、离散事件驱动的网络环境模拟器,能够支持众多的协议,提供了丰富的测试脚本,是目前网络分析、研究和教学的首选工具.本文在linux平台下,运行NS2的ns-allinone-2.26版本,进一步使用mns_v2.0扩展包向NS2添加MPLS流量工程模块,并修改文件夹/ns-allinone-2.26/ns-2.26/tcl/mns_v2.0中的ns-mpls-cr.tcl文件以及部分底层C++源代码文件以实现路由算法,最后采用数据分析工具awk分析运行产生的.tr文件分析结果.本实验选择较为流行的CSPF、MIRA与KPLA算法在拒绝率、时延、吞吐量以及路由计算时间等性能指标上进行比较分析.实验中,我们设置K=3,权值系数λ=0.1.网络拓扑结构如图1所示,由学术界普遍认同的MIRA算法拓扑结构改进,能够较好的模拟实际中的网络拓扑结构,并便于同其他算法进行比较.其中节点0、1、2、13、14、15是传统路由器,节点3、4、5、6、7、8、9、10、11、12是支持MPLS的标记交换路由器LSR(LabelSwitchingRouter),用正方形表示,链路带宽如图1所示.在本实验中我们建立三种业务请求:(1)节点0发送数据流到节点13;(2)节点1发送数据流到节点14;(3)节点2发送数据流到节点15;在这三对入/出节点对之间分别建立5、10、15、20、25、30、35、40、45、50个LSP请求,请求频率为每隔0.1秒同时建立一个请求,请求带宽为200kb/s.三种算法在不同LSP请求数量下被拒绝的请求数如图2所示.从图2中可以看出,在30个请求之后CSPF首先出现了拒绝请求的行为,且拒绝数始终最大,这是由于其采用直接抢占机制,导致部分链路被过度使用而引起网络拥塞;35个请求以后MIRA和KPLA都出现了拒绝请求的行为,但KPLA的请求拒绝曲线始终处于最低端.这表明KPLA从全网的范围内考虑网络流量分配和性能优化,采用的K条最短路径集合能够有效地避免忽视掉重要的非关键链路,同时利用链路权值均衡了负载分布,有效地减少了网络拥塞.图3是三种算法在进行业务请求(1)时端到端平均时延的比较.CSPF从10个请求以后上升较快,这是因为CSPF算法在带宽满足的情况下只选择最短的路径,没有考虑后续请求的到达.KPLA在前10个请求时,延迟比CSPF和MIRA稍大,这是由于KPLA须离线计算,导致初始延迟较大;10个请求以后,KPLA延迟明显降低,表明KPLA综合考虑了进出口节点对、链路关键度和最大剩余带宽的影响,能够更好地均衡网络负载,进一步结合K值赋予不同的链路权值,避免了选择过长的路径,减小了请求运行时间和拥塞等待时间.图4是分别运行三种算法时终端链路node11→node13的吞吐量的比较.如图所示KPLA的吞吐量从1.5秒开始在三种算法中一直是最大的,这说明KPLA算法计算最短路径和最大流时,综合考虑了进出节点对、链路关键度及最大剩余带宽的影响,产生的路径对未来LSP请求的干扰最小,并从全局范围内进行流量分配,使得更多的LSP请求均衡地通过网络,扩大了链路的吞吐