MPLS业务量工程中负载均衡算法的研究

1、2001年9月第24卷第3期北京邮电大学学报JournalofBeijingUniversityofPostsandTelecommunicationsSept.2001.24No.3Vol文章编号:100725321(2001)0320046205MPLS业务量工程中负载均衡算法的研究张中山,隆克平,程时端(北京邮电大学程控交换技术与通信网国家重点实验室,北京100876)摘要:设计了MPLS业务量工程中3种负载均衡算法,仿真结果证实了这3种算法均能够不同程度地提高网络中数据流吞吐率及资源利用率.关键词:计算机通信网;多协议标签交换;业务量工程;负载均衡中图分类号:TN915.02文献标识码

2、:A业务量工程14是与网络性能优化密切相关的.它的一个主要目的是在实现方便、有效、可靠的网络操作的同时优化网络资源的利用率和数据流传输性能.MPLS能够有效的支持业务量工程.负载均衡是MPLS业务量工程中的一个主要内容.本文设计了3种负载均衡算法.1静态负载均衡算法1.1基于拓扑的静态负载均衡算法(TSLB)首先构造一个名为“路由”的数据结构来标识一条路由:路由=<路由ID><HOP><路由长度><空闲容量>其中,路由ID为一条路由区别于其他路由的标识号;HOP为该路由所通过的中间网络节点的顺序排列;路由长度标识该路由所跨越的链路数;空闲容量的含

3、义是:设路由R所经过的每条链路用L标识,其中i为链路的上游节点,j为链路的下游节点,再设L余带宽为Fi,j,则路由R的空闲容量定义为M(Fi,j).i,ji,j可供分配的剩再构造一个名为“可选路由集合”的数据结构.该集合包含从源节点到目的节点间所有可选的并行路由.其结构如下可选路由集合=路由1、路由2,路由n当源节点接到一个新的数据流发送请求时,首先建立可选路由集合,然后转到(1).(1)如果可选路由集合为空,转到(4);否则转到(2);(2)查找可选路由集合中长度最短的路由,看看该路由上是否存在足够的空闲容量满足该数据流的带宽要求.如果满足则转到(5),否则转到(3);(3)将可选路由集合中

4、长度最短的路由删除,转到(1);收稿日期:2000211230基金项目:华为科学基金资助项目作者简介:张中山(1974),男,硕士生.© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.第3期张中山等:MPLS业务量工程中负载均衡算法的研究47(4)空闲资源不足,无法传输该数据流,算法中止.(5)沿着所选的路由建立一条新的ER2LSP,将本次请求传输的数据流映射到该ER2.LSP上,然后更新这条路由的空闲容量,算法成功完成.该算法中,新到的数据流首先选择TSLB算法是在最短路由算法的基础上加

5、以改进的最短路由;当最短路由空闲容量不足时,选择次最短路由;只有当所有路由都不能满足数据流带宽要求时,算法才失败.这种算法有效的缓解了最短路由上的拥塞.但考虑到网络中数据流的到达是随机的.假设先到的低速率数据流占据大容量链路,而后到的高速率数据流因各条路由上的空闲容量均不满足其带宽要求而无法得到服务,因而造成了吞吐率及网络资源利用率的降低.举例如图1所示.图1多个并行链路的网络实例该例中有3个数据流:由Src1到Dst1、由Src2到Dst2以及由Src3到Dst3.其中,Src1突发速率不超过5.3Mbit s;Src2突发速率不超过3.7Mbit s;Src3突发速率不超过2.4Mbit

6、s.如果这3个数据流到达的顺序是Src1最先,Src2其次,Src3最后,则按照TSLB算法,这3个数据流都能映射到各自合适的路由上去.但如果这3个数据流到达的顺序是Src3最先,Src2其次,Src1最后,则按照该算法,Src3发送的数据流选取的路由是R52R62R112R14;Src2发送的数据流选取的路由是R42R62R72R112R13;此时各条路由上所剩下的空闲容量均不能满足Src1的带宽要求,因而Src1数据流发送请求被禁止.这样,由于数据流不合理的映射,造成了网络吞吐率和资源利用率的降低.基于资源的静态负载均衡算法解决了数据流发送的随机性所造成的网络资源利用率低的问题.1.2基于

