Abstract
While traceroute is the bedrock of network diagnostics, it has a glaring blind spot: it only shows the path to a destination, not the path back. This paper introduces Reverse Traceroute, a distributed system that uses clever IP options and controlled source spoofing to map the return path from an arbitrary destination. By revealing the hidden asymmetries that often cause "unexplained" network latency, the system provides a vital tool for troubleshooting modern internet routing.
Introduction
In an ideal network, data travels symmetrically. In reality, internet routing is highly asymmetric due to "hot-potato" routing and complex peering policies. A packet might take a fast, direct route from New York to London, but the reply might loop through California. Standard traceroute works by incrementing the Time-to-Live (TTL) field, forcing routers to send back error messages. However, once a packet reaches its destination, the TTL is reset for the reply, leaving the sender blind to the reverse path. Reverse Traceroute addresses this "invisibility" by stitching together paths using distributed vantage points (VPs).
Methods
The system incrementally discovers the reverse path using three primary techniques:
1. The Atlas and Path Stitching
The system maintains a pre-computed "atlas" of paths from various global VPs back to the source. The goal is not to map the entire path from scratch but to find a single hop from the destination that eventually intersects with this known atlas.
As illustrated above, by identifying an intersection point (like router R4) between the destination's reverse path and a path already in the atlas (from V1), the system can "stitch" together a complete route back to the source (S).
2. IP Options (Record Route & Timestamp)
- Record Route (RR): This IP option asks routers to write their IP addresses directly into the packet header. While limited to 9 hops, it provides "ground truth" for the final stretch of the reverse path.
- Timestamp (TS): This allows the prober to ask specific routers if they saw the packet. By querying routers known to be "near" the destination based on topology maps, the system can confirm the next hop in the reverse direction.
3. Controlled Source Spoofing
To overcome the physical limitations of a prober's location, the system uses "controlled source spoofing." A VP sends a probe to the destination but spoofs the source address as the original requester.
When the destination (D) receives the spoofed packet, its reply—containing the Record Route data—is sent back to the original source (S) rather than the VP. This allows the system to effectively "place" a prober much closer to the destination than the source actually is.
Key Results
The researchers evaluated Reverse Traceroute using PlanetLab and iPlane data, validating results against ground-truth backbone data from Sprint.
- Accuracy: If one assumes path symmetry, only about 38% of hops are correctly identified. Reverse Traceroute increases this accuracy to 87% of hops in the median case.
- Coverage: The system can measure 95% of hops without needing to fall back on symmetry assumptions.
- Topology Discovery: The tool uncovered over 5,000 peering links that were invisible to standard mapping efforts because they only appear on reverse paths.
- Latency Precision: The authors estimated the latency of individual backbone links with an average error of less than one millisecond.
Limitations
The system's effectiveness is constrained by router compliance; approximately 16.6% of routers respond to pings but refuse to provide timestamps. Additionally, Reverse Traceroute is more "expensive" than a standard traceroute, requiring 2-3x more packets and taking significantly longer (a median of 41 seconds vs. 5 seconds) due to the coordination required between the controller and distributed VPs.
Conclusion
Reverse Traceroute transforms the "black box" of reverse routing into a measurable path. By leveraging limited source spoofing and a distributed atlas of routes, it provides network operators with the visibility needed to diagnose the asymmetries that define modern internet traffic.
Summary updated