Stability is one of the key challenges of BGP, the de facto inter-domain routing protocol in today's Internet. BGP's slow convergence and recovery in the face of routing failures and policy changes can lead to poor data plane performance including significant periods of packet loss.

In this paper, we present stable route selection (SRS), a simple approach to improve BGP stability, by directly incorporating route stability as a factor in the route selection process. Through extensive simulations in a realistic environment, we show that the mean rate at which routes change can be reduced by a factor of 4.8, while preserving local preferences based on ISP business relationships, and limiting the increase of the path length to less than 15%. Moreover, this approach can be deployed easily, as it requires no protocol changes or coordination among ISPs. A single ISP can unilaterally implement SRS and obtain a significant improvement in stability, with benefits increasing as more ISPs participate.

This is joint work with Matthew Caesar, Scott Shenker, Ion Stoica, and Ian Haken.