Route Oscillations in I-BGP with Route Reflection

We study the route oscillation problem~cite{MGW00,Cis00} in the Internal Border Gateway Protocol (I-BGP)~cite{RL95} 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. Finally, we 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.