End-to-end routing behavior in the internet

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

End-to-end routing behavior in the internet

Full text

Pdf (544 KB)

Source

ACM SIGCOMM Computer Communication Review archive
Volume 36 , Issue 5 (October 2006) table of contents

COLUMN: Editorial zone table of contents

Pages: 41 - 56

Year of Publication: 2006

ISSN:0146-4833

Author

Vern Paxson

University of California, Berkeley and Lawrence Berkeley National Laboratory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 61, Downloads (12 Months): 287, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1163593.1163602 What is a DOI?

ABSTRACT

The large-scale behavior of routing in the Internet has gone virtually without any formal study, the exception being Chinoy's analysis of the dynamics of Internet routing information [Ch93]. We report on an analysis of 40,000 end-to-end route measurements conducted using repeated "traceroutes" between 37 Internet sites. We analyze the routing behavior for pathological conditions, routing stability, and routing symmetry. For pathologies, we characterize the prevalence of routing loops, erroneous routing, infrastructure failures, and temporary outages. We find that the likelihood of encountering a major routing pathology more than doubled between the end of 1994 and the end of 1995, rising from 1.5% to 3.4%. For routing stability, we define two separate types of stability, "prevalence," meaning the overall likelihood that a particular route is encountered, and "persistence," the likelihood that a route remains unchanged over a long period of time. We find that Internet paths are heavily dominated by a single prevalent route, but that the time periods over which routes persist show wide variation, ranging from seconds up to days. About 2/3's of the Internet paths had routes persisting for either days or weeks. For routing symmetry, we look at the likelihood that a path through the Internet visits at least one different city in the two directions. At the end of 1995, this was the case half the time, and at least one different autonomous system was visited 30% of the time.

