{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T21:28:20Z","timestamp":1762032500419,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2004,7,1]],"date-time":"2004-07-01T00:00:00Z","timestamp":1088640000000},"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":[[2004,7]]},"abstract":"<jats:p>As the Internet grows in size, it becomes crucial to understand how the speeds of links in the network must improve in order to sustain the pressure of new end-nodes being added each day. Although the speeds of links in the core and at the edges improve roughly according to Moore's law, this improvement alone might not be enough. Indeed, the structure of the Internet graph and routing in the network might necessitate much faster improvements in the speeds of key links in the network.<\/jats:p>\n          <jats:p>In this paper, using a combination of analysis and extensive simulations, we show that the worst congestion in the Internet AS-level graph in fact scales poorly with the network size (&lt;i&gt;n&lt;\/i&gt;&lt;sup&gt;1+\u03c9(1)&lt;\/sup&gt;, where &lt;i&gt;n&lt;\/i&gt; is the number of nodes), when shortest-path routing is used to route traffic between ASes. We also show, somewhat surprisingly, that policy-based routing &lt;i&gt;does not&lt;\/i&gt; exacerbate the maximum congestion when compared to shortest-path routing.<\/jats:p>\n          <jats:p>Our results show that it is crucial to identify ways to alleviate this congestion to avoid some links from being perpetually congested. To this end, we show that the congestion scaling properties of Internet-like graphs can be improved dramatically by introducing moderate amounts of redundancy in the graph in terms of parallel edges between pairs of adjacent nodes.<\/jats:p>","DOI":"10.1145\/1031134.1031141","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:49:14Z","timestamp":1106758154000},"page":"43-56","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["On the scaling of congestion in the internet graph"],"prefix":"10.1145","volume":"34","author":[{"given":"Aditya","family":"Akella","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuchi","family":"Chawla","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arvind","family":"Kannan","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivasan","family":"Seshan","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"BGP Tables from the University of Oregon RouteViews Project. http:\/\/moat.nlanr.net\/AS\/data.  BGP Tables from the University of Oregon RouteViews Project. http:\/\/moat.nlanr.net\/AS\/data."},{"key":"e_1_2_1_2_1","unstructured":"National Laboratory for Applied Network Research. Routing data. http:\/\/moat.nlanr.net\/Routing\/rawdata\/.  National Laboratory for Applied Network Research. Routing data. http:\/\/moat.nlanr.net\/Routing\/rawdata\/."},{"key":"e_1_2_1_3_1","first-page":"510","volume-title":"Random Evolution in Massive Graphs. In FOCS","author":"Aiello W.","year":"2001","unstructured":"Aiello , W. , Chung , F. , and Lu , L . Random Evolution in Massive Graphs. In FOCS ( 2001 ), pp. 510 -- 519 . Aiello, W., Chung, F., and Lu, L. Random Evolution in Massive Graphs. In FOCS (2001), pp. 510--519."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.85.5234"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"e_1_2_1_7_1","first-page":"509","volume":"286","author":"Barabasi A.-L.","year":"1999","unstructured":"Barabasi , A.-L. , and Albert , R. Emergnece of Scaling in Random Networks. Science 286 ( 1999 ), 509 -- 512 . Barabasi, A.-L., and Albert, R. Emergnece of Scaling in Random Networks. Science 286 (1999), 509--512.","journal-title":"Emergnece of Scaling in Random Networks. Science"},{"key":"e_1_2_1_8_1","first-page":"110","volume-title":"Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. In ICALP","author":"Fabrikant A.","year":"2002","unstructured":"Fabrikant , A. , Koutsoupias , E. , and Papadimitriou , C . Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. In ICALP ( 2002 ), pp. 110 -- 122 . Fabrikant, A., Koutsoupias, E., and Papadimitriou, C. Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. In ICALP (2002), pp. 110--122."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_10_1","first-page":"264","volume":"03","author":"Fenner T.","year":"2003","unstructured":"Fenner , T. , Flaxman , A. , and Frieze , A. High Degree Vertices and Eigenvalues in the Preferential Attachment Graph. In RANDOM 03 ( 2003 ), pp. 264 -- 274 . Fenner, T., Flaxman, A., and Frieze, A. High Degree Vertices and Eigenvalues in the Preferential Attachment Graph. In RANDOM 03 (2003), pp. 264--274.","journal-title":"High Degree Vertices and Eigenvalues in the Preferential Attachment Graph. In RANDOM"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.974527"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/781027.781046"},{"key":"e_1_2_1_13_1","volume-title":"Trees, Hypercubes","author":"Leighton F. T.","year":"1992","unstructured":"Leighton , F. T. Introduction to Parallel Algorithms and Architectures: Arrays , Trees, Hypercubes . Morgan Kaufmann Publishers , 1992 . Leighton, F. T. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, 1992."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1007\/BFb0029572","volume-title":"Online Algorithms - The State of the Art","author":"Leonardi S.","year":"1998","unstructured":"Leonardi , S. On-line Network Routing . In Online Algorithms - The State of the Art ( 1998 ), Springer , pp. 242 -- 267 . Leonardi, S. On-line Network Routing. In Online Algorithms - The State of the Art (1998), Springer, pp. 242--267."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015470"},{"key":"e_1_2_1_16_1","volume-title":"MASCOTS","author":"Medina A.","year":"2001","unstructured":"Medina , A. , Lakhina , A. , Matta , I. , and Byers , J . BRITE: An Approach to Universal Topology Generation . In MASCOTS ( 2001 ). Medina, A., Lakhina, A., Matta, I., and Byers, J. BRITE: An Approach to Universal Topology Generation. In MASCOTS (2001)."},{"key":"e_1_2_1_17_1","first-page":"28","volume-title":"On Certain Connectivity Properties of the Internet Topology. In FOCS 2003","author":"Mihail M.","year":"2003","unstructured":"Mihail , M. , Papadimitriou , C. , and Saberi , A . On Certain Connectivity Properties of the Internet Topology. In FOCS 2003 ( 2003 ), pp. 28 -- 35 . Mihail, M., Papadimitriou, C., and Saberi, A. On Certain Connectivity Properties of the Internet Topology. In FOCS 2003 (2003), pp. 28--35."},{"key":"e_1_2_1_18_1","volume-title":"Machine Learning","author":"Mitchell T. M.","year":"1997","unstructured":"Mitchell , T. M. Machine Learning . McGraw-Hill Companies, Inc. , 1997 . Mitchell, T. M. Machine Learning. McGraw-Hill Companies, Inc., 1997."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80012-3"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383061"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2002.1019307"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633040"},{"key":"e_1_2_1_23_1","volume-title":"Inet-3.0: Internet Topology Generator. Tech. rep","author":"Winick J.","year":"2002","unstructured":"Winick , J. , and Jamin , S . Inet-3.0: Internet Topology Generator. Tech. rep ., University of Michigan , 2002 . Technical Report, CSE-TR-456-02. Winick, J., and Jamin, S. Inet-3.0: Internet Topology Generator. Tech. rep., University of Michigan, 2002. Technical Report, CSE-TR-456-02."}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1031134.1031141","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1031134.1031141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:30:56Z","timestamp":1750264256000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1031134.1031141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,7]]}},"alternative-id":["10.1145\/1031134.1031141"],"URL":"https:\/\/doi.org\/10.1145\/1031134.1031141","relation":{},"ISSN":["0146-4833"],"issn-type":[{"type":"print","value":"0146-4833"}],"subject":[],"published":{"date-parts":[[2004,7]]},"assertion":[{"value":"2004-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}