Achieving Stable iBGP with Only One Add-Path

Border Gateway Protocol (BGP) has been and will still be the de-facto standard for inter-domain routing in the Internet. However, the problem of routing oscillations in BGP has not been well addressed, which can introduce lots of unnecessary routing updates and severely degrade network performance. In particular, existing studies need a great effort to be deployed or introduce a large overhead. In this paper, we propose to first detect a routing oscillation quickly after the oscillation happened, and then, we eliminate the routing oscillation by disseminating only one additional path (Add-path). Based on analysis of BGP updates in the routers where oscillations have already happened, we present a general method to detect a routing oscillation within a couple of routing replacements. Then, we show that one more Add-path is enough to stop the oscillation. We propose the Minimal Add-paths BGP (MA-BGP) approach, develop algorithms, and prove that MA-BGP can guarantee stable iBGP by a classical model that captures the underlying semantics of any path vector protocol including BGP. The simulation results show the effectiveness and efficiency of our approach.