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. We then show how to enable efficient communication between monitors through the use of Bloom filters.
Introduction: The Challenge of Large-Scale Mapping
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. 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 many destinations repeatedly traverses the same routers near its own location.
- Inter-monitor redundancy: Multiple monitors probing the same destination all traverse the same routers near that destination.
Without a way to coordinate, these systems waste bandwidth and risk triggering security alarms at target networks.
The Doubletree Algorithm
The core contribution of this work is the Doubletree algorithm. Instead of starting at hop 1 and progressing linearly, Doubletree takes a "start in the middle" approach to exploit the tree-like structure of Internet routes.
Midpoint Probing and Stopping Rules
A monitor starts probing at an intermediate hop distance $h$. From this midpoint, it performs two types of tracing:
- Backward Tracing (Intra-monitor): The monitor probes backward toward itself, stopping as soon as it hits a previously seen interface. This exploits the fact that routes from a monitor look like a tree rooted at the source.
- Forward Tracing (Inter-monitor): The monitor probes forward toward the destination, stopping if it encounters an (interface, destination) pair already stored in a Global Stop Set. This exploits the fact that routes to a destination look like a tree rooted at the target.
To share the "Global Stop Set" efficiently between distributed monitors, the authors utilize Bloom filters, achieving a 6.4:1 compression ratio for coordination traffic.
Experimental Evaluation
The study evaluates the algorithm using real-world data from CAIDA’s skitter project, involving 24 global monitors and a subset of 50,000 destinations.
Key Results
- Probe Reduction: Doubletree reduced the number of probes by 70% compared to classical probing methods.
- High Coverage: Despite the 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.
- The Power of $p$: Tuning the parameter $p$ (the probability of hitting a destination on the first probe) allows researchers to balance the load on destinations against the discovery of new internal nodes.
Conclusion
Doubletree demonstrates that exploiting the "tree duality" of the Internet allows for highly efficient topology discovery. While the algorithm assumes a tree-like structure, it provides a robust framework for scalable, network-friendly mapping. Future work may address non-tree topologies, such as those involving load balancers, and explore clustering monitors to further refine probing efficiency.
Summary updated