Research On BGP Convergence Algorithm And Parallelization Design

BGP is the most important inter-domain protocol in Internet. The convergence ofBGP directly affects the stability of Internet, which is an important indicator to theperformance of routing. It is of great significance to judge the convergence of BGPsince it can avoid BGP route flapping and improve the stability of the Internet.In order to solve the problem of BGP convergence, this paper analyses the threadmechanism, processing module and data structure of BGP. On this basis, BRFE(BGPRoute Flapping Elimination) algorithm is proposed. This algorithm has the ability ofjudging BGP convergence and avoiding BGP route flapping. BRFE algorithm addshistorical paths when route messages are received in order to detect route flappings andeliminate them. Therefore, this algorithm can calculate historical paths dynamically andeliminate route flapping. This algorithm, based on BGP route graph theory model,realizes the functions of choosing best routes, calculating routing table and routingindex table and judging route cycles. Afterwards, BRFE is realized in parallel andoptimized in performance in multicore architecture. Parallel BRFE algorithm is verifiedby three different test cases. Also, it achieves a superior speed-up ratio in multicorearchitecture.