Internet end-to-end routing paper available

The following paper:

  End-to-End Routing Behavior in the Internet

is now available from:

This paper corresponds to the talk I gave at the February NANOG meeting.
A slightly shorter version of this paper will appear in the proceedings
of SIGCOMM '96. Abstract appended.


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 [Chinoy93]. 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.