Dynamics of routes using traceroute

> By Matthieu Latapy


The standard traceroute tool gives (in principle) the route followed by packets sent from the machine running traceroute to a given destination, as a series of IP adresses (the addresses of successive routers on the path). It proceeds by sending a probe at distance 1, thus obtaining the IP address of the first router on the path, then a new probe but at distance 2, thus obtaining the IP address of the second router on the path, and so on.
If the router at a given distance does not answer to the probe then traceroute display a star (*).

In order to observe the dynamics of routes between our machine and a given destination, we ran 100 periodic traceroutes (one every 10 minutes).
The animation displays the successive routes discovered, with IP addresses (the circle nodes) and stars. The first time a node or link is discovered, it is drawn in red, and the width of each link grows as the number of times we saw it in our measurement. We also give the number of packets sent by our measurement, the number of IP addresses and stars observed, as well as the number of times we ran traceroute so far.

First notice that, whereas routers which answer our probes are identified by an IP address, the routers which do not answer only lead to stars which we may be unable to distinguish. Indeed, if a router at a given distance never answers probes, we will see a star every time we traverse it. This leads to a new star every time we run traceroute, which is unrealistic. However, this situation cannot be distinguished from the case where several routers are present at that distance and none answers to probes. In order to avoid a situation where we would have to display huge numbers of irrelevant stars, we applied the following heuristic: we merged all stars appearing immediately after a same node (IP address or other star). As a consequence, the number of star nodes in our drawing is much smaller than the total number of observed stars.

One may observe that parts of the route are very stable, whereas others change very often, and some change at very specific occasions. The most regular changes, close to the destination, is generally considered as load-balancing: a router has a choice between several next hops to reach the destination, and chooses alternatively each of these possibilities, leading to the discovery of different paths. Here, a router has two possible choices, which in turn have eight possible choices each, and each of these eight nodes have two choices. finally, the path to the destination ends with a series of four stars.

At traceroute number 23, something new happens: we see six stars at the end of the route, instead of four. At traceroute 24, we observe that the route changed significantly, leading to the discovery of 7 new nodes (two of which first appear as stars). After some time (at traceroute 38), the route changes again to the initial one.

One may guess that the change observed at traceroute 23 is probably due to the fact that the route changed during the running of this traceroute; as the length of the route changes, we observe some nodes (here, two stars) several times. See this paper for details.

This entry was posted in Videos and tagged , ,