MR-PBGP: A Multi-Root Tree Model for Parallel BGP
Yaping Liu, Shuo Zhang, Baosheng Wang · 2012
BGP protocol has been confronted with many performance problems caused by large scale networks, and have raised great concerns of industry and academia. In this paper, we present a multi-root tree model called MR-PBGP for parallel BGP in the context of a multi-core platform with shared memory. This model is an integrated model of the neighbor-based division and data division. We prove that threads of BGP constructed by a multi-root tree with binary bough excluding the first-level branch nearest leaves will achieve optimal performance with unlimited number of cores (ideal case) in a router. However, with limited number of cores (actual case), we proposed an approximation algorithm to solve this nonlinear programming problem. Simulation results show that (i) the approximation algorithm can get a good performance speedup and parallel efficiency w.r.t. the increase of its neighbors. (ii) 50% of the optimal performance can be reached by using only 5% of the ideal number of cores. Comparing with other researches, MR-PBGP is a more effective model for parallel BGP.