On the scaling of congestion in the internet graph

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 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.

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 (<i>n</i>^1+ω(1), where <i>n</i> 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 <i>does not</i> 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 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.

REFERENCES

• 1: BGP Tables from the University of Oregon RouteViews Project. http://moat.nlanr.net/AS/data.
• 2: National Laboratory for Applied Network Research. Routing data. http://moat.nlanr.net/Routing/rawdata/.
• 3: W. Aiello , F. Chung, Random Evolution in Massive Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.510, October 14-17, 2001
• 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.
• 5: Albert, R., and Barabasi, A.-L. Topology of Evolving Networks: Local Events and Universality. Physical Review Letters 85(24) (2000), 5234--5237.
• 6: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 7: Barabasi, A.-L., and Albert, R. Emergnece of Scaling in Random Networks. Science 286 (1999), 509--512.
• 8: Alex Fabrikant , Elias Koutsoupias , Christos H. Papadimitriou, Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.110-122, July 08-13, 2002
• 9: 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
• 10: Fenner, T., Flaxman, A., and Frieze, A. High Degree Vertices and Eigenvalues in the Preferential Attachment Graph. In RANDOM 03 (2003), pp. 264--274.
• 11: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 12: Christos Gkantsidis , Milena Mihail , Amin Saberi, Conductance and congestion in power law graphs, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 13: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 14: Stefano Leonardi, On-line Network Routing, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.242-267, January 1998
• 15: Lun Li , David Alderson , Walter Willinger , John Doyle, A first-principles approach to understanding the internet's router-level topology, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 16: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.346, August 15-18, 2001
• 17: Milena Mihail , Christos Papadimitriou , Amin Saberi, On Certain Connectivity Properties of the Internet Topology, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.28, October 11-14, 2003
• 18: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 19: Okamura, H., and Seymour, P. Multicommodity Flows in Planar Graphs. Journal of Combinatorial Theory B 31 (1981), 75--81.
• 20: Kihong Park , Heejo Lee, On the effectiveness of route-based packet filtering for distributed DoS attack prevention in power-law internets, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.15-26, August 2001, San Diego, California, United States
• 21: 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).
• 22: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 23: Winick, J., and Jamin, S. Inet-3.0: Internet Topology Generator. Tech. rep., University of Michigan, 2002. Technical Report, CSE-TR-456-02.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Keywords:
congestion, power-law graphs, shortest path routing