Profiles of BFS to model internet topology measurements

> By Wang Xiaomin, Matthieu Latapy and Michèle Soria

Profiles of BFS to model internet topology measurements

Profiles of BFS to model internet topology measurements

The basic approach to construct a map of the internet as a graph is as follows: one runs the traceroute tool from some machines, called monitors, towards some others, called destinations, and then merges all the obtained paths.

The view obtained from each monitor is roughly a tree, and may be modeled as a BFS tree. Although this approximation is rather rough in general, it seems reasonable for the nodes close from the monitor.

The properties of a BFS (for instance, the number of nodes at a each level, called profile of the BFS) are consequences of some properties of the underlying graph. Therefore, one may try to deduce the properties of the internet topology from the ones of the BFS-like measurements we have of it.

The plot above illustrates this approach. It contains three pairs of curves, each pair being composed of a simulation curve and a theoretical prediction which we established. From left to right, the first plot is obtained on power-law graphs, random Poisson graphs and regular graphs, each containing one million nodes. Each curve represents the proportion of nodes at a given distance from the root of a BFS, i.e. the profile of the BFS.

It appears clearly that the shapes of these plots make it possible to distinguish between the three types (power-law, Poisson and regular) of random graphs. Also, our theoretical predictions fit the experiments very well, even though the variance is higher for power-law graphs.

This entry was posted in Plots and tagged , ,