A Divergence Analysis in Autonomous Systems Using Full-Mesh iBGP

From a global point of view, the Internet consists of Autonomous Systems, exchanging reachability information by using BGP. In big ASs, the usage of scaling techniques as iBGP Route Reflection is necessary to reduce the information exchanged inside the system. However, as discussed in various studies, these techniques may lead to routing anomalies like suboptimal path selection, deflection, non-determinism, or oscillation. Especially an endless exchange of update messages and the resulting unstable behavior of the system, involved with oscillation, are extremely unwanted. Besides oscillation, also non-determinism may result in similar situations. In contrast to this, both non-determinism and oscillation were not observed in ASs using full-mesh iBGP. In this paper, it is proved that these routing anomalies cannot occur here. Understanding the conditions for the absence of these anomalies may be a first step to amalgamate the scalability advantages of iBGP Route Reflection and the stability of full-mesh iBGP.