Bibliography Details

V. Paxson, "End-to-end routing behavior in the Internet", IEEE/ACM Transactions on Networking, vol. 5, no. 5, pp. 601-615, 1997.

End-to-end routing behavior in the Internet
Authors:	V. Paxson
Published:	IEEE/ACM Transactions on Networking, 1997
URL:	ftp://ftp.ee.lbl.gov/papers/vp-routing-TON.ps.gz http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.7351
Entry Date:	2003-05-15
Abstract:	The large-scale behavior of routing in the Internet has gone virtually without any formal study, the exceptions being Chinoy's analysis of the dynamics of Internet routing information [Ch93], and recent work, similar in spirit, by Labovitz, Malan and Jahanian [LMJ97]. 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, rout-ing stability, and routing symmetry. For pathologies, we character-ize the prevalence of routing loops, erroneous routing, infrastruc-ture failures, and temporary outages. We find that the likelihood of encountering a major routing pathology more than doubled be-tween the end of 1994 and the end of 1995, rising from 1.5% to 3.3%. For routing stability, we define two separate types of stabil-ity, "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 In-ternet paths are heavily dominated by a single prevalent route, but that the time periods over which routes persist show wide varia-tion, 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.
Datasets:	traceroute paths between hosts running the "network probe daemon" (NPD); 37 participating hosts in 34 stub networks (most are in U.S.) exponentially distributed measurement intervals main dataset (D2) collected Nov 3 to Dec 21, 1995: 60% with mean inter-measurement interval of 2 hours; 40% with mean interval of 2.75 days usually collected paths in both directions for each pairing of hosts
Results:	routing loops in traceroute paths (that is, observe same sequence of routers at least three times): very few occurrences, but some lasted more than half a day can be geographically and temporally clustered one instance of "erroneous routing," a circuitous path that is clearly wrong ...