The Internet is a composition of ASes (Autonomous Systems), BGP (Border Gateway Protocol) is the routing protocol that is responsible of exchanging routes between these ASes. It operates in two modes: eBGP (External BGP) and iBGP (Internal BGP). EBGP exchanges routing information between ASes, while iBGP propagates that information within the AS. IBGP node has not the ability to reflect routes. Therefore, each internal node should have iBGP sessions with all ASBRs (Autonomous System Border Routers). BGP route reflection was widely employed as an alternative to full mesh solution to reduce the needed number of iBGP sessions and, in turn, increase the scalability inside the AS. Under particular configuration, BGP scaling mechanism defined in route reflection mechanism introduces persistent route oscillation, forwarding loops, and non-optimal egress nodes. We propose the PC-iBGP (Partial Complete iBGP) as an alternative to the route reflection approach. PC- iBGP nodes have the ability of reflecting routes. It eliminates the use of clusters and establishes iBGP sessions only between single hop neighbors. We prove that it holds sufficient correctness conditions as well as its robustness against failures, asymmetric path problem, and MED (Multi Exit Discriminator) induced oscillations.

The Internet is a composition of ASes (Autonomous Systems), BGP (Border Gateway Protocol) is the routing protocol that is responsible of exchanging routes between these ASes. It operates in two modes: External BGP (eBGP) and Internal BGP (iBGP). EBGP exchanges routing information between ASes, while iBGP propagates that information within the AS. BGP Full Mesh Solution (FMS) is based on that all the ASBRs (Autonomous System Border Routers) should be fully meshed and each internal node should have an iBGP session with all of them. This was because an iBGP node does not have the ability to reflect routes. BGP route reflection was widely employed as an alternative to full mesh to reduce the needed number of iBGP sessions and, in turn, increase the scalability inside the AS. Under particular configuration, it introduces persistent route oscillation, forwarding loops, and non-optimal egress nodes. Skeleton is an alternative to route reflection that overcomes these routing anomalies. Skeleton is a subgraph of the physical graph with the same set of nodes, its edges are the iBGP sessions between the nodes. All Skeleton nodes have the ability of reflecting routes. Skeleton eliminates the use of clusters and establishes iBGP sessions only between single hop neighbors. We prove that it holds the sufficient correctness conditions as well as its robustness against MED induced oscillations. We evaluate it on five real world topologies and find that the number of iBGP sessions has a linear relationship with the number of ASBRs, where in FMS this relationship is quadratic.