Reverse Traceroute

Ethan Katz-Bassett ethan at cs.washington.edu
Mon Feb 27 04:51:20 UTC 2023


Chris, thanks for mentioning me/our project! Rolf, thanks for pointing to our
recent 2nd reverse traceroute paper
<https://hal.science/hal-03788618v1/file/internet-scale-revtr.pdf>!


Our recent paper addressed what we saw as the major limitations of my
original 1st reverse traceroute paper
<http://www.columbia.edu/~ebk2141/papers/reverse_traceroute-nsdi10.pdf>
that Chris linked (accuracy and scalability). We intend our system to be an
open tool for the community, and we are currently testing it with outside
users. It can potentially measure paths to you from *any* responsive host
on the Internet, without requiring access/changes/new support at the host
or routers along the path (more details below). If you want to try out our
tool during this testing phase, please email us at revtr at ccs.neu.edu

I'll describe our project a bit, including some of the similarities and
differences between our project and Rolf's. I'll call ours revtr-2.0, since
that's what we call it in the paper, and I'll call Rolf's revtr-lg, since
it is somewhat akin to a Looking Glass server.

The goal in both is the same: the user u wants to measure the path (IP
addresses of routers, RTTs per hop) from a remote host h to u, without
direct control of h.

revtr-2.0's approach relies on the rarely used (but actually widely
supported) IP Record Route option, coupled with some measurement tricks. In
my understanding, revtr-lg proposes to add a new ICMP type.

Both approaches rely on a set of distributed vantage points running an
implementation of their particular reverse traceroute code, but the way
they use the vantage points is very different, and that leads to the main
differences between the approaches. Our current tool has vantage points at
150 sites around the world, so I'll use that number as an example for
discussion.

COVERAGE

- revtr-lg allows a user u to contact a vantage point to request a
traceroute from the vantage point to u, so it measures from sites that have
opted to run the revtr-lg software. So, with 150 sites, revtr-lg would be
able to measure 150 paths to u.

- revtr-2.0 uses the vantage points to issue various measurements that
combine to measure the route to u from any host h the user requests -- h
need not be part of the system and need not run any special software. We
were able to use revtr-2.0 and its 150 vantage points to measure paths from
hosts in 39,544 ASes. (According to APNIC estimates
<https://stats.labs.apnic.net/aspop>, these ASes host 92.6% of Internet
users).

- If you want to use revtr-2.0 to measure paths to you (from whichever
hosts you request), you need to run our client code on a public IP address.
It will contact our system and use our vantage points to measure routes to
you. If you want to try out our tool, please email us at revtr at ccs.neu.edu

- Our vantage points currently support running a few tens of millions of
reverse traceroutes per day. We hope to improve the scalability/throughput
going forward.

Just as some hosts are configured not to respond to ping, some hosts do not
respond to our measurements. We found that 75% of hosts that respond to
ping also respond to our measurements. Of responsive hosts, 63% are within
range of our current vantage points. Going forward, we would be able to
measure from more than the 39,544 ASes if we add more vantage points in
strategic locations where we currently lack coverage and/or (perhaps if our
system gains traction) if more operators configure their routers to
respond.

ACCURACY

I think both approaches are similarly accurate. Rolf mentions that revtr-lg
"perform[s] the actual measurement between two endpoints, we identify the
actual forwarding path, at the router-level, including load-balanced
paths." revtr-2.0 also measures the actual forwarding path between the two
endpoints, at the router/IP-level, including the ability to uncover the
multiple branches of load balanced paths.

In only 1.5% of cases, revtr-2.0 returned a path that did not agree with a
normal traceroute issued from the remote host (in a controlled experiment
where we had access to the remote host but did not give revtr-2.0 access). It
could be a path change between the two measurements, or an anomaly that
impacted either traditional traceroute or our tool. So in the other 98.5%
of cases, our tool was accurate. Rolf mentioned that revtr-2.0 has an
accuracy of 92% at the AS-level. What we meant by that is that 92.3% of our
measurements had all of the ASes on them that a traceroute issued from the
remote host had In an additional 6.1% of cases, revtr-2.0 missed a single
AS that was unresponsive -- like a "*" in traditional traceroute. In only
the remaining 1.5% of cases did the two measurements actually have
discrepancies.


We expect that our tool is similarly accurate at the IP and router-level,
it's just harder to give exact numbers because tools can return different
IP addresses that correspond to the same router, and so we did the
comparison at AS level.


Best,

Ethan (and Kevin Vermeulen, Dave Choffnes, and Italo Cunha)

On Wed, Feb 22, 2023 at 1:21 PM Rolf Winter <rolf.winter at hs-augsburg.de>
wrote:

> Hi Christoper,
>
> I cannot/shouldn't really answer, since this is somebody else's work.
> The latest publication on that body of work can be found here:
>
> https://dl.acm.org/doi/pdf/10.1145/3517745.3561422
>
> Published at IMC 22 last October.
>
> I believe a demo is actually online here: https://revtr.ccs.neu.edu/
>
> That piece of work and ours differ in a number of ways. Whereas the work
> you cite is an external system really, that let's you perform a reverse
> traceroute through said system, we have implemented something, that
> works just like traceroute does today, but for the reverse direction.
> I.e. it works from your terminal, performing a traceroute back to you.
> The system you mention has an accuracy of about 92% at the AS-level.
> Since we perform the actual measurement between two endpoints we
> identify the actual forwarding path, at the router-level, including
> load-balanced paths.
>
> But we use ICMP and would need code points to move forward. So if you
> find this useful, discussion on the IntArea mailing list would be
> appreciated.
>
> Best,
>
> Rolf
>
>
> Am 22.02.23 um 18:19 schrieb Christopher Morrow:
> > Didn't ethan's project:
> >    https://www.measurementlab.net/publications/reverse-traceroute.pdf
> >
> > end with usable code/etc?
> >
> > On Wed, Feb 22, 2023 at 8:09 AM Rolf Winter <rolf.winter at hs-augsburg.de>
> wrote:
> >>
> >> Dear NANOG folks,
> >>
> >> As you know, traceroute is unable to enumerate routers on the reverse
> >> path. Given that paths through the public internet are usually
> >> asymmetric, knowing the reverse path would be beneficial e.g. for
> >> troubleshooting purposes (https://youtu.be/L0RUI5kHzEQ?t=2312).
> >>
> >> We have implemented a reverse traceroute tool
> >> (https://github.com/hsanet/reverse-traceroute), both client and server
> >> for both IPv4 and IPv6. We are also in the process of specifying the
> >> protocol at the IETF
> >> (
> https://datatracker.ietf.org/doc/html/draft-heiwin-intarea-reverse-traceroute
> ).
> >>
> >>
> >> We also gave a talk on reverse traceroute at DENOG14
> >> (https://youtu.be/Y7NtqLEtgjU).
> >>
> >> If you would like to play with reverse traceroute, the easiest option is
> >> to work with the client and use one of the public server instances
> >> (https://github.com/HSAnet/reverse-traceroute/blob/main/ENDPOINTS). If
> >> you would be willing to host a public server instance yourself, please
> >> reach out to us. Also, if you find this work useful, please start
> >> discussing the work at the IntArea WG at the IETF.
> >>
> >> If you have any questions or comments, just drop us a line, file an
> >> issue on github and/or use the IntArea mailing list.
> >>
> >> Thanks a bunch,
> >>
> >> Rolf
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.nanog.org/pipermail/nanog/attachments/20230226/d6bc603c/attachment.html>


More information about the NANOG mailing list