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.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P, Bloomfield, "Fourier Analysis of Time Series: An Introduction," John Wiley ~z Sons, New York. 1976.
	2	tt.-W. Braun, P. S. Ford and Y. Rekhter, "CIDR and the Evolution of the Internet,' SDSC Report GA- A21364, in Proceedings o/INET'93, Republished in ConneXions Sep 1993 (InterOp93 version).
	3	Bilal Chinoy, Dynamics of internet routing information, Conference proceedings on Communications architectures, protocols and applications, p.45-52, September 13-17, 1993, San Francisco, California, United States
	4	Deborah Estrin , Yakov Rekhter , Steven Hotz, Scalable inter-domain routing architecture, Conference proceedings on Communications architectures & protocols, p.40-52, August 17-20, 1992, Baltimore, Maryland, United States
	5	Sally Floyd , Van Jacobson, The synchronization of periodic routing messages, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.122-136, April 1994  [doi>10.1109/90.298431]
	6	R. Govindan , A. Reddy, An Analysis of Internet Inter-Domain Topology and Route Stability, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.850, April 09-11, 1997
	7	J. Honig, D. Katz, M. Mathis, Y. Rekhter, and J. Yu, `~Application of the Border Gateway Protocol in the Internet,' RFC-1164, June 1990.
	8	Internet Performance Measurement and Analysis project (IPMA), http://www.merit.edu/ipma.
	9	C. Labovitz, ~Multithreaded Routing Toolkit," Merit Technical Report, 1996.
	10	C. Labovitz, NANOG presentation, Washington, D.C., May 1996.
	11	Dave O'Leary, Cisco Systems, Inc. Private communication, January 1997.
	12	K. Lougheed and Y. Rekhter, "A Border Gateway Protocol (BGP),', RFC-1163 June 1990.
	13	B. Metcalf, "Predicting the internet's CatastropMc Collapse and Ghost Sites Galore in 1996,' Info World, December 4, 1995.
	14	Merit :Joint Technical Staff mail archives, http://www.merit.edu/mjts/msg00078.html.
	15	MFS Communications Mae-East Statistics Page, http://ww~.mf~t.com/MA~/~s~.st~ts.ht~.
	16	North American Network Operators Group, http://www.nanog.org.
	17	Vern Paxson, End-to-end routing behavior in the Internet, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.25-38, August 28-30, 1996, Palo Alto, California, United States
	18	Y. Rekhter, "Scalable Support for Multi-homed Multi- Provider Connectivity," NAN OG, Ann Arbor, MI. October 1996.
	19	Y. Rekhter and C. Topolcic, ``Exchanging Routing Information Across Provider Boundaries in the CIDR Environment,' RFG-1520. September 1993.
	20	Routing Arbiter web pages, http://www.ra.ne~;.
	21	K. Varadhan, R. Govindan, and D. Estrin, "Persistent Routing Oscillations in Inter-Domain Routing," USC/ISI, Available at the Routing Arbiter project's homepage at USC/ISI.
	22	C. Villamizer, R. Chandra, and R. Govindan, "draftietf-idr-route-dampen-00-previevf', Internet Engineering Task Force Draft, July 21, 1995.
	23	C. Villaxnizer, ``TCP Response Under Loss Conditions", NANOG Presentation, San Francisco, February 1997.

• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM   34, 12
  Ellen Francik ,  Susan Ehrlich Rudman ,  Donna Cooper ,  Stephen Levine
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski
  
  

• Applications, Technologies, Architectures, and Protocols for Computer Communication
  Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication
  
  1997 , Cannes, France