Reverse Traceroute

Mon Feb 27 07:47:11 UTC 2023

Before "revtr-lg" sticks, in the grand tradition of Paris Traceroute and 
Tokyo Ping we call our version of traceroute "Augsburg Traceroute". And 
it does not resemble a looking glass server. There are two parties 
involved in a reverse traceroute operation (not counting the routers 
that reply to an expired packet with an ICMP Time Exceeded) and that are 
the two hosts at the end of the path in question. Just like ping or 
traceroute today. There is no external system or particular server 
instance required. What it means though is that, if we want to have this 
kind of functionality for the public internet, we need to go through the 
IETF standardization process (or have the server side run at the 
application layer, which we would like to avoid). That might take some 
time and getting this into operating system code might take some time, 
too, but we believe it is worth doing.

The reason why we would like to have this on NLNOG Ring is not, because 
we need the servers to make the traceroute result better, but to give 
people a lot more choice for public instances against which they can run 
a reverse traceroute. If you have infrastructure and would like to make 
use of reverse traceroute today, you can. You can just use our code. For 
the server, the only hard requirement is a Linux kernel version 5.15 or 
above.

So from my perspective, the main differences are:

1. Who: An external system that attempts to measure a path for you 
(revtr-2.0) or two hosts performing a traceroute between each other 
(Augsburg Traceroute).

2. How: Used techniques such as source address spoofing and record route 
options (amongst others, revtr-2.0) vs. a new ICMP message to trigger a 
traceroute probe and convey the results (Augsburg Traceroute).

3. What: Can create a map of the paths through the internet and do 
on-demand traceroutes (revtr-2.0) is only useful between a host you 
control (issuing the traceroute) and a host on the internet willing to 
perform the operation (Augsburg Traceroute).

A lot of other differences are a result of the above such as overhead, 
accuracy, policability, deployability etc.

Just as a final remark, the reason why I said that we can accurately 
measure the router-level path (including load-balanced paths) is that we 
basically perform a form of Paris Traceroute between two hosts from 
those actual hosts at the end of the path in question.

Best,

Rolf

Am 27.02.23 um 05:51 schrieb Ethan Katz-Bassett:
> 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 <mailto: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 <mailto: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. 
> Rolfmentioned 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 
> <mailto: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
>     <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/
>     <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
>     <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 <mailto: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
>     <https://youtu.be/L0RUI5kHzEQ?t=2312>).
>      >>
>      >> We have implemented a reverse traceroute tool
>      >> (https://github.com/hsanet/reverse-traceroute
>     <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 <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 <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
>     <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 --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4757 bytes
Desc: S/MIME Cryptographic Signature
URL: <http://mailman.nanog.org/pipermail/nanog/attachments/20230227/53a2e2eb/attachment.bin>