2003 · 135 citations · 11 references
ComputingAutonomous SystemsComputer ScienceAlgorithmsComputer NetworksFormal MethodsInternet RoutingNetwork ArchitectureNetwork ProtocolsRoutingRouting AlgorithmsRouting ProtocolsAutonomous System RoutingBgp Route ControlBorder Gateway ProtocolInterdomain RoutingPath ComputationPolicy-based RoutingRouting PoliciesRouting Stability
The multi exit discriminator (MED) attribute of the border gateway protocol (BGP) is widely used to implement "cold potato routing" between autonomous systems. However, the use of MED in practice has led to BGP persistent oscillation. The MED oscillation problem has been described with example configurations and complicated, step-by-step evaluation of dynamic route computations performed at multiple routers. Our work presents the first rigorous analysis of the MED oscillation problem. We employ the stable paths problem (SPP) formalism that allows a static analysis of the interaction of routing policies. We give a formal definition of MED induced routing anomalies (MIRA) and show that, in general, they can span multiple autonomous systems. However, if we assume that the BGP configurations between autonomous systems follows a common model based on customer/provider and peer/peer relationships, then we show that the scope of any MIRA is always contained within a single autonomous system. Contrary to widely held assumptions, we show that a MIRA can occur even in a fully meshed IBGP configuration. We also show that a stable BGP routing may actually violate the stated semantics of the MED attribute.
11
Stable Internet routing without global coordination
Lixin Gao, Jennifer Rexford · 2000 · 199 citations · Full text
On the correctness of IBGP configuration
Timothy G. Griffin, Gordon Wilfong · 2002 · 188 citations
Inherently safe backup routing with BGP
Lixin Gao, Timothy G. Griffin, Jennifer Rexford · 2002 · 175 citations · Full text