一种最小化最大带宽利用率的TE路由算法

26卷第3期小型微型计算机系统Vol.26No.3MINI-MICROSYSTEMS2005年3月Mar.2005TE王新红1,刘富强1,王光兴21(同济大学电信学院,上海200092)东北大学网络与通信中心,辽宁沈阳110006)2(E-mail:wangxinhong@163.com-:随着网络中流量的迅速增长,流量工程对于减小拥塞、提高网络资源的使用效率、满足业务的QoS要求,正在起着越来越重要的作用.提出了一种对Dijkstra算法进行改进的最小化最大带宽利用率TE路由算法.该算法在搜寻路径的过程中,将原来Dijkstra算法中的以路径代价最小为目标,更改为以最小化最大带宽利用率为目标.仿真证明,算法在一定程度上达到了均衡负载分布的作用.:流量工程;路由算法;带宽利用率;均衡负载:TP393:A:1000-1220(2005)03-0422-03RoutingAlgorithmtoMinimizeMaximumLinkUtilizationWANGXin-hong1,LIUFu-qiang1,WANGGuang-xing21(ElectrandIormationEng,ongjiUniversity,Shanghai200092,China110006,China))2(etworkand,NortheasternUniversity,Shenyang:Withtherapidgrowthofthetrafficinthenetwork,trafficengineeringisplayingamoreandmoreimportantroleinAbstractreducingcongestion,improvingresourceutilizationandsatisfyingthequalityofservice.Inthispaper,aTEalgorithmispro-posedtominimizemaximumlinkutilizationbasedonmodificationofDijkstraalgorithm.Itreplacesfindingtheleastcostpathwithfindingthepathwithminimalbandwidthutilization.Thesimulationshowsthatthealgorithmbalancestheloaddistribu-tiontosomeextent.ds:trafficengineering;routingalgorithm;rateoflinkutilization;loadbalance1通过对流量工程的研究,可以很好地维护网络均衡状态,避免拥塞的产生,从而使用户的要求得以满足QoS.随着计算机网络中业务流量的迅猛增长,如何高效的利流量工程,归根到底是基于业务流所请求的资源和网络用网络资源并保证业务的QoS要求得以满足正在变得越来当前的可用资源,通过对业务流的合理路由来实现的,所以其越重要.传统的最短路径路由经常导致以下问题:(1)当来自核心问题是路径计算问题.实现流量工程的路由技术称为TE不同源的多条最短路径都使用某一链路并超过该链路容量[4,5]路由.本文将提出一种对Dijkstra算法进行改进的最小化时,该链路将发生拥塞;(2)当源到目的间的业务流超过最短最大带宽利用率的TE路由算法.需要说明的是,在选路过程路径上的链路容量时,最短路径将发生拥塞,而它们之间的较我们考虑的约束条件仅为带宽要求这是由于其他中QoS,,长路径却不被使用.为了解决这种由于负载分布不均衡而的要求如时延、丢包率等可以转化为等效带宽的形[1]QoS,,引起的网络拥塞,提出了流量工程(,式而且很多实时应用也对带宽有严格的要求并且网络TETrafficEngin,.,[6]eering)[2,3]的概念.中链路状态信息的获取和更新通过信令协议MPLSRSVP-流量工程是一个控制业务流如何经过网络,以达到优化TE或CR-LDP来进行.网络资源利用、提高网络性能目的的过程.流量工程目前被公2认为MPLS网络最重要的TE发布了多个RFC和草案.在传统的网络中,数在近十几年来路由得到了广泛的关注但路由,QoS,TE据的转发是由路由器按照Hop-by-Hop的方式完成,每个路和路由有所不同路由应用之一,IETF已经针对MPLS-InternetIPQoS.QoS是在一延、时延抖动等的路由定的可用网络资源下由器独立地决定数据转发的策略,无法要求其它路由器按照指定的路径传输.在网络中,数据的转发沿着问题而路由具有更加广泛的目标它不仅要从个体MPLS,.TE[4,7]求解满足单个流要求如带宽、时QoS()进LSP.行,只要使LSP按照指定的路径建立,就能符合TE的要求上考虑——满足特定流的要求,还要从全网的角度上QoS日期:2003-08-28介,女,1974年生,博士,主要研究方向为计算机网络、QoS、路由技术等,男,1965年生,教;,主要研究方向为多媒体技术、计算机网络等,男,1937年生,教授、博士生导师,主要研究方向为计算机网络和多媒体通信.:授、博士生导师;3期王新红等:一种最小化最大带宽利用率的TE路由算法423考虑——优化网络性能,均衡负载分布,使网络处于良好的运请求带宽为b的新呼叫后,链路(i,j)的带宽利用率为行状态.与QoS路由的目标有所区别,通常进行TE路由的目标是均衡负载分布,降低对未来请求的阻塞率,避免拥塞的产生.关于TE路由问题,正在引起人们的关注,目前已经提出了一些算法.-×100.U=1-ijij3.路径带宽利用率:对于P(i,j)∈P,路径P的带宽利用率U(P)l定义为P上所有链路带宽利用率的最大值,lGuerin等提出了一种最宽最短路径算法(WSP,Widest-ShortestPath)[8].首先利用Dijkstra算法寻找源到目的之间跳数最少的路径,如果存在多条的话,选择其中路径剩余带宽最大的一条.该算法的性能优劣依赖于网络中存在多条最短路径,如果网络中只有一条最短路径,那么该算法的性能与最短路径路由算法是一样的.即.U(P)=MaxUlPl(i,j)∈链路带宽利用率反映常也反映该链路的负载情况.路径带宽利用率在这里由该路径上负载最重的链路的带宽利用率来表示,也就是反映了选.当U→1,也就了某条链路上的带宽使用情况,通Kodialam和Lakshman提出了一种最小干涉路由算法(MIRA,MinimumInterferenceRoutingAlgorithm)[9,10].为了减小请求的阻塞率,算法根据最大流最小割原理,在选路时选择对入口-出口节点对产生“干涉”最小的链路.该算法由择该路径后造成的链路负载加重的最坏程度i,j是链路(i,j)的负载比较重时,节点i和j间链路的可用带宽与,将其他经过该链路的连接请求.当较小链连接所请求的带宽接近,那么在这一链路上接纳此连接后来会很难再接纳路负载较轻时,节点和间链路的可用带宽比较U,i,j于需要执行多个最大流计算,其算法复杂度较高Suri等提出了一种基于轮廓的路由(PBR,Profile-BasedRouting)[11]算法.该算法分为两部分,离线部分根据流量轮来接纳新廓,通过求解多商品流问题的方法,计算在每条链路上为每个为了避免拥塞的产生,在路由过程流量等级分配多少带宽,才能使经过该网络的流量最大;在线使用负载重的链路,即最小化负载最重的链路的使用.因而.多,那么在这ij条链路上接纳新的连接请求.的连接后剩余带宽还较为充足不会影响将,,显然,中应该尽量避免,部分负责计算具体的路径.PBR算法离线部分需要求解复杂在这里我们选路的目标就是以最小化最大带宽利用率为优化路使用那些带宽利用率的多商品流问题,并且需要事先已知流量轮廓,所以其扩展性目标,以使业务流避开拥挤的热点链,比较差.低的空闲链路同时,最小化最大带宽利用率也意味着链路上剩余带宽所占的比率被最大化,这样,链路上的剩余带宽尽可流的方能多,有利于降低请求的阻塞率,为未来接入更多的连接请求法,把问题模型化为线性规划问题,求解优化解,然而优化解留有余地.的求解比较困难,并且业务流要被拆分到多条显式路径上传.Wang等[12]为了减小拥塞,以最小化最大带宽利用率为TE目标,并提出了两种解决方法.一种是拆分业务基于以上考虑,最小化最大带宽利用率的TE路由问题流可以不用拆分,问题被可以描述如下输.第二种是非拆分的方法,即业务:模型化为整数规划问题,这个问题具有NP难度,作者提出了给定一个网络G(V,E),源节点∈sV,目的节点∈dV,对启发式算法——基于拆分优化解的重新法需要在第一种线性规划所得拆分解的基础上做重新路由优化,实现起来也非常复杂.本文也以最小化最大带宽利用率为路由算法,但是该算于P∈链路容量∈剩余带宽R∈已知要求(i,j)E,CR,R,++ijij找到一条从s出发,到目的节点d的路径P,使之在满足带宽约束Bandwidth(P)≥b的前提下,路径P的带宽利用率U(P)最TE目标,通过一种对Dijkstra算法进行改进的方法来进行求解.小,即满足(P)=Min(()).PU∈3网络模型化为一有向赋权图和链路集,节点数为n,链路数为m.对于每条链路(i,j)∈E,C→R+表示链路的容量,R→R表示链路的剩余带宽,请求表示为(,,),其中s,dG=(V,E),V,E分别表示本算法是在Dijkstra算法的基础上为度量,寻找源节点s到目的节点d的“度量最小的路径”.如果令节点i的代价cost(i)表示从源节点s到节点i的最大带宽利用率,则上述问题是一个-,以最大带宽利用率节点集+ijR+是正实数集.新到来的呼叫ijsdb,s∈V,d∈V,b为呼叫请求的带宽数.d之间存在多条路径P,所有MinMax问题,cost(i)=min(cost(i),max(cost(j),U)).分别为源和目的节点假设给定的源节点s和目的节点j∈Vjil算法分为两个阶段进行.首先,进行初始化的工作.删除不满足带宽要求的链路构造一个新图′,以后路径的寻找就的可用带宽是指该在这个新图中进行,并对算法运行做初始值的设定.第二个阶中,每一次循环都要找到k的路径带宽利用率最小的路径,直到节点即为目的节点d为止.这些路径构成给出几个定义1.路径的可用带宽:一条路径P一个集合5(,)={,,…,P}.我们首先sdPP21lG.l段就是具体的寻路过程.在这个过程路径的瓶颈带宽,也就是路径上所有链路可用带宽的最小值,源节点s到当前节点即k(P)=.,Bandwidthmin对网络中的每个节点i都定义一个结构Node[i],该结构l(,)∈2.链路带宽利用率:对于P(i,j)∈E,链路(i,j)接入包含三个元素,分别为minU、label和pre,其中minU记录从源424小2005年节点s到节点i的最小U;label表示节点i是否已经处理过,如果已经处理,label=True,否则label=False;pre表示到达节点i的前一跳节点.算法具体描述如下:出,开始时网络中的连接数比较少,链路上的负载比较轻,表1实验数ANBdemand25demand10MH0.27MMLU0.27123451.如果R<b,删除链路(,),得到图G′=(V,E′).2030405048710.430.600.800.970.400.530.670.822.对图G′中的每条链路(i,j)计算带宽利用率U.3.初始化.对Pi,j∈V,如果(i,j)|E′,U=0.Node[s].minU=ij960,Node[s].label=True.对Pi∈V-{s},Node[i].pre=-1,Node[i].minU=∞,Node[i].label=False.k=s.4.do{120两种算法的A值基本相同.随着连接数的增多,链路上的负载do对每个5.节点i≠s{逐渐加重,随之A值也逐渐加大,但是本算法中A值的增加要6.≠0且Node[i].label=Falsethen7.fmax(Node[k].minU,U)<Node[i].minUfki比MH算法中的小.这说明随着链路负载的加重,本算法在一kithen定程度上避免了业务流走负载重的链路,起到了均衡负载分8.Node[i].minU=max(Node[k].minU,U)ki9.10.endf11.endf12.}enddo13.k=0,mn=∞14.do对每个节点i≠s{经常使用的方法.本文提出了一种对Dijkstra算法进行改进15.fNode[i].label=False且Node[i].pre=k布的作用.6为了减小拥塞最小化最大带宽利用率是实现路由,TENode[i].minU<mnthen.,的最小化最大带宽利用率算法在算法搜寻路径的过程中将16.mn=Node[i].MinU算法中的以路径代价最小为目标更改为以最小17.k=i18.endf19.}enddo20.Node[k].label=True21.}while(k≠d)原来Dijkstra化最大带宽利用率为目标最后通过仿真对本算法和.,,最小跳数算法在接的连接请求下的最大带宽利用率的入不同数量.,,变化情况进行了比较结果证明随着连接数的增多本算法22.把从节点s到d的pre中存储的节点连起来,即得到节点s到在一定程度上避免了对部分链路的过度使用,起到了均衡负d的路径.载分布的作用.在该算法中,第5行到12行和第14行到19行的循环都分别需要运行中的节点数),而第4行到21-1次(其中是网络References:nn[1]XaoX,HannanA,BaileyB,NiL.Trafficengineeringwith行的外循环最多也要运行n-1次,因此整个算法的时间复杂MPLSntheinternet[J].IEEENetworkmagazine,Mar.度为((-1)2(-1)),即为On().2Onn*2000.[2]AwducheDetal.RequirementsfortrafficengneeringOverMPLS[S].IETFRFC2702,Sept1999.5[3]AwducheDetal.Overviewandprinciplesofnternettrafficen-对如图1所示的网络拓扑进行了实验仿真.假设每gineering[S].IETFRFC3272,May2002.我们[4]GargiBanerjee,DeepnderSidhu.Multi-constrainedpathcom-putationfortrafficengneeringnMPLSnetworks[C].In:Pro-ceedingsofSCSSPECTS,2001.[5]GargiBanerjee,DeepinderSidhu.ComparativeanalyofpathcomputationtechniquesforMPLStrafficengineering[J].Com-puterNetworks,2002,40(1):149-165.[6]RekhterYetal.CcosystemøsTagswitchingarchitectureovervew[S].RFC2105,Feb.1997.[7]WangYu-fei,WangZheng.Explicitroutingforinternettrafficengineering[J].IEEEINFOCOMø99,582-588.图1[8]GuerinR.ArelOrda,WilliamsD.QosroutingmechanismsandOSPFextensions[C].InProceedingsof2ndGlobalInter-个节点了解整个网络拓扑和链路状态信息.网络中所有链路netMnconference(ontwithGlobecomø97),Nov