Does AS size determine degree in as topology?

ABSTRACT

In a recent and much celebrated paper, Faloutsos <i>et al.</i> [6] found that the inter Autonomous System (AS) topology exhibits a power-law 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 <i>et al.</i> [2], and its application to network topology generation in the work of Medina <i>et al.</i> [9], have explored a promising class of models that yield strict power-law degree distributions. These models, which we will refer to collectively as the <i>B-A model</i>, describe the detailed dynamics of the network growth process, modeling the way in which connections are made between ASs. There are two simple connectivity rules that define the evolution of AS connectivity over time: <i>incremental growth</i> where a new AS connects to existing ASs, and <i>preferential connectivity</i> where the likelihood of connecting to an AS is proportional to the vertex outdegree of the target AS. These simple rules, which are similar to the classical "rich get richer" model originally proposed by Simon [12], lead to power-law degree distributions.

While the B-A model provably yields power-law vertex degree distributions, recent empirical evidence indicates that the model may not be consistent with the dynamics underlying the evolution of the actual AS topology. First, there is strong evidence [3, 4] that the degree distribution of the actual AS topology does not conform to a strict power law. However, the distribution is certainly <i>heavy-tailed</i> or <i>highly-variable</i> in the sense that the observed vertex degrees typically range over three or four orders of magnitude; in some cases, the <i>tail</i> of the degree distribution may fit a power law. These observations were gleaned from more complete pictures of AS - level connectivity (obtained by augmenting BGP route tables with peering relationships from other sources) than those used by earlier work [2, 6, 9]. Second, the B-A model's AS connectivity evolution rules can be shown to be inconsistent with empirical AS growth measurements [16]. As such, while the B-A model appears to produce topologies whose degree distribution characteristics exhibit power-law behavior, it cannot be a valid <i>explanation</i> for the connectivity evolution in the AS topology.

Clearly, some of these empirical observations don't corroborate the claim that the B-A model explains the phenomenon of highly variable vertex degrees in the Internet's AS topology [2]. However, the B-A model was originally proposed as a simple illustration of how some elementary mechanisms or rules can give rise to power law vertex degree distributions. As such, it is likely that the B-A model can be modified to accommodate these more recent findings [1], but we will neither discuss here such modifications nor comment on their possibility for success. Instead, we merely note that any such resulting model would seek, as does the original B-A model, to explain the highly variable degree distribution of the AS topology through the detailed dynamics of how connections between ASs are established.

The purpose of this note is to raise the question --- motivated by the B-A approach---of whether the underlying cause of the high variability phenomenon of the vertex degree distribution lies in the detailed dynamics of network growth, or if there are alternative explanations. To that end, we briefly outline an alternative explanation for the AS topology degree distribution. We do not claim to have proven that this explanation holds; our purpose here is merely to expand the dialog to a larger class of explanations for the variability of the AS topology degree distribution.

REFERENCES

• 1: ALBERT, R., AND BARABASI, A.-L. Statistical Mechanics of Complex Networks. cond-mat/0106096 (June 2001).
• 2: BARABASI, A.-L., AND ALBERT, R. Emergence of Scaling in Random Networks. Science 286 (1999), 509--512.
• 3: BROIDO, A., AND CLAFFY, K. C. Internet Topology: Local Properties. In Proceedings of SPIE ITCom 2001 (Denver, CO, August 2001).
• 4: CHANG, H., GOVINDAN, R., JAMIN, S., SHENKER, S., AND WILLINGER, W. On Inferring AS-level Connectivity from BGP Route Tables. submitted to the ACM Internet Measurements Workshop 2001.
• 5: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 6: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 7: GOVINDAN, R., AND TANGMUNARUNKIT, H. Heuristics for Internet Map Discovery. In Proceedings of the IEEE Infocom (Tel-Aviv, Israel, March 2000).
• 8: LAHERRERE, J., AND SORNETTE, D. Stretched Exponential Distributions in Nature and Economy: Fat tails with characteristic scales. European Physics Journal B, 2 (1998), 525--539.
• 9: Alberto Medina , Ibrahim Matta , John Byers, On the origin of power laws in Internet topologies, ACM SIGCOMM Computer Communication Review, v.30 n.2, April 2000 [doi>10.1145/505680.505683]
• 10: OKUYAMA, K., TAKAYASU, M., AND TAKAYASU, H. Zipf's Law in income distribution of companies. Physica A 269 (1999), 125--131.
• 11: RAMSDEN, J. J., AND KISS-HAYPAL, G. Company size distribution in different countries. Physica A 277 (2000), 220--227.
• 12: SIMON, H. On a Class of Skew Distribution Functions. Biometrika (1953).
• 13: TANGMUNARUNKIT, H., GOVINDAN, R., JAMIN, S., SHENKER, S., AND WILLINGER, W. On network topologies, power laws and hierarchy. Tech. Rep. 01-746, University of Southern California, Computer Science Department, 2001.
• 14: TANGMUNARUNKIT, H., GOVINDAN, R., SHENKER, S., AND ESTRIN, D. The Impact of Policy on Internet Paths. In Proceedings of the IEEE Infocom (Anchorage, AK, 2001).
• 15: Werner Vogels, File system usage in Windows NT 4.0, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.93-109, December 12-15, 1999, Charleston, South Carolina, United States
• 16: WILLINGER, W., GOVINDAN, R., JAMIN, S., PAXSON, V., AND SHENKER, S. Scaling Phenomena in the Internet: Critically Examining Criticality. Proceedings of the National Academy of Sciences. 2001 (to appear); also available at http://topology.eecs.umich.edu.
• 17: ZIPF, G. K. Human Behavior and the Principle of Least Effort. Addison-Wesley, 1949.