7、资源的静态负载均衡算法(RSLB)该算法用到的数据结构与TSLB算法中定义的相同,算法描述如下:当源节点接到一个新的数据流发送请求时,首先建立可选路由集合,然后转到(1).(1)如果可选路由集合为空,转到(4);否则转到(2);(2)查找可选路由集合中空闲容量最小的路由,看它的空闲容量是否满足本次数据流的带宽要求,如果满足则转到(5),否则转到(3);(3)将可选路由集合中空闲容量最小的路由删除,转到(1);(4)空闲容量不足,无法传输新到的数据流,算法中止;(5)沿着所选的路由建立一条新的ER2LSP,将本次请求传输的数据流映射到该ER2.LSP上,然后更新这条路由的空闲容量,算法成功完成该

8、算法的原理是选择空闲容量与新到数据流带宽要求最为接近的路由.但是如果在很长一段时间内只有少数几个低速率数据流在发送,则网络中的大容量链路可能长时间处于空闲© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.48北京邮电大学学报第24卷状态.同时由于分配给数据流的空闲容量与其带宽要求非常接近,所以该算法不能很好地适应数据流的突发性,有可能由于一段时间内数据流突发速率很高而丢包.1.3两种静态负载均衡算法的局限以上介绍的两种负载均衡算法均有其局限性.造成这种局限性的最根本原因是由于这2种负载均衡

9、算法都是静态的,一条ER2LSP一旦建立,是不会被其他ER2LSP抢占资源的,也不会自动重选路由到更合适的路由上去.而在某些情况下,如果一条ER2LSP能够主动将其所承载的数据流重选路到另一条路由上去,使该数据流原先所在的路由上原本较小的空闲容量变成较大的空闲容量供一个高带宽要求的数据流使用,既能保证原先数据流传输不被中断,又能增大网络吞吐率和提高网络资源的利用率.2动态负载均衡算法(DLB)2.1算法描述首先构造2个数据结构“路由”和“可选路由集合(SRC)”.其定义与TSLB中定义的相同.然后再构造一个名为“ER2的数据结构来标识一条ER2LSP”LSP:ER2LSP=<数据流ID&

10、gt;<LSPID><路由ID><ER2LSP占用带宽UB><空闲容量FC><贡献带宽CB>其中,数据流ID标识该ER2LSP上承载的数据流;LSPID为该ER2LSP区别于其他ER2LSP的标识号;路由ID标识该ER2LSP所通过的路由;ER2LSP占用带宽UB是该ER2LSP所占用的资源;空闲容量FC的含义与TSLB中定义的相同;贡献带宽CB的含义是:如果该ER2.LSP将其所占用的资源全部让出的话,则沿着这条路由可供分配的空闲容量一共是多少再设置一个变量“pending2Traffic”用来保存当前正待选择路由或重选路的数据流I

11、D.对于每一个新到的数据流或需要重选路的数据流,构造一个“协商LSP集合”.该集合包含所有并行的可协商ER2LSP,其所经过的路由包含在SRC中,并且其UB值小于当前待选路由的数据流的带宽要求.其结构为协商LSP集合=ER2LSP1,ER2LSP2,ER2LSPn再设置一个“待选路由栈(TS)”,用来暂存尚未选路的数据流ID.当源节点接到一个新的数据流传输请求时,首先建立SRC,将TS清空,再将pending2Traffic赋值为本次路由请求的数据流ID,然后转到(1).(1)首先使用TSLB算法对pending2Traffic所标识的数据流进行选路,成功则转到(9),否则转到(2);(2)建

12、立SRC,再为pending2Traffic所标识的数据流建立协商LSP集合,转到(3);(3)如果协商LSP集合为空,转到(6),否则转到(4);(4)查找协商LSP集合中UB最小的ER2LSP,看其贡献带宽CB是否大于pending2Traffic所标识的数据流的带宽要求,若大于则转到(7),否则转到(5);(5)将协商LSP集合中UB值最小的ER2LSP删除,转到(3);(6)空闲资源不足,无法传输新到的数据流,算法中止;(7)将当前的pending2Traffic值压入TS栈顶,再将pending2Traffic赋值为协商LSP集合中UB值最小的数据流ID,从SRC中删除当前pendi

13、ng2Traffic所标识的路由,转到(1);(8)拆除pending2Traffic值所对应的ER2LSP,将pending2Traffic赋值为TS的栈顶值,© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.第3期张中山等:MPLS业务量工程中负载均衡算法的研究49然后TS栈顶退栈,转到(1);(9)如果TS为空,则算法成功完成;如果TS不空,则转到(8).2.2算法分析由于DLB同时考虑到了网络资源占用情况以及网络中负载的特征(传输速率的突发性),在以上所介绍的3种负载均衡算法中,这

14、种算法最有效.3仿真评估以图1所示的网络为例,假设数据源发送的顺序是Src3在第0.1s开始发送、Src2在第2.0s开始发送、Src1在第4.0s开始发送,通过对最短路由算法及以上所述的3种负载均衡算法分别进行仿真,比较出了各算法在吞吐率及网络资源利用率方面的性能差异,如图2图5所示.图2最短路由算法图3TSLB算法图4RSLB算法图5DLB算法从图2图5所示的仿真结果可以看出,应用最短路由算法,网络吞吐率及资源利用率是最低的,网络资源利用率在45%以下.对于3种负载均衡算法,RSLB和DLB效果要好于.但在轻负载的情况下,DLBTSLB.在重负载的情况下,RSLB和DLB二者性能差别不大明

15、显要好于RSLB.从图4、图5可以看出,在第4.0s到第6.0s之间,3个数据流的吞吐率均达到各自的最大值,网络资源利用率也均接近于100%.但在第0.1s到第4.0s之间,Src1尚未发送数据包,Src2发送的数据流的吞吐率严格限制在3.0Mbit s以下,Src1发送的数据流的吞吐率严格限制在2.0Mbit s以下,网络资源利用率也限制在60%以下,并且这3条曲线都比较平稳.而在图5中,在这个时间段,Src2发送的数据流的吞吐率平均也保持在3.0Mbit s附近,但波动较大,最大可达3.6Mbit .此时网络资源利用s,Src1发送的数据流也有相同的特征率平均保持在60%左右,但波动性较大

16、,最大利用率接近70%.正是这种波动性,保证了© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.50北京邮电大学学报第24卷.当然DLB算法在网络轻负载的情况下比RSLB算法更好地适应了数据传输速率的突发性.但总的来说,DLB算法的运算开销会非常大,这种开销将成为DLB算法有效性的制约因素当并行路由的数量不太大、网络负载较轻的情况下,这个算法是最有效的.4结论本文对所提出的3种负载均衡算法进行了分析和仿真评估.仿真结果表明:3种负载均衡算法均能不同程度的缓解最短路由上的拥塞问题,其中,动态

17、负载均衡算法(DLB)无论是在网络资源利用率还是吞吐率方面,其性能均优于静态负载均衡算法.本文仅研究了无优先级情况下的负载均衡算法,在多优先级情况下的负载均衡算法尚待进一步研究.参考文献:1IETFRFC27021999,RequirementsfortrafficengineeringoverMPLSS.2IETFRFC24301998,Aproviderarchitecturefordifferentiatedservicedandtrafficengineering(PAS2TE)S.3GhanwanAnoop,JamoussiBilel.Trafficengineeringstanda

18、rdsinIPnetworksusingMPLSJ.IEEECommunicationsMagazine,1999.4XiaoXipeng,HannanAlan.TrafficengineeringwithMPLSintheinternetJ.IEEENetwork,2000.TheResearchforLoad-BalancingAlgorithmsinMPLSTrafficEngineeringZHANGZhong2shan,LONGKe2ping,CHENGShi2duan(NationalLaboratoryofSwitchingTechnologyandTelecommunicationNetworks,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)Abstract:ThreeLoad2BalancingAlgo