On the high variability of AS sizes in Internet Topology:

There has been a significant increase in research activities related to modeling and analyzing the Internet topology in the past three years. The results of such studies may facilitate many tasks such as designing more efficient protocols, creating realistic models for simulation, and speculation on the growth process of the Internet. In particular, we focus on the toplogical features at the domain, or Autonomous System (AS) level, where an AS is a connected subnetwork administered by a specific authority. We plan to investigate the high variability in AS sizes (the number of routers in an AS) and how it is related to AS degrees.

A recent study by Faloutsos et al. [1] used topology information collected using Border Gateway Protocol (BGP) routing tables obtained from the Oregon route server [2], and showed that graph distributions followed power-laws. An explanation of that phenomenon, the BA model, was presented by Barabasi and Albert [3]. However, it has been shown that the BGP data may provide only a very sketchy picture of the complete inter-AS connection in the actual Internet [4]. Using more complete data sets, Chang et al. showed that power laws do not hold, however the distributions are highly variable [5]. A recent paper by Tangmunarunkit et al. argued that the BA model can not be a valid explanation for the connectivity evolution in AS topology [6]. They used the BGP data to support their alternative explanation.

The objectives of this project are to:

• Present an overview of the recent studies in AS topology.
• Demonstrate the high variability in AS sizes using the more complete data set used in [5].
• Determine the size-degree relationship using that data set.
• If possible, attempt to shed some light on possible causes of the high variability phenomenon.

References:

1. M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On Power-law Relationships of the Internet Topology," in SIGCOMM'99, pp. 251-261, 1999.
2. University of Oregon Route Views Project.
3. A.-L. Barabasi, and R. Albert, "Emergence of Scaling in Random Networks." Science 286, pp. 509-512, 1999.
4. H. Chang, S. Jamin, and W. Willinger, "Inferring AS-level Internet Topology from Router-Level Path Traces," Proceeding of SPIE ITCom 2001, Denver, CO, 19-24, August 2001
5. Q. Chen, H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, "The Origin of Power Laws in Internet Topologies Revisited," to appear in Proceeding of IEEE Infocom 2002.
6. H. Tangmunarunkit, J. Doyle, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, "Does AS Size Determine Degree in AS Topology?," ACM Computer Communication Review, October 2001.