Route Oscillations in I-BGP with Route Reflection. Anindya Basu (Bell Labs), Chih-Hao Luke Ong (Oxford University), April Rasala (MIT),  F.Bruce Shepherd and Gordon Wilfong (Bell Labs)

 

We study the route oscillation problem in the Internal Border Gateway Protocol (I-BGP) when route reflection is used.  We propose a formal model of I-BGP and use it to show that even deciding whether an I-BGP configuration with route reflection can converge is an NP-Complete problem. We then propose a modification to I-BGP and show that route reflection cannot cause the modified protocol to diverge. Moreover, we show that the modified protocol converges to the same stable routing configuration regardless of the order in which messages are sent or received.

Papers are provided as a service to all by the members of ACM SIGCOMM.

This paper is available in Adobe PDF format.