A Stability-Oriented Approach to Improving BGP Convergence

Date Added: Jan 2011
Format: PDF

This paper shows that the elimination of fault-agnostic instability, the instability caused by fault-agnostic distributed control, substantially improves BGP convergence speed. To this end, the authors first classify BGP convergence instability into two categories: fault-agnostic instability and distribution-inherent instability; secondly, they prove the impossibility of eliminating all distribution-inherent instability in distributed routing protocols; thirdly, they design the Grapevine Border Gateway Protocol (G-BGP) to show that all fault-agnostic instability can be eliminated. G-BGP eliminates all fault-agnostic instability under different fault and routing policy scenarios by piggybacking onto BGP UPDATE messages fine-grained information about faults to the nodes affected by the faults, quickly resolving the uncertainty between link and node failure as well as the uncertainty of whether a node has changed route, and rejecting obsolete fault information.