Rigorous Measurement of the Internet Degree Distribution
Matthieu Latapy1
Élie Rotenberg1,2
Christophe Crespelle2
Fabien Tarissan2
1Université Paris-Sorbonne, UPMC Univ. Paris 06, CNRS
LIP6 UMR 7606, 4 place Jussieu 75005 Paris
2Université Claude Bernard Lyon 1, DANTE/INRIA
LIP UMR CNRS 5668, ENS de Lyon, Université de Lyon
Firstname.Lastname@lip6.fr
Abstract
The degree distribution of the internet, that is, the fraction of routers with k links for any k, is its most studied property. It has a crucial influence on network robustness, spreading phenomena and protocol design. In practice, however, this distribution is observed on partial, biased and erroneous maps. This raises serious concerns about the true knowledge we actually have of this key property. Here, we design and run a drastically new measurement approach for the reliable estimation of the degree distribution of the internet, without resorting to any map. It consists of sampling random core routers and precisely estimating their degree with probes sent from many monitors scattered over the internet. Our measurement shows that the true degree distribution significantly differs from classical assumptions: it is heterogeneous but it decreases sharply, in a way incompatible with a heavy-tailed power law.
