Stabilizing BGP, Safely
Philip Brighten Godfrey, Matthew Caesar, Ian Haken, Yaron Singer, Scott Shenker and Ion Stoica
Route instability is widely recognized as a major problem in the Internet. Core routers are barraged with millions of updates daily, leading to massive infrastructural costs and worsened data-plane performance. Route flap damping provides some protection against instability, but introduces pathologies and reduces availability.
With concerns about the scalability of the routing system prompting a renewed interest in stability, we believe it's time for a more principled approach to stabilizing Internet routing. This project takes a step towards that goal by quantitatively characterizing the tradeoffs between stability and two other important objectives: availability, and adherence to the network operator's preferences. We are bounding the performance of theoretically optimal strategies, and evaluating the performance of several implementable strategies. Our evaluation makes use of a large-scale simulation of the BGP protocol supplied with traces of measured inter-AS adjacency failures, as well as an experimental deployment of software routers.
Motivated by the principle that any improvements to stability should not come at the price of availability, we argue for an approach which we call Stable Route Selection (SRS). Our numerical evaluation shows that SRS preserves the high availability of BGP without flap damping, while obtaining stability similar to BGP with flap damping. These results indicate a promising approach to safely stabilizing BGP.