Multi-level MDA-Lite Paris Traceroute

By on 3 Dec 2018

Category: Tech matters

Tags: , , ,


Blog home

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, at Sorbonne Université, in collaboration with the RIPE NCC, 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 minimize the number of traceroute packets required.

Further to this, we are interested in deploying this as a new measurement type on the RIPE Atlas platform. More on that below.


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

In addition, companies build more complex network topologies now than ever before. Before 2018, topologies that were reported by researchers were not wider than 16 interfaces (see example below):

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, and so forth), 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 minimize the number of packets when mapping a multi-path topology.

Multilevel route tracing

Digging deeper, the complexity of these topologies is intriguing as 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 minimize 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 that converged into a single router; compare Figure 6 (below) to Figure 3 above to see the difference.

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. However, this does get us closer to understanding the router-level topology.

All of our tools and our dataset can be found in this git repository. 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.

Adding a new traceroute to RIPE Atlas?

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 to hold additional state 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:

Contributors: Stephen Strowes

Adapted from original post which appeared on RIPE Labs Blog.

Kévin Vermeulen is a PhD candidate in Computer Science at Sorbonne Université under the supervision of Olivier Fourmaux and Timur Friedman. 

Rate this article

The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.


  1. Shabbir

    Good tool for multipath load balancing testing I am going to try it soon. My work involves improving network performance and I normally need such things. I’ll try it mainly with mpls l3 vpns.


Leave a Reply

Your email address will not be published. Required fields are marked *