CSE logo University of Washington Computer Science & Engineering
 Reverse Traceroute
  CSE Home   About Us    Search    Contact Info 

 Ethan Katz-Bassett
 David Choffnes
 Harsha Madhyastha
 Colin Scott
 Justine Sherry
 Tom Anderson
 Arvind Krishnamurthy
    Abstract

Traceroute is the most widely used Internet diagnostic tool today. Network operators use it to help identify routing failures, path inflation, and router misconfigurations. Researchers use it to map the Internet, predict performance, geolocate routers, and classify the performance of ISPs. However, traceroute has long had a fundamental limitation that affects all these applications: it does not provide reverse path information. Although various public traceroute servers across the Internet provide some visibility, no general method exists for determining a reverse path from an arbitrary destination, without control of that destination.

In this work, we address this longstanding limitation by building a reverse traceroute tool. Our tool provides the same information as traceroute, but for the reverse path, and it works in the same case as traceroute, when the user may lack control of the destination. Our approach combines a number of ideas: source spoofing, IP timestamp and record route options, and multiple vantage points. We deploy our system on PlanetLab and compare reverse traceroute paths with traceroutes issued from the destinations. In the median case our tool finds 87% of the hops seen in a directly measured traceroute along the same path. We then use our reverse traceroute system to study previously unmeasurable aspects of the Internet: we uncover thousands of peer-to-peer AS links invisible to current topology mapping efforts, and we present a case study of how a content provider could use our tool to troubleshoot poor path performance.

Demo

Try out the public demo of our system at revtr.cs.washington.edu.

Publications

  • Reverse Traceroute
    E. Katz-Bassett, H. Madhyastha, V. Adhikari, C. Scott, J. Sherry, P. van Wesep, A. Krishnamurthy, T. Anderson
    USENIX Symposium on Networked Systems Design & Implementation (NSDI), 2010. Paper, slides, and video available.
    Awarded Best Paper.

Talks

  • Reverse Traceroute
    E. Katz-Bassett.
    Réseaux IP Européens (RIPE) 58, May 2009.
  • How I Learned to Stop Worrying and Love to Spoof
    E. Katz-Bassett.
    ISMA 2009 AIMS - Workshop on Active Internet Measurements, February 2009.
  • Practical Reverse Traceroute
    E. Katz-Bassett.
    North American Network Operators Group (NANOG) 45, January 2009.
    Video and PDF slides available.
  • Measuring Reverse Paths
    E. Katz-Bassett.
    10th CAIDA-WIDE Workshop, August 2008.

Acknowledgements

Google, Cisco, and NSF partially funded this work. We are very appreciative of the support.


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to arvind]