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:
- 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).
- 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