nanog mailing list archives

Previous By Date Next
Previous By Thread Next

Re: Reverse Traceroute

From: Rolf Winter <rolf.winter () hs-augsburg de>
Date: Mon, 27 Feb 2023 08:47:11 +0100
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 () ccs neu edu <mailto:revtr () 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 () ccs neu edu <mailto:revtr () 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 () hs-augsburg de <mailto:rolf.winter () 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 () hs-augsburg de <mailto:rolf.winter () 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

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature

Previous By Date Next
Previous By Thread Next

Current thread: