Conductance and congestion in power law graphs

ABSTRACT

It has been observed that the degrees of the topologies of several communication networks follow heavy tailed statistics. What is the impact of such heavy tailed statistics on the performance of basic communication tasks that a network is presumed to support? How does performance scale with the size of the network? We study routing in families of sparse random graphs whose degrees follow heavy tailed distributions. Instantiations of such random graphs have been proposed as models for the topology of the Internet at the level of Autonomous Systems as well as at the level of routers. Let n be the number of nodes. Suppose that for each pair of nodes with degrees d_u and d_v we have O(d_u d_v) units of demand. Thus the total demand is O(n²). We argue analytically and experimentally that in the considered random graph model such demand patterns can be routed so that the flow through each link is at most O(n log² n). This is to be compared with a bound O(n²) that holds for arbitrary graphs. Similar results were previously known for sparse random regular graphs, a.k.a. "expander graphs." The significance is that Internet-like topologies, which grow in a dynamic, decentralized fashion and appear highly inhomogeneous, can support routing with performance characteristics comparable to those of their regular counterparts, at least under the assumption of uniform demand and capacities. Our proof uses approximation algorithms for multicommodity flow and establishes strong bounds of a generalization of "expansion," namely "conductance." Besides routing, our bounds on conductance have further implications, most notably on the gap between first and second eigenvalues of the stochastic normalization of the adjacency matrix of the graph.

REFERENCES

• 1: L. Adamic. Zipf, power-laws, and pareto, a ranking tutorial. http://www.hpl.hp.com/shl/papers/ranking/, 2002.
• 2: S. Agarwal, L. Subramanian, J. Rexford, and R. Katz. Characterizing the internet hierarchy from multiple vantage points web page. http://www.cs.berkeley.edu/~1sagarwal/research/BGP-hierarchy/, 2002.
• 3: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 4: 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
• 5: D. Alderson, J. Doyle, and W. Willinger. Toward an optimization-driven framework for designing and generating realistic internet topologies. In HotNets, 2002.
• 6: A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.
• 7: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 8: Bob metcalfe eats his words. Internet Computing Online, 1(3), 1997. http://www.computer.org/internet/v1n3/eats9702.htm.
• 9: B. Bollobás. Random Graphs, 2nd Ed. Cambridge University Press, 2001.
• 10: B. Bollobás and O. Riordan. The diameter of scale-free graphs. Combinatorica, To appear.
• 11: Béla Bollobás , Oliver Riordan , Joel Spencer , Gábor Tusnády, The degree sequence of a scale-free random graph process, Random Structures & Algorithms, v.18 n.3, p.279-290, May 2001 [doi>10.1002/rsa.1009]
• 12: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 13: A. Broido and K. Claffy. Internet topology: Connectivity of ip graphs. http://www.caida.org/outreach/papers/2001/OSD/, 2001.
• 14: C. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. The origins of power-laws in internet topologies revisited. In Proc. Infocom. IEEE, 2002.
• 15: F. Chung and L. Lu. The average distance in a random graph with given expected degree. Available at http://math.ucsd.edu/~1fan/inet.html.
• 16: F. Chung and L. Lu. Connected components in random graphs with given degree sequences. http://www.math.ucsd.edu/~1fan, 2002.
• 17: F. R. Chung. Spectral Graph Theory. American Mathematical Society Book Series, 1997.
• 18: Colin Cooper , Alan M. Frieze, A General Model of Undirected Web Graphs, Proceedings of the 9th Annual European Symposium on Algorithms, p.500-511, August 28-31, 2001
• 19: J. Doyle, J. Carlson, S. Low, F. Paganini, G. Vinnicombe, W. Willinger, J. Hickey, P. Parrilo, and L. Vandenberghe. Robustness and the internet: Theoretical foundations. http://netlab.caltech.edu/internet/, 2002.
• 20: 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
• 21: 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
• 22: N. L. for Applied Retwork Research. Route views archive. http://moat.nlanr.net/Routing/rawdata, 2002.
• 23: Alan M. Frieze, Disjoint Paths in Expander Graphs via Random Walks: A Short Survey, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.1-14, October 08-10, 1998
• 24: L. Gao. On inferring autonomous system relationships in the internet. IEEE Glogal Internet, 2000.
• 25: C. Gkantsidis, M. Mihail, and E. Zegura. The markov chain simulation method for generating connected power law random graphs. In Proc. 5th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, January 2003.
• 26: C. Gkantsidis, M. Mihail, and E. Zegura. Spectral analysis of internet topologies. In Proc. Infocom. IEEE, 2003. To appear.
• 27: C. Jin, Q. Chen, and S. Jamin. Inet: Internet topology generator. Technical Report CSE-TR-433-00, U. Michigan, Ann Arbor, 2000.
• 28: J. Kleinberg. Navigation in small world. Nature, 406, 2000.
• 29: J. Kleinberg , R. Rubinfeld, Short paths in expander graphs, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.86, October 14-16, 1996
• 30: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 31: C. Law and K.-Y. Siu. Distributed construction of random expander networks. In Proc. Infocom. IEEE, 2003. To appear.
• 32: F. Leighton. Parallel Algorithms and Architectures. Morgan Kaufmann, 1992.
• 33: F. Leighton and S. Rao. Circuit switching: Multicommodity flow based approach. In Workshop on Randomized Parallel Computing, 1996.
• 34: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 35: N. Linial, E. London, and Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215--245, 1995.
• 36: A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261--278, 1988.
• 37: Alberto Medina , Ibrahim Matta , John Byers, On the origin of power laws in Internet topologies, ACM SIGCOMM Computer Communication Review, v.30 n.2, April 2000 [doi>10.1145/505680.505683]
• 38: Bob M. Metcalfe, Internet Collapses and Other InfoWorld Punditry, Hungry Minds, Incorporated, 2000
• 39: M. Mihail and C. Papadimitriou. Random 2002, 2002.
• 40: M. Mihail, C. Papadimitrious, and A. Saberi. On certain connectivity properties of internet graphs. submitted, 2003.
• 41: Michael Molloy , Bruce Reed, A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, v.6 n.2-3, p.161-179, March-May 1995
• 42: Michael Molloy , Bruce Reed, The Size of the Giant Component of a Random Graph with a Given Degree Sequence, Combinatorics, Probability and Computing, v.7 n.3, p.295-305, September 1998 [doi>10.1017/S0963548398003526]
• 43: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 44: M. Newman. Assortativity mixing in networks. Phys. Rev. Lett., 89, 2002.
• 45: V. Padmanabhan, L. Qiu, and H. Wang. Server-based inference of internet performance. In Proc. Infocom. IEEE, 2003. To appear.
• 46: C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• 47: N. Pippinger. Information theory and the complexity of switching networks. In Proc. 16th Symposium on Foundations of Computer Science (FOCS), pages 113--118, 1975.
• 48: N. Pippinger. Superconcentrators. SIAM Journal on Computing, 6(2):298--304, 1977.
• 49: N. Pippinger. On rearrangeable and non-blocking switching networks. Journal of Computer and System Sciences, 17(2):145--162, 1978.
• 50: J. S. Quarterman. Imminent death of the internet? Matrix News, 6(6), June 1996. Also, available at http://www2.aus.us.mids.org/mn/606/death.html.
• 51: Y. Rehkter and P. Gross. Application of the border gateway protocol in the internet. RFC 1655, IETF, July 1994.
• 52: Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
• 53: L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the internet hierarchy from multiple vantage points. In Proc. Infocom. IEEE, 2002.
• 54: 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
• 55: H. Tagmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Network topology generators: Degree-based vs structural. Technical Report 02-760, USC, 2002.
• 56: D. Towsley. Modeling the internet: Seeing the forest through the trees. Keynote Address, Sigmetrics, 2002.
• 57: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 58: W. Willinger and J. Doyle. Robustness and the internet: Design and evolution. http://netlab.caltech.edu/internet/, 2002.
• 59: H. Zhang, A. Goel, and R. Govindan. Using the small-world model to improve freenet performance. In Proc. Infocom. IEEE, 2002.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

General Terms:
Algorithms, Performance, Theory

Keywords:
conductance, congestion, expansion, internet topology, powerlaw graphs, routing