Paper review: End-to-End Routing Behavior in the Internet

Reviewer: Kenneth Chin

This paper is not attempting to solve any problem. Instead, through real analysis, it provides sufficient and convincing findings that reveals the routing issues of the Internet in 1995 in a quantitative manner.

Basically, there are three issues the paper is trying to discover quantitatively: 1) Routing pathologies; 2) Routing stability; 3) Routing symmetry. For routing pathologies, it characterizes the prevalence of routing loops (namely forwarding loop, information loop adn traceroute loop), erroneous routing, infrastructure failures, and temporary outages. For routing stability, it means 2 things: 1) Prevalence - the overall likelihood that a particular route is encountered; 2) Persistence - the likelihood that a route remains unchanged over a long period of time. For routing symmetry, it menas the likelihood that a path through the Internet visits at least on different city in the two directions.

As for the experimental settings, 37 Internet hosts were participating in the measurements. They essentially composed the source-destination pairs. Although only 37 hosts were involved, it was aruged that the routes between those 37 hosts were good enough to capture the essence of the Internet routing scenario in 1995. It is because only a fraction of autonomous systems (AS) are used heavily and those 37 hosts were believed to exploit some AS's heavily. In terms of software, traceroute was used to measure the single-trip delay and the round-trip delay. Each host had a network probe daemon (NPD) which was communicating with a controller, npd_control, in a local server. The following diagram depicts the a particular experimental setting:

The main idea of this paper is to identify quantitatively the routing behavior in the Internet. The finiding shows that the likelihood of encountering a major routing pathology between the end of 1994 and the end of 1995 is more than doubled, rising form 1.5% to 3.4%. It also shows 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. Moreover, about 2/3's of the Internet paths had routes persisting for either days or weeks. Furthermore, 50% of the Internet paths are asymmetric.

The findings undoubtedly shows that the network was unstable in 1995. Unstability is undesirable because it makes network unpredictable in the sense that the network states shared amount routers do not reflect the true network traffic. Obviously, the measurement was done between 1994 and 1995, so it is believed that the routing behavior is exacerbated nowadays. Network unstability issue is prevalent and needs to be addressed immediately.

I would grade this paper with a 3. The measurement is really helpful to roughly understand the routing behavior of the Internet.