> By Elie Rotenberg, Christophe Crespelle and Matthieu Latapy

Here, we aim at measuring the IP-level neighborhood of internet core routers in a rigorous way.

We proceed as follows. First, we send traceroute probes from many monitors distributed in the internet towards a given target router. Then we consider the last but one IP adress of each traceroute measurement as a neighbor of the target.

The underlying idea is that, if we use sufficiently many monitors, distributed enough on the internet, then we will discover all the neighbors of the target.

However, because of erroneous information delivered by traceroute, we may also discover fake neighbors.

For instance, if there exist two paths *m-a-b-c-t* and *m-a-d-t* from monitor *m* to target *t*, the discovered path may be *m-a-b-t* if traceroute probes follow twice the first path then the second one. In this case, we see *b* as a neighbor of t, which is a mistake.

The appearance of such fake neighbors is due to routing dynamics, which often occurs because of load balancing. See also this video and this one.

Notice however that, if all paths have the same length, the fact that traceroute may mix different routes does not lead to observation of fake neighbors anymore.

We therefore send several probes from each monitor to the selected target and discard monitors from which we observe routes of different length.

One question rises: will there be enough monitors left to discover all the neighbors of the target?

For the above plot, we conducted a measurement involving 477 monitors and 8071 random targets. Each traceroute from each monitor to each destination is repeated 10 times. For each destination, we computed the number of monitors whose routes to this destination all have the same length, and we plotted the cumulative distribution of this value. In other words, a point with coordinates *(x,y)* means that exactly *x* targets obtained all traceroutes with the same length from *y* monitors or less.

The plot shows that only 980 targets out of 8 071 (roughly 12%) have less than 350 monitors producing all its traceroute of the same length. Using simulations (not presented here), we have provided strong evidence that such a number is large enough to discover all neighbors of the target, as long as the degree of the target is not too high (typically 50 or less). Thus, our method is able to produce complete and exact neighborhood of most of core routers, and it is robust to routing dynamics.