Stable, Loop-Free, Multi-Path Inter-Domain Routing Using BGP

We introduce the concept of a routing etiquette as the set consisting of the information maintained by routers, local operations that can be carried out on such information, and the information that routers share with one another to reach stable routes using local private policies for path selection. OPERA is presented as one such etiquette. Sufficient conditions for stable and loop-free routing based on OPERA are proven. Based on these results, BGP is proven to be inherently unstable and prone to looping, and the policy mechanisms of BGP are modified slightly to attain OPERA-based BGP (OBGP). OBGP is the first loop-free inter-domain multi-path routing solution based on BGP. OBGP is proven to be stable and loop-free. Well-known examples of systems in which BGP does not converge are used to show the benefits of OBGP.