|
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.
|