Article

Scaling properties of the Internet graph

Authors:

Srinivasan SeshanAuthors Info & Claims

PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

Pages 337 - 346

https://doi.org/10.1145/872035.872087

Published: 13 July 2003 Publication History

Abstract

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 roughly improve 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.In this paper, using a combination of analysis and extensive simulations, we show that the worst congestion in the Internet in fact scales poorly with the network size (n^1+Ω(1), where n is the number of nodes), when shortest-path routing is used. We also show, somewhat surprisingly, that policy-based routing does not exacerbate the maximum congestion when compared to shortest-path routing.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 the Internet graph can be improved dramatically by introducing moderate amounts of redundancy in the graph in terms of parallel edges between pairs of adjacent nodes.

References

[1]

BGP Tables from the University of Oregon Route Views Project. http://moat.nlanr.net/AS/data.

[2]

National laboratory for applied network research. Routing data. http://moat.nlanr.net/Routing/rawdata/.

[3]

AIELLO, W., CHUNG, F., AND LU, L. Random evolution in massive graphs. In FOCS (2001), pp. 510--519.

Digital Library

[4]

AKELLA, A., CHAWLA, S., KANNAN, A., AND SESHAN, S. Scaling properties of the Internet graph. Technical Report CMU-CS-03-131, CMU, Pittsburgh, Pennsylvania, May 2003.

Digital Library

[5]

ALBERT, R., AND BARABASI, A.-L. Topology of evolving networks: local events and universality. Physical Review Letters 85(24) (2000), 5234--5237.

[6]

