Seminars will be held in the Lecture Theatre 1 - William Gates Building, Computer Laboratory at 4.15pm

	See also: Security seminars Logic and Semantics seminars Additional meetings weekly timetable for other meetings

On the Existence and Origin of Power Laws in AS-Level Internet Topologies

Sugih Jamin

University of Michigan, Ann Arbor

In a recent paper, Faloutsos et al. found that the inter Autonomous System (AS) topology exhibits a power-law vertex degree distribution. This result was quite unexpected in the networking community and stirred significant interest in exploring the possible causes of this phenomenon. The work of Barabasi and Albert and its appli ation to network topology generation in the work of Medina et al. have explored a promising class of models that yield strict power-law vertex degree distributions. In this talk I will describe our efforts to re-examine the BGP measurements that form the basis for the results reported in the paper by Faloutsos et al. 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. I will also describe our attempts to construct and validate a more complete AS-level topology. The AS peering relationship maps constructed from NLANR data typically miss 20-50% or even more of the relationships found in our more complete AS maps. Subsequently, we find that while the vertex degree distributions resulting from the extended maps are heavy-tailed, they deviate significantly from a strict power law. Finally, we show that available historical data does not support the connectivity-based dynamics assumed in the paper by Barabasi and Albert. 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 by Barabasi and Albert.