On the Emergence of Highly Variable Distributions in the Autonomous System Topology
Abstract
Recent studies have noted that vertex degree in the autonomous system (AS) graph exhibits a highly variable distribution [15, 22]. The most prominent explanatory model for this phenomenon is the Barab asi-Albert (B-A) model [5, 2]. A central feature of the B-A model is preferential connectivity meaning that the likelihood a new node in a growing graph will connect to an existing node is proportional to the existing node nodes degree. In this paper we ask whether a more general explanation than the B-A model, and absent the assumption of preferential connectivity, is consistent with empirical data. We are motivated by two observations: first, AS degree and AS size are highly correlated [11]; and second, highly variable AS size can arise simply through exponential growth. We construct a model incorporating exponential growth in the size of the Internet, and in the number of ASes. We then show via analysis that such a model yields a size distribution exhibiting a power-law tail. In such a model, if an AS a link formation is roughly proportional to its size, then AS degree will also show high variability. We instantiate such a model with empirically derived estimates of growth rates and show that the resulting degree distribution is in good agreement with that of real AS graphs.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2003
- Accession Number
- ADA450798
Entities
People
- David Finkel
- John Byers
- Mark Crovella
- Marwan Fayed
- P. L. Krapivsky
- Sid Redner
Organizations
- Boston University