2002 · 16 citations · 14 references
ComputingComputer ScienceComputer NetworksDigital CommunicationFormal MethodsInternet RoutingNetwork ArchitectureNetwork ProtocolsRoutingRouting AlgorithmsRouting ProtocolsBgp Route ControlBorder Gateway ProtocolInterdomain RoutingNetwork OscillationsNp-complete ProblemsNp-completenessRoute ConvergenceRouting Stability
We study the route oscillation problem [16, 19] in the Internal Border Gateway Protocol (I-BGP)[18] 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. We then 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.
14
Craig Labovitz, G. Robert Malan, Farnam Jahanian · 1997 · 363 citations
The impact of Internet policy and topology on delayed routing convergence
Craig Labovitz, Abha Ahuja, R. Wattenhofer et al. · 2002 · 255 citations
Delayed Internet routing convergence
Craig Labovitz, Abha Ahuja, Abhijit Bose et al. · 2000 · 217 citations · Full text
Stable Internet routing without global coordination
Lixin Gao, Jennifer Rexford · 2000 · 199 citations · Full text