The origin of power laws in Internet topologies revisited

Abstract — In a recent paper, Faloutsos et al. [1] found that the inter Autonomous System (AS) topology exhibits a power-law vertex degree dis-tribution. This result was quite unexpected in the networking community and stirred significant interest in exploring the possible causes of this phe-nomenon. The work of Barabasi and Albert [2] and its application to net-work topology generation in the work of Medina et al. [3] have explored a promising class of models that yield strict power-law vertex degree dis-tributions. In this paper, we re-examine the BGP measurements that form the basis for the results reported in [1]. We find that by their very nature (i.e., being strictly BGP-based), the data provides a very incomplete picture of Internet connectivity at the AS level. The AS connectivity maps con-structed from this data (the original maps) typically miss 20–50 % or even more of the physical links in AS maps constructed using additional sources (the extended maps). Subsequently, we find that while the vertex degree dis-tributions resulting from the extended maps are heavy-tailed, they deviate significantly from a strict power law. Finally, we show that available his-torical data does not support the connectivity-based dynamics assumed in [2]. Together, our results suggest that the Internet topology at the AS level may well have developed over time following a very different set of growth processes than those proposed in [2]. I