分布式控制平面:并行BGP路由计算自适应负载均衡算法  

Distributed Control Plane:Adaptive Load Balancing for Parallel BGP Route Computing

作　　者：江学智[1,2] 徐明伟[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]石家庄机械化步兵学院,石家庄050083

出　　处：《计算机学报》2010年第9期1591-1601,共11页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2009CB320502);国家"八六三"高技术研究发展计划项目基金(2009AA01Z251);国家"十一五"科技支撑计划(2008BAH37B03)资助~~

摘　　要：下一代互联网高度可扩展支持服务动态部署.越来越多延时和抖动敏感服务(如IPTV、VoIP等)的应用对BGP路由计算的性能提出了更高的需求.路由器采用分布式控制平面和实现并行BGP路由计算克服集中控制平面的性能瓶颈是解决这个问题的有效途径.但现有并行BGP路由计算方案因负载均衡性能差影响了系统的并行性能.文中基于Hashing技术提出了并行BGP路由计算自适应负载均衡模型.通过在线统计路由更新设计了自适应负载均衡算法P-AP(Prediction-based Adaptive Partition),自适应地动态调整路由更新在处理节点间的分配.最后设计和实现了原型系统,并利用Route Views收集的BGP Update数据进行实验.实验结果表明,P-AP算法具有负载均衡性能好、负载调整频率小和路由计算加速性能好等特点,能够有效地提高并行BGP路由计算性能.The high scalability of next generation Internet supports deploying Internet services dynamically. With the deployment of more and more delay- and jitter- sensitive applications such as IPTV and VoIP, more route processing power is required to improve the performance of BGP route selection. Routers adopt distributed control planes and implement parallel BGP route processing, which is a potential approach to overcome the bottleneck of centralized control planes and improve the performance of route computation. However, current BGP parallel route computing schemes cannot keep load balance well, which degrades the performance of parallel route computing. In this paper, a load balance model for parallel BGP route computing is proposed based on hashing. Through accumulating prefix updates online and reallocating them among all processing nodes adaptively, the authors propose P-AP （Prediction-based Adaptive Partition） algorithm for parallel BGP route computation, design and implement the prototype of load balancing for parallel BGP route computation. Route Views BGP Update dataset is used to verify the performance of P-AP algorithm. Experimental results show that P-AP algorithm can balance load well among allprocessing nodes, minimize load adjusting, and have the maximum speedup of route computation. It can effectively improve the performance of parallel BGP route computing.

关 键 词：分布式控制平面 BGP 并行路由计算 负载均衡 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]