Title: On the Emergence of Highly Variable Distributions in the Autonomous System Topology
Author: Fayed, Marwan; Krapivsky, Paul; Byers, John; Crovella, Mark; Finkel, David; Redner, Sid
Date: March 1, 2003
Abstract:
Recent studies have noted that vertex degree in the autonomous system
(AS) graph exhibits a highly variable distribution \cite{fff,MP01}.
The most prominent explanatory model for this phenomenon is the
Barabasi-Albert (B-A) model [BA99,AB00]. 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's 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 [CHEN02]; 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's 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.