{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T07:26:17Z","timestamp":1751873177925,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2001,10,1]],"date-time":"2001-10-01T00:00:00Z","timestamp":1001894400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGCOMM Comput. Commun. Rev."],"published-print":{"date-parts":[[2001,10]]},"abstract":"<jats:p>In a recent and much celebrated paper, Faloutsos &lt;i&gt;et al.&lt;\/i&gt; [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 &lt;i&gt;et al.&lt;\/i&gt; [2], and its application to network topology generation in the work of Medina &lt;i&gt;et al.&lt;\/i&gt; [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 &lt;i&gt;B-A model&lt;\/i&gt;, 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: &lt;i&gt;incremental growth&lt;\/i&gt; where a new AS connects to existing ASs, and &lt;i&gt;preferential connectivity&lt;\/i&gt; 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.<\/jats:p>\n          <jats:p>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 &lt;i&gt;heavy-tailed&lt;\/i&gt; or &lt;i&gt;highly-variable&lt;\/i&gt; in the sense that the observed vertex degrees typically range over three or four orders of magnitude; in some cases, the &lt;i&gt;tail&lt;\/i&gt; 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 &lt;i&gt;explanation&lt;\/i&gt; for the connectivity evolution in the AS topology.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/1037107.1037108","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:49:14Z","timestamp":1106758154000},"page":"7-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":59,"title":["Does AS size determine degree in as topology?"],"prefix":"10.1145","volume":"31","author":[{"given":"Hongsuda","family":"Tangmunarunkit","sequence":"first","affiliation":[{"name":"USC-ISI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Doyle","sequence":"additional","affiliation":[{"name":"Caltech"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramesh","family":"Govindan","sequence":"additional","affiliation":[{"name":"USC-ISI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Walter","family":"Willinger","sequence":"additional","affiliation":[{"name":"AT&amp;T"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sugih","family":"Jamin","sequence":"additional","affiliation":[{"name":"Univ. of Michigan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Scott","family":"Shenker","sequence":"additional","affiliation":[{"name":"ACIRI"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2001,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Statistical Mechanics of Complex Networks. cond-mat\/0106096 (June","author":"ALBERT R.","year":"2001","unstructured":"ALBERT , R. , AND BARABASI , A.-L. Statistical Mechanics of Complex Networks. cond-mat\/0106096 (June 2001 ). ALBERT, R., AND BARABASI, A.-L. Statistical Mechanics of Complex Networks. cond-mat\/0106096 (June 2001)."},{"key":"e_1_2_1_2_1","first-page":"509","article-title":"Emergence of Scaling","volume":"286","author":"BARABASI A.-L.","year":"1999","unstructured":"BARABASI , A.-L. , AND ALBERT , R . Emergence of Scaling in Random Networks. Science 286 ( 1999 ), 509 -- 512 . BARABASI, A.-L., AND ALBERT, R. Emergence of Scaling in Random Networks. Science 286 (1999), 509--512.","journal-title":"Random Networks. Science"},{"key":"e_1_2_1_3_1","volume-title":"K. C. Internet Topology: Local Properties. In Proceedings of SPIE ITCom 2001","author":"BROIDO A.","year":"2001","unstructured":"BROIDO , A. , AND CLAFFY , K. C. Internet Topology: Local Properties. In Proceedings of SPIE ITCom 2001 ( Denver, CO , August 2001 ). BROIDO, A., AND CLAFFY, K. C. Internet Topology: Local Properties. In Proceedings of SPIE ITCom 2001 (Denver, CO, August 2001)."},{"key":"e_1_2_1_4_1","volume-title":"On Inferring AS-level Connectivity from BGP Route Tables. submitted to the ACM Internet Measurements Workshop","author":"CHANG H.","year":"2001","unstructured":"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 . 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."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.650143"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_7_1","volume-title":"H. Heuristics for Internet Map Discovery. In Proceedings of the IEEE Infocom (Tel-Aviv","author":"GOVINDAN R.","year":"2000","unstructured":"GOVINDAN , R. , AND TANGMUNARUNKIT , H. Heuristics for Internet Map Discovery. In Proceedings of the IEEE Infocom (Tel-Aviv , Israel , March 2000 ). GOVINDAN, R., AND TANGMUNARUNKIT, H. Heuristics for Internet Map Discovery. In Proceedings of the IEEE Infocom (Tel-Aviv, Israel, March 2000)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s100510050276"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/505680.505683"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(99)00086-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(99)00572-5"},{"key":"e_1_2_1_12_1","volume-title":"On a Class of Skew Distribution Functions. Biometrika","author":"SIMON H.","year":"1953","unstructured":"SIMON , H. On a Class of Skew Distribution Functions. Biometrika ( 1953 ). SIMON, H. On a Class of Skew Distribution Functions. Biometrika (1953)."},{"key":"e_1_2_1_14_1","volume-title":"D. The Impact of Policy on Internet Paths. In Proceedings of the IEEE Infocom","author":"TANGMUNARUNKIT H.","year":"2001","unstructured":"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 ). 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)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/319151.319158"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1073\/pnas.012583099"},{"key":"e_1_2_1_17_1","volume-title":"Human Behavior and the Principle of Least Effort","author":"ZIPF G. K.","year":"1949","unstructured":"ZIPF , G. K. Human Behavior and the Principle of Least Effort . Addison-Wesley , 1949 . ZIPF, G. K. Human Behavior and the Principle of Least Effort. Addison-Wesley, 1949."}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1037107.1037108","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1037107.1037108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:36:49Z","timestamp":1750282609000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1037107.1037108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,10]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2001,10]]}},"alternative-id":["10.1145\/1037107.1037108"],"URL":"https:\/\/doi.org\/10.1145\/1037107.1037108","relation":{},"ISSN":["0146-4833"],"issn-type":[{"type":"print","value":"0146-4833"}],"subject":[],"published":{"date-parts":[[2001,10]]},"assertion":[{"value":"2001-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}