David Murrell

Measured Impact of Crooked Traceroute

Matthew Luckie, Amogh Dhamdhere, kc claffy, and David Murrell
Appears in: 
CCR January 2011

Data collected using traceroute-based algorithms underpins research into the Internet’s router-level topology, though it is possible to infer false links from this data. One source of false inference is the combination of per-flow load-balancing, in which more than one path is active from a given source to destination, and classic traceroute, which varies the UDP destination port number or ICMP checksum of successive probe packets, which can cause per-flow load-balancers to treat successive packets as distinct flows and forward them along different paths.

Public Review By: 
R. Teixeira

The research community has applied traceroute-style probing to measure Internet topologies for more than a decade with systems such as Skitter/Ark, Dimes, or Rocketfuel. These topologies are the basis of many other research efforts. Unfortunately, recent studies showed that classic traceroute can report false links when a router in the path performs load balancing. Although new probing techniques correct measurement artifacts under per-flow load balancing, we cannot correct topologies that have already been collected using classic traceroute and no prior work has studied how these errors affect inferred topologies. A natural question is then: how accurate are the topologies that we have all been using in our research?
This paper gives us a mixed answer. Measurement artifacts due to per-flow load balancing introduce only few errors when traceroute is used to discover a macroscopic topology (i.e., an Internet-wide topology), but they introduce significant errors when discovering the topology of an ISP. Such a sharp difference in the fraction of false links between the macroscopic topology and the ISP topology suggests that the error really depends on the set of vantage points and the networks traversed. This paper studies only one source of errors in inferred Internet topologies. As the authors point out: "the state of the art in Internet topology measurement is essentially and necessarily a set of hacks, which introduce many sources of possible errors". Hopefully, new studies will follow to understand the caveats of measured Internet topologies and to measure more accurate topologies. In the mean time, this paper confirms that we should be cautions when using inferred Internet topologies.

Syndicate content