CS268 Reading Review

End-to-End Routing Behavior in the Internet

Vern Paxson
Review by Feng Zhou
2/16/2003

The problem: How the routing protocols of Internet behave in the real world is an important problem to study. This paper presents results about the prevalence of pathology, routing stability and routing symmetry measured using end-to-end techniques.

Key points:

  1. The basic methodology is to treat Internet routing as a complete black box. End-to-end "traceroutes" between 37 participating sites were collected and analyzed. Although not perfect, this may well be the most plausible way of measuring routing behavior on a large scale for most researchers. The opposite approach of using router traces is not scalable, given the distributed nature of Internet administration. Thus the key point of good Internet measurement seems to be the devising of a good end-to-end measurement tool that exploiting the features of existing infrastrure and protocols. Traceroute is a ubiquitous tool to do routing analysis that suits the needs here.
  2. It seems to me that the hosts measured do not have to be cooperative to each other. Maybe one can do the routing measurement with a few controlled hosts talking to many other uncontrolled hosts in the Internet. With this, we can possibly collect data for many more routes than in the paper. Symmetry may be hard to measure. But it can yield much more information about routing pathologies and stability.
  3. Signficant results of the paper includes: likelihood of routing pathology within 1.5%-3.4%, 2/3 of paths with routes persisting for days or weeks and more than 50% of paths are assymmetry. The overall routing behavior of the Internet has great implications for systems and applications, e.g. overlay networks. It will be very interesting to see whether today's Internet, 7 years from when the paper was written, still has the same routing properties. All three aspects of routing behavior are important for systems and applications trying to deliver reliable services.