6. Topology
Evaluation of a Large-Scale Topology Discovery Algorithm
Benoit Donnet1, 2, Bradley Huffaker2, Timur Friedman1 and kc claffy2
| (1) |
Université Pierre & Marie Curie – Laboratoire LiP6/CNRS, UMR 7606, France |
| (2) |
Caida – San Diego Supercomputer Center, USA |
Abstract
In the past few years, the network measurement community has been interested in the problem of internet topology discovery
using a large number (hundreds or thousands) of measurement monitors. The standard way to obtain information about the internet
topology is to use the traceroute tool from a small number of monitors. Recent papers have made the case that increasing the
number of monitors will give a more accurate view of the topology. However, scaling up the number of monitors is not a trivial
process. Duplication of effort close to the monitors wastes time by reexploring well-known parts of the network, and close
to destinations might appear to be a distributed denial-of-service (DDoS) attack as the probes converge from a set of sources
towards a given destination. In prior work, authors of this paper proposed Doubletree, an algorithm for cooperative topology
discovery, that reduces the load on the network, i.e., router IP interfaces and end-hosts, while discovering almost as many
nodes and links as standard approaches based on traceroute. This paper presents our open-source and freely downloadable implementation
of Doubletree in a tool we call traceroute@home. We evaluate the performance of our implementation on the PlanetLab testbed
and discuss a large-scale monitoring infrastructure that could benefit of Doubletree.