The Problem

Traceroute is one of the most widely-used tools for network troubleshooting, but it is not well-suited to modern networks where path-based load balancing is common.

If you are trying to debug a network and multiple paths are available to traffic, how do you know your traceroute has shown you all the available paths, or only a small portion? What happens if one of your load-balanced paths is causing trouble, but traceroute doesn't show it to you?

Paris Traceroute allows you to deterministically measure particular paths by setting particular flow IDs - effectively setting combinations in packet headers to be treated consistently by routers on a path. Using this trick to run many traceroutes with different flow IDs to a target may reveal an entire topology, but without extra logic it may involve tens of thousands of traceroute packets to do so. Many of those packets will be sent over hops that never change making those packets redundant, while also consuming bandwidth and time.

We have been working on a multi-level, multi-path detection traceroute. Our work improves our ability to reveal the router level of a multi-path route in a single command, and it does so while trying to minimise the number of traceroute packets required.

We are interested in deploying this as a new measurement type on the RIPE Atlas platform, and we'd like your feedback. More on that below!

MDA-Lite

Not all paths are simple paths, so we need a smarter traceroute.

In addition, companies build more complex network topologies now than ever before. Prior to 2018, topologies that were reported by researchers were not wider than 16 interfaces and could look like this:

Figure 1: Example topology that has been reported before 2018

Today, our measurements reveal that many distinct interfaces can be discovered at a single hop in a traceroute. We found examples of up to 96 interfaces at one hop.

We have found some surprisingly complex topologies in our work. In all types of Autonomous Systems (Tier 1, Tier 2, CDNs, cellular providers, etc.), we have seen topologies such as those in Figures 2 and 3:

Figure 2: Complex topology found in a CDN

Figure 3: Complex topology found in a cellular provider

Both of these topologies show a complex overlapping of interfaces between hops, which we refer to as meshing. Revealing such a complex topology has an important cost overhead: if we were speaking of hundreds of probes a decade ago to fully uncover all of the hops in a load-balanced path with traceroute, today we might require thousands, even tens of thousands, of packets in very complex cases. Many packets are necessary to deterministically test various paths until such a point that any algorithm is confident it has uncovered all likely interfaces at any given hop.

We defined MDA-Lite, a form of traceroute with a Multi-path Detection Algorithm (MDA), which attempts to avoid as many redundant traceroute packets as possible. Our aim is to reduce the packets necessary while also being confident we have mapped all of the path diversity.

Luckily, the majority of the load balanced topologies we found in our studies follow what we refer to as the unmeshed uniform pattern, such as in Figure 4 below:

Figure 4: Unmeshed uniform topology found in a Tier 2 Autonomous System

Let's define those two words:

• Unmeshed means the absence of all the edge complexity seen in Figures 2 and 3; that is, the edges do not overlap.
• Uniform means that given a certain hop, every interface at this hop has the same probability to be reached.

Our measurements suggest that both these conditions are very common, which allows MDA-Lite to minimise the number of packets when mapping a multi-path topology.

Multilevel Route Tracing

Digging deeper, the complexity of these topologies is intriguing but many IP addresses may be aliased onto one physical device. To assist our understanding, we built a Multi-level Traceroute, which gives us both the IP level of a multi-path traceroute and also the router level.

In our tools, we are using the Monotonic Bound Test (MBT) from MIDAR, router TTL-fingerprinting and MPLS tunnels labelling, as these techniques offer good efficiency without too much additional probing.

As MDA-Lite traceroutes are likely to send many traceroute packets, we take advantage of the ICMP answers from the IP level to save time and minimise the number of packets sent for this new step of multi-path traceroute.

In our measurements, we found two cases of “topology reduction” illustrated by the following examples.

First, compare Figure 5 (below) with Figure 2 from earlier; these represent the same network, but in the second case we've applied the multi-level mapping to identify individual routers (which are indicated as the grouped nodes in the network):

Figure 5: Complex topology found in a CDN after Multi-level Paris Traceroute. Compare to Figure 2.

In the second case, we did the same as above but we observed that almost nothing has changed, except the last multiple interfaces hop which converged into a single router; compare Figure 6 (below) to Figure 3 from above:

Figure 6: Complex topology found in a cellular provider after Multi-level Paris Traceroute. Compare to Figure 3.

This does not mean that all the distinct nodes of this topology belong to a distinct router. Indeed, typically if all the interfaces of a router set the ICMP response with an IP ID of 0, we can not infer that these interfaces belong to the same router. But this gets us closer to understanding the router-level topology.

Conclusions, and adding a new traceroute to RIPE Atlas?

All of our tools and our dataset can be found in this git repo. You will find our Multi-level MDA-Lite Paris Traceroute implementation, the dataset it is built on, and the Fakeroute tool we used to help test the tool.

We are interested in building on this investigation and working with the RIPE NCC on a RIPE Atlas implementation of this form of traceroute.

In short:

• This form of traceroute is sufficiently different from the current RIPE Atlas implementation that we think it ought to be a distinct measurement type. We think we can develop this without changing the existing traceroute measurements on the platform.
• In order to learn complex path topologies, this type of measurement requires many more traceroute packets than the current traceroute. This may be undesirable for some RIPE Atlas probe hosts. We may therefore choose to implement it for RIPE Atlas anchors only, or implement it for anchors and v3/v4 probes that opt-in.
• Further, this form of traceroute will require additional state to be held in memory, which may be difficult to manage in the constraints of a v3 probe.
• Finally, it may be possible to request an Atlas MDA measurement that meets a given confidence level regarding the completeness of a topology, or perhaps it could adhere to a packet budget and report the final confidence in the results.

These are basically open questions that we'd like you, the community, to offer your opinions on. If you have comments or questions, including how this may benefit you as a network operator, please let us know in the comment section below, or on the ripe-atlas mailing list.

This post is a summary of work we have written in our paper Multi-level MDA-Lite Paris Traceroute, which we presented at IMC 2018. You can find out more about this work by:

• Reading the paper or,
• Viewing our presentation at the IETF101 maprg meeting: slides
• Watching our recent presentation at the MAT Working Group at the RIPE 77 meeting: slides, video

We'd love to hear your feedback! Would this be useful to you as a network operator?