Chinese Journal of Computers   Full Text
Title	Distributed Control Plane: Adaptive Load Balancing for Parallel BGP Route Computing
Authors	JIANG Xue-Zhi1), 2) XU Ming-Wei1)
Address	1)(Department of Computer Science and Technology, Tsinghua University, Beijing 100084) 2)(Shijiazhuang Mechanized Infantry Institute, Shijiazhuang 050083)
Year	2010
Issue	No.9(1591—1601)
Abstract &   Background	Abstract 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 all processing nodes, minimize load adjusting, and have the maximum speedup of route computation. It can effectively improve the performance of parallel BGP route computing. Keywords distributed control plane; BGP; parallel route computation; load balancing Background The explosive growth of the Internet and delay- and jitter- sensitive applications such as VoIP and IPTV requires real-time route calculation. However, current routers are restricted by the bottleneck of a single control element (CE) on centralized control plane. With the exponentially growth of BGP updates and hardware limitations of current router control plane, next generation routers demand exploiting distributed control plane that consist of multiple CEs to implement parallel BGP route processing. But the burst of BGP updates impedes load balance. Traditional BGP parallel route processing schemes always allocated route updates unreasonably and load unbalanced among CEs. It seriously degraded the performance of parallel route processing. With the support of National Basic Research Program(973 Program) of China under grant (No.2009CB320502) and the National Science & Technology Pillar Program during the Eleventh Five-Year Plan Period under grant (No.2008BAH37B03), the authors have researched on the distributed control plane architecture and parallel route table computation. To improve the performance of parallel BGP route computation, we propose a load balance model for BGP distributed parallel route computing based on hashing and devise an adaptive load balance scheme that dynamically divides prefixes into groups with hashing and adjusts the allocation of the prefix groups adaptively. Through accumulating prefix updates online, we propose P-AP (Prediction-Based Adaptive Partition) algorithm to allocate prefix updates among all CEs adaptively. With the support of National High Technology Research and Development Program (863 Program) of China under grant (No.2009AA01Z251), the authors designed and implemented the prototype of load balancing for parallel BGP route computing. Using Route Views BGP Updates dataset, we verify the performance of P-AP algorithm. The experimental results show that P-AP algorithm keeps load balanced, minimizes the frequency of load adjusting, and has the maximum speedup of route computing. It effectively improves the performance of parallel BGP route computing.