AUMANN, Y., AND RABANI, Y. An o(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM Journal on Computing 27(1) (1998), 291--301.

Digital Library

[7]

BARABASI, A.-L., AND ALBERT, R. Emergence of scaling in random networks. Science 286 (1999), 509--512.

[8]

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.

Digital Library

[9]

FALOUTSOS, M., FALOUTSOS, P., AND FALOUTSOS, C. On power-law relationships of the Internet topology. In Proceedings of the SIGCOMM '99 Symposium on Communications Architectures and Protocols (1999), pp. 251--262.

Digital Library

[10]

GAO, L. On inferring autonomous system relationships in the Internet. IEEE/ACM Transactions on Networking 9(6) (December 2001).

Digital Library

[11]

GKANTSIDIS, C., SABERI, A., AND MIHAIL, M. Conductance and congestion in power law graphs. In Proceedings of the ACM Sigmetrics 2003 (2003).

Digital Library

[12]

LEIGHTON, F. T. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, 1992.

Digital Library

[13]

LEONARDI, S. On-line network routing. In Online Algorithms - The State of the Art (1998), Springer, pp. 242--267.

Digital Library

[14]

MEDINA, A., LAKHINA, A., MATTA, I., AND BYERS, J. Brite: An approach to universal topology generation. In MASCOTS (2001).

Digital Library

[15]

MITCHELL, T. M. Machine Learning. McGraw-Hill Companies, Inc., 1997.

Digital Library

[16]

OKAMURA, H., AND SEYMOUR, P. Multicommodity flows in planar graphs. Journal of Combinatorial Theory B 31 (1981), 75--81.

[17]

PARK, K., AND LEE, H. On the effectiveness of route-based packet filtering for distributed DoS attack prevention in power-law Internets. In Proceedings of the SIGCOMM '01 Symposium on Communications Architectures and Protocols (San Diego, California, August 2001).

Digital Library

[18]

SUBRAMANIAN, L., AGARWAL, S., REXFORD, J., AND KATZ, R. H. Characterizing the Internet hierarchy from multiple vantage points. In Proceedings of IEEE INFOCOM. (June 2002).

[19]

TANGMUNARUNKIT, H., GOVINDAN, R., JAMIN, S., SHENKER, S., AND WILLINGER, W. Network topology generators: Degree-based vs structural. In Proceedings of the SIGCOMM '02 Symposium on Communications Architectures and Protocols (Pittsburgh, Pennsylvania, August 2002).

Digital Library

[20]

WINICK, J., AND JAMIN, S. Inet-3.0: Internet topology generator. Tech. rep., University of Michigan, 2002. Technical Report, CSE-TR-456-02.

Cited By

Guichon JFatès NContassot-Vivier SAmato M(2024)Properties of B2B Invoice Graphs and Detection of StructuresComplex Networks & Their Applications XII10.1007/978-3-031-53472-0_37(444-455)Online publication date: 21-Feb-2024
https://doi.org/10.1007/978-3-031-53472-0_37
Arakawa STakine TMurata M(2012)Analyzing and modeling router-level internet topology and application to routing controlComputer Communications10.1016/j.comcom.2012.02.01035:8(980-992)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.comcom.2012.02.010
Erlebach TMoonen LSpieksma FVukadinović D(2009)Connectivity Measures for Internet Topologies on the Level of Autonomous SystemsOperations Research10.1287/opre.1080.067757:4(1006-1025)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1287/opre.1080.0677
Show More Cited By

Index Terms

Scaling properties of the Internet graph
1. Hardware
  1. Communication hardware, interfaces and storage
2. Networks
  1. Network architectures

Recommendations

On the scaling of congestion in the internet graph

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 ...
Increasing Internet Capacity Using Local Search

Open Shortest Path First (OSPF) is one of the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow evenly at nodes where several outgoing links are on shortest paths to the destination. ...
PMPATH: A Policy Routing System for Multihomed End-Hosts

To achieve profits derived from multihoming, policy routing is supposed to be necessary. For routers' policy routing, some systems and implementations already exist. In addition to routers' operating systems with policy routing functions, IP Filter and ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

July 2003

380 pages

ISBN:1581137087

DOI:10.1145/872035

General Chair:
Elizabeth Borowsky
Boston Coll.
,
Program Chair:
Sergio Rajsbaum
UNAM

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC03

Sponsor:

PODC03: Twenty-Second Annual ACM Symposium on Principles of Distributed Computing

July 13 - 16, 2003

Massachusetts, Boston

Acceptance Rates

PODC '03 Paper Acceptance Rate 51 of 226 submissions, 23%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
544
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guichon JFatès NContassot-Vivier SAmato M(2024)Properties of B2B Invoice Graphs and Detection of StructuresComplex Networks & Their Applications XII10.1007/978-3-031-53472-0_37(444-455)Online publication date: 21-Feb-2024
https://doi.org/10.1007/978-3-031-53472-0_37
Arakawa STakine TMurata M(2012)Analyzing and modeling router-level internet topology and application to routing controlComputer Communications10.1016/j.comcom.2012.02.01035:8(980-992)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.comcom.2012.02.010
Erlebach TMoonen LSpieksma FVukadinović D(2009)Connectivity Measures for Internet Topologies on the Level of Autonomous SystemsOperations Research10.1287/opre.1080.067757:4(1006-1025)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1287/opre.1080.0677
Hirayama TArakawa SArai KMurata M(2009)On the Packet Delay Distribution in Power-Law NetworksProceedings of the 2009 First International Conference on Evolving Internet10.1109/INTERNET.2009.23(101-105)Online publication date: 23-Aug-2009
https://dl.acm.org/doi/10.1109/INTERNET.2009.23
Fukumoto RArakawa SMurata M(2006)On routing controls in ISP topologies: A structural perspective2006 First International Conference on Communications and Networking in China10.1109/CHINACOM.2006.344870(1-5)Online publication date: Oct-2006
https://doi.org/10.1109/CHINACOM.2006.344870
Huang YGuerin R(2005)Does Over-Provisioning Become More or Less Efficient as Networks Grow Larger?Proceedings of the 13TH IEEE International Conference on Network Protocols10.1109/ICNP.2005.12(225-235)Online publication date: 6-Nov-2005
https://dl.acm.org/doi/10.1109/ICNP.2005.12
Akella AChawla SKannan ASeshan S(2004)On the scaling of congestion in the internet graphACM SIGCOMM Computer Communication Review10.1145/1031134.103114134:3(43-56)Online publication date: 1-Jul-2004
https://dl.acm.org/doi/10.1145/1031134.1031141
Erlebach TMoonen LSpieksma FVukadinovic D(undefined)Connectivity Measures for Internet TopologiesSSRN Electronic Journal10.2139/ssrn.870269
https://doi.org/10.2139/ssrn.870269

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents