URL: http://www.acm.org/sigcomm/sigcomm97/papers/p109.pdf
http://www.acm.org/sigcomm/sigcomm97/papers/p109.ps Entry Date: 2003-05-14 Abstract: This paper examines the network inter-domain routing information exchanged between backbone service providers at the major U.S. public Internet exchange points. Internet routing instability, or the rapid fluctuation of network reachability information, is an important problem currently facing the Internet engineering community. High levels of network instability can lead to packet loss, increased network latency and time to convergence. At the extreme, high levels of routing instability have lead to the loss of internal connectivity in wide-area, national networks. In this paper, we describe several unexpected trends in routing instability, and examine a number of anomalies and pathologies observed in the exchange of inter-domain routing information. The analysis in this paper is based on data collected from BGP routing messages generated by border routers at five of the Internet core's public exchange points during a nine month period. We show that the volume of these routing updates is several orders of magnitude more than expected and that the majority of this routing information is redundant, or pathological. Furthermore, our analysis reveals several unexpected trends and ill-behaved systematic properties in Internet routing. We finally posit a number of explanations for these anomalies and evaluate their potential impact on the Internet infrastructure. Datasets: BGP updates collected over 9 months at 5 U.S. exchange points: AADS, Mae-East, Mae-West, PacBell, and Sprint Results: Quoting from paper with added details:

• The number of BGP updates exchanged per day in the Internet core is one or more orders of magnitude larger than expected.
  • 3-6 million updates per day; one peak at 30 million or more updates
  • only 45,000 prefixes in default-free backbone tables
• Routing information is dominated by pathological, or redundant updates, which may not reflect changes in routing policy or topology.
  • (WWDup) withdrawals of prefixes that have not been announced; caused by stateless BGP implementations
  • (AADup) announcements of prefixes with no change in path attributes
  • (WADup) route flapping: withdrawals followed by announcements with same path attributes
• Instability and redundant updates exhibit a specific periodicity of 30 and 60 seconds.
  • perhaps due to unjittered timers, self-synchronization, interactions between IGP and BGP, or CSU link oscillation
• Instability and redundant updates show a surprising correlation to network usage and exhibit corresponding daily and weekly cyclic trends.
• Instability is not dominated by a small set of autonomous systems or routes.
• Instability and redundant updates exhibit both strong high and low frequency components. Much of the high frequency instability is pathological.
• Discounting policy fluctuation and pathological behavior, there remains a significant level of Internet forwarding instability.
• This work has led to specific architectural and protocol implementation changes in commercial Internet routers through our collaboration with vendors.

References: The most significant pathology--redundant withdrawals--was corrected in router implementations in 1997-1998, so some of the observations are merely of historical interest today. The paper "Origins of Internet Routing Instability" by the same authors is a followup to this paper.