REFERENCES

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	F. Baker, Requirements for IP Version 4 Routers, RFC Editor, 1995
	2	C. Baransel, W. Dobosiewicz, and P. Gburzynski, "Routing in Multihop Packet Switching Networks: Gb/s Challenge," IEEE Network, 9(3), pp. 38--61, May/June 1995.
	3	Ivars Bilinskis , A. K. Mikelson, Randomized Signal Processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	4	Jean-Chrysotome Bolot, End-to-end packet delay and loss behavior in the internet, Conference proceedings on Communications architectures, protocols and applications, p.289-298, September 13-17, 1993, San Francisco, California, United States
	5	R. Braden , D. Clark , S. Shenker, Integrated Services in the Internet Architecture: an Overview, RFC Editor, 1994
	6	L. Breslau , D. Estrin, Design of inter-administrative domain routing protocols, Proceedings of the ACM symposium on Communications architectures & protocols, p.231-241, September 26-28, 1990, Philadelphia, Pennsylvania, United States
	7	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
	8	K. Claffy, H-W. Braun and G. Polyzos, "A Parameterizable Methodology for Internet Traffic Flow Profiling," IEEE JSAC, 13(8), pp. 1481--1494 October 1995.
	9	K. Claffy, G. Polyzos and H.-W. Braun, "Measurement Considerations for Assessing Unidirectional Latencies," Internet-working: Research and Experience, 4 (3), pp. 121--132, September 1993.
	10	Stephen E. Deering , David R. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.85-110, May 1990 [doi>10.1145/78952.78953]
	11	L. Delgrossi , L. Berger, Internet Stream Protocol Version 2 (ST2) Protocol Specification - Version ST2+, RFC Editor, 1995
	12	Sean Doran, "Route Flapping," with notes by Stan Barber, http://www.merit.edu/routing.arbiter/NANOG/2.95.NANOG.notes/route-flapping.html.
	13	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
	14	Domenico Ferrari , Anindo Banerjea , Hui Zhang, Network support for multimedia: a discussion of the Tenet approach, Computer Networks and ISDN Systems, v.26 n.10, p.1267-1280, July 1994 [doi>10.1016/0169-7552(94)90101-5]
	15	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]
	16	S. Hares , D. Katz, Administrative Domains and Routing Domains: A model for routing in the Internet, RFC Editor, 1989
	17	Christian Huitema, Routing in the Internet, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
	18	V. Jacobson, traceroute, ftp://ftp.ee.lbl.gov/traceroute.tar.Z, 1989.
	19	A. Khanna , J. Zinky, The revised ARPANET routing metric, Symposium proceedings on Communications architectures & protocols, p.45-56, September 25-27, 1989, Austin, Texas, United States
	20	C. Labovitz, private communication, May 1996.
	21	M. Little, Goals and functional requirements for inter-autonomous system routing, RFC Editor, 1989
	22	M. Lottor, ftp://nic.merit.edu/nsfnet/statistics; October, 1995.
	23	J. McQuillan, G. Falk and I. Richer, "A Review of the Development and Performance of the ARPANET Routing Algorithm," IEEE Transactions on Communications, 26(12), pp. 1802--1811, December 1978.
	24	J. McQuillan, I. Richer and E. Rosen, "The New Routing Algorithm for the ARPANET," IEEE Transactions on Communications, 28(5), pp. 711--719, May 1980.
	25	Merit Network, Inc., ftp://nic.merit.edu/nsfnet/statistics/history.nets; May, 1995.
	26	Merit Network, Inc., http://nic.merit.edu/routing.arbiter/RA/statistics/flap.html.
	27	D. Mills, Network Time Protocol (Version 3) Specification, Implementation, RFC Editor, 1992
	28	A. Mukherjee, "On the Dynamics and Significance of Low Frequency Components of Internet Load," Internetworking: Research and Experience, Vol. 5, pp. 163--205, December 1994.
	29	Vern Paxson, Empirically derived analytic models of wide-area TCP connections, IEEE/ACM Transactions on Networking (TON), v.2 n.4, p.316-336, Aug. 1994 [doi>10.1109/90.330413]
	30	Vern Edward Paxson, Measurements and analysis of end-to-end Internet dynamics, University of California at Berkeley, Berkeley, CA, 1998
	31	R. Perlman , G. Varghese, Pitfalls in the design of distributed routing algorithms, Symposium proceedings on Communications architectures and protocols, p.43-54, August 16-18, 1988, Stanford, California, United States
	32	R. Perlman, "A comparison between two routing protocols: OSPF and IS-IS," IEEE Network, 5(5), pp. 18--24, September 1991.
	33	Radia Perlman, Interconnections: bridges and routers, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	34	Y. Rekhter and B. Chinoy, "Injecting Inter-autonomous System Routes into Intra-autonomous System Routing: a Performance Analysis," Internetworking: Research and Experience, Vol.3, pp. 189--202, 1992.
	35	Y. Rekhter, "Inter-Domain Routing: EGP, BGP, and IDRP," in {St95}.
	36	Y. Rekhter , T. Li, A Border Gateway Protocol 4 (BGP-4), RFC Editor, 1995
	37	Y. Rekhter , P. Gross, Application of the Border Gateway Protocol in the Internet, RFC Editor, 1995
	38	E. Rosen, "Exterior Gateway Protocol (EGP)," RFC 896, Net-work Information Center, SRI International, Menlo Park, CA, October 1982.
	39	S. Ross, Stochastic Processes, John Wiley & Sons, 1983.
	40	D. Sanghi, A.K. Agrawal, Ò. Gudmundsson, and B.N. Jain, "Experimental Assessment of End-to-end Behavior on Internet," Proceedings of INFOCOM'93, San Francisco, March, 1993.
	41	M. Schwartz and T. Stern, "Routing Techniques Used in Computer Communication Networks," IEEE Transactions on Com-munications, 28(4), pp. 539--552, April 1980.
	42	Deepinder Sidhu , Tayang Fu , Shukri Abdallah , Raj Nair , Rob Coltun, Open shortest path first (OSPF) routing protocol simulation, Conference proceedings on Communications architectures, protocols and applications, p.53-62, September 13-17, 1993, San Francisco, California, United States
	43	Martha Steenstrup, Routing in communications networks, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
	44	W. Richard Stevens, TCP/IP illustrated (vol. 1): the protocols, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
	45	P. Traina, Experience with the BGP-4 protocol, RFC Editor, 1995
	46	P. Traina, BGP-4 Protocol Analysis, RFC Editor, 1995
	47	R. Wolff, "Poisson Arrivals See Time Averages," Operations Research, 30(2), pp. 223--231, 1982.
	48	W. Zaumen and J.J. Garcia-Luna Aceves, "Dynamics of Link-state and Loop-free Distance-vector Routing Algorithms," Internetworking: Research and Experience, Vol. 3, pp. 161--188, 1992.
	49	L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, "RSVP: A New Resource ReSerVation Protocol," IEEE Net-work, 7(5), pp. 8--18, September 1993.