Delayed Internet routing convergence

By Craig Labovitz, Abha Ahuja, A. Bose, Farnam Jahanian. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2000

930 citations recorded by the source corpus.

This paper examines the latency in Internet path failure, failover and repair due to the convergence properties of inter-domain routing. Unlike switches in the public telephony network which exhibit failover on the order of milliseconds, our experimental measurements show that inter-domain routers in the packet switched Internet may take tens of minutes to reach a consistent view of the network topology after a fault. These delays stem from temporary routing table oscillations formed during the operation of the BGP path selection process on Internet backbone routers. During these periods of delayed convergence, we show that end-to-end Internet paths will experience intermittent loss of connectivity, as well as increased packet loss and latency. We present a two-year study of Internet routing convergence through the experimental instrumentation of key portions of the Internet infrastructure, including both passive data collection and fault-injection machines at major Internet exchange points. Based on data from the injection and measurement of several hundred thousand inter-domain routing faults, we describe several unexpected properties of convergence and show that the measured upper bound on Internet inter-domain routing convergence delay is an order of magnitude slower than previously thought. Our analysis also shows that the upper theoretic computational bound on the number of router states and control messages exchanged during the process of BGP convergence is factorial with respect to the number of autonomous systems in the Internet. Finally, we demonstrate that much of the observed convergence delay stems from specific router vendor implementation decisions and ambiguity in the BGP specification.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/3f1901441165f41e2aaed2b7e794a9f3099fc720

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Resilient overlay networks (2001, background): “Resilient Overlay Networks (RONs) are a remedy for some of these problems.”
Route flap damping exacerbates internet routing convergence (2002, background): “A second instance is the default setting of Hello timers in intra-domain routing protocols.”
Understanding BGP misconfiguration (2002, background): “In a continuation of that work they showed that convergence properties of path vector protocols such as BGP are much worse than previously assumed [24].”
BGP routing stability of popular destinations (2002, methodology): “timer that limits the rate of updates from an eBGP neighbor [6]; a popular vendor uses a default timer value of 30 seconds.”
Towards an accurate AS-level traceroute tool (2003, methodology): “In our study, we apply a 30-minute window before and after each traceroute to account for delays in BGP routing convergence [21].”
The impact of Internet policy and topology on delayed routing convergence (2001, methodology): “We assume that the reader is familiar with Internet routing concepts and terminology discussed in [5], [6], [1].”
Measuring ISP topologies with Rocketfuel (2004, background): “Topology influences the dynamics of routing protocols [3], [11], the scalability of multicast [19], the efficacy of denial-of-service tracing and response [12], [18], [23], [24], and other aspects of protocol performance [20].”
A Survey on Wireless Security: Technical Challenges, Recent Advances, and Future Trends (2015, methodology): “In the network layer, we also have different protocols, such as the IP, which was conceived for delivering data packets based on IP addresses, and the ICMP designed for sending error messages for indicating, for example, that a requested service is unavailable or that a network node could not be rea”
Detecting BGP configuration faults with static analysis (2005, background): “Failure-inducing configuration faults include invalid routes (including hijacked and leaked routes); contract violations [10]; unstable routes [20]; routing loops [7, 9]; and persistently oscillating”
Measuring ISP topologies with rocketfuel (2002, background): “Topology influences the dynamics of routing protocols [2, 10 ], the scalability of multicast [17], the efficacy of proposals for denial-of-service tracing and response [16, 11, 21, 22], and other aspects of protocol performance [18].”