URL: ftp://ftp.research.microsoft.com/pub/tr/tr-2000-08.ps
http://www.acm.org/sigcomm/sigcomm2000/conf/abstract/5-2.htm Entry Date: 2002-11-4 Abstract: 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, we show that inter-domain routers in the packet switched Internet may take several minutes to reach a consistent view of the network topology after a fault. These delays stem from temporary routing table oscillations formed during operation of the BGP path selection process on Internet backbone routers. During these periods of delayed convergence, 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 computational bound on the number of router states and control messages exchanged during the process of BGP convergence is exponential with respect to the number of autonomous systems on the Internet. Finally, we demonstrate that much of the observed convergence delay stems from both specific router vendor implementation decisions, as well as ambiguity in the BGP specification. Experiments: Over a two year period the authors injected faults at major Internet exchange points, and performed passive measurements. Results:

• The authors examine the latency in Internet path failure, failover and repair due to the convergence properties of inter-domain routing.
• The delay in Internet inter-domain path failovers averages three minutes, and some percentage of failovers trigger routing table oscillations lasting up to fifteen minutes. The upper bound on delay is an order of magnitude slower than previously thought.
• The theoretical upper computational bound on the number of router states and control messages during BGP convergence is exponential in the number of autonomous systems in the Internet.
• The theoretical lower bound on delay and number of states of BGP convergence is linear in the number of autonomous systems in the Internet. The authors suggest changes that would make the time complexity a constant (30 seconds).
• Internet path failover affects end-to-end performance - measured packet loss grows by a factor of 30 and latency by a factor of four during path restoral.
• Much of the observed convergence delay stems from router vendor implementation decisions and BGP specification ambiguity.

References:

• Complements:
  • T.G. Griffin, F. B. Shepherd, and G. Wilfong, "Policy disputes in path-vector protocols," in Proc. International Conference on Network Protocols, November 1999.
  • K. Varadhan, R. Govindan, and D. Estrin. Persistent route oscillations in inter-domain routing. Technical Report 96-631, USC/ISI, February 1996.
• Explains observations in:
  • C. Labovitz, G. R. Malan, and F. Jahanian, "Origins of pathological Internet routing instability," in Proc. IEEE INFOCOM, March 1999.
  • V. Paxson, "End-to-end Internet packet dynamics," in Proc. ACM SIGCOMM, 1997.
• Other references:
  • C. Labovitz, A. Ahuja, and F. Jahanian, "Experimental study of Internet stability and wide-area network failures," in Proc. International Symposium on Fault-Tolerant Computing, June 1999.
  • C. Labovitz, G. R. Malan, and F. Jahanian, "Internet routing instability," IEEE/ACM Transactions on Networking, August 1997.