Efficient algorithms for large-scale topology discovery

Benoit Donnet, Philippe Raoult, Timur Friedman, Mark Crovella

Mapping the Internet's "skeleton"—its routers and the links between them—is a massive undertaking. As we move from a few dedicated measurement servers to thousands of distributed "home" monitors, we face a major problem: if we aren't careful, our attempts to map the network will look exactly like a Distributed Denial of Service (DDoS) attack.

This paper by Donnet et al. introduces Doubletree, an algorithm designed to make large-scale topology discovery efficient, network-friendly, and scalable.

TL;DR

The authors propose Doubletree, an algorithm that exploits the tree-like structure of Internet routes to eliminate redundant network probing. By starting "traceroutes" in the middle of a path and using stopping rules, Doubletree reduces measurement traffic by approximately 70% while still discovering over 90% of the network's nodes and links.

What Problem Does This Paper Address?

Standard topology discovery relies on traceroute, a tool that sends packets with increasing Time-To-Live (TTL) values to identify every hop between a source and a destination. When scaled up to thousands of monitors, two types of massive redundancy emerge:

  1. Intra-monitor redundancy: A single monitor probing a million destinations will traverse the same routers near its own location over and over again (the "root" of its local tree).
  2. Inter-monitor redundancy: Multiple monitors probing the same destination will all traverse the same routers near that destination (the "root" of the destination's tree).

Without a way to coordinate, these systems waste bandwidth and risk triggering security alarms at target networks.

Methods

The core contribution is the Doubletree algorithm. Instead of starting at hop 1 and going to the end, Doubletree takes a "start in the middle" approach:

  • Midpoint Probing: A monitor starts probing at an intermediate hop distance $h$.
  • Backward Tracing (Intra-monitor): The monitor probes backward toward itself. It stops as soon as it hits an interface it has seen before. This exploits the fact that routes from a monitor look like a tree rooted at the monitor.
  • Forward Tracing (Inter-monitor): The monitor probes forward toward the destination. It stops if it encounters an (interface, destination) pair that has already been stored in a Global Stop Set. This exploits the fact that routes to a destination look like a tree rooted at the destination.
  • Bloom Filters: To share the "Global Stop Set" between distributed monitors without overwhelming the network with coordination traffic, the authors use Bloom filters—a space-efficient probabilistic data structure.

Datasets

The study evaluates the algorithm using real-world data from CAIDA’s skitter project.

  • Source: Data from August 1–3, 2004.
  • Scale: 24 monitors located globally (US, Canada, UK, France, Japan, etc.).
  • Scope: While the original set had 1 million IPv4 destinations, the authors used a randomly chosen subset of 50,000 destinations to keep computation manageable.

Key Insights and Ideas

  • The "Tree" Duality: The Internet's topology can be viewed as a collection of trees rooted at sources (outgoing) and trees rooted at destinations (incoming). Efficiency comes from recognizing that once you hit a "branch" you've already mapped, you can stop.
  • Redundancy is Location-Dependent: Intra-monitor redundancy is highest near the source, while inter-monitor redundancy is highest near the destination. Doubletree is the first algorithm to tackle both simultaneously.
  • The Power of $p$: The authors define a parameter $p$ (the probability of hitting a destination on the first probe). Tuning $p$ allows researchers to balance the "DDoS-like" load on destinations against the discovery of new internal nodes.
  • Bloom Filter "Serendipity": Surprisingly, using Bloom filters (which have a small false-positive rate) actually increased node and link coverage slightly. The authors suggest that false positives might act as a form of "random exploration," pushing the algorithm to find paths it might otherwise have skipped.

Key Results

  • Probe Reduction: Doubletree reduced the number of probes by 70% compared to classical "skitter-style" probing.
  • High Coverage: Despite the massive reduction in traffic, the algorithm maintained 90% to 98% coverage of nodes and links.
  • DDoS Mitigation: Inter-monitor redundancy on destinations was reduced by 84% at certain settings, significantly lowering the profile of the measurement system.
  • Communication Efficiency: Bloom filters provided a 6.4:1 compression ratio for sharing discovered paths between monitors, making coordination feasible for large-scale deployments.

Limitations and Future Work

  • Non-Tree Topologies: The algorithm assumes a tree-like structure. While generally true, the Internet contains loops, multi-path routing, and load balancers that can break this assumption and lead to missed links.
  • Monitor Coordination: The paper assumes a simplified scenario where monitors share data in a sequence. Real-world parallel coordination is more complex.
  • Clustering: The authors suggest future work should look into "clustering" monitors and destinations to further refine which monitors probe which parts of the network, potentially increasing efficiency even further.

Summary updated

Abstract

There is a growing interest in discovery of internet topology at the interface level. A new generation of highly distributed measurement systems is currently being deployed. Unfortunately, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner. In this paper we make two contributions toward that end. First, we show that standard topology discovery methods (e.g., skitter) are quite inefficient, repeatedly probing the same interfaces. This is a concern, because when scaled up, such methods will generate so much traffic that they will begin to resemble DDoS attacks. We measure two kinds of redundancy in probing (intra- and inter-monitor) and show that both kinds are important. We show that straightforward approaches to addressing these two kinds of redundancy must take opposite tacks, and are thus fundamentally in conflict. Our second contribution is to propose and evaluate Doubletree, an algorithm that reduces both types of redundancy simultaneously on routers and end systems. The key ideas are to exploit the tree-like structure of routes to and from a single point in order to guide when to stop probing, and to probe each path by starting near its midpoint. Our results show that Doubletree can reduce both types of measurement load on the network dramatically, while permitting discovery of nearly the same set of nodes and links.
BibTeX
@inproceedings{donnet2005efficient,
  author = {Benoit Donnet and Philippe Raoult and Timur Friedman and Mark Crovella},
  title = {{Efficient algorithms for large-scale topology discovery}},
  booktitle = {SIGMETRICS},
  year = {2005},
  doi = {10.1145/1064212.1064256},
}

Loading related content...

Figure