Reverse traceroute

Ethan Katz-Bassett, Harsha V. Madhyastha, Vijay Kumar Adhikari, Colin Scott, Justine Sherry, Peter van Wesep, Thomas E. Anderson, Arvind KrishnamurthyNsdi 2010

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.

Stitching the reverse path using an atlas of known routes from vantage points.

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.

Controlled source spoofing to record the reverse path.

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

BibTeX
@inproceedings{katzbassett2010reverse,
  author = {Ethan Katz-Bassett and Harsha V. Madhyastha and Vijay Kumar Adhikari and Colin Scott and Justine Sherry and Peter van Wesep and Thomas E. Anderson and Arvind Krishnamurthy},
  title = {{Reverse traceroute}},
  booktitle = {Nsdi},
  year = {2010},
}
Figure