Christos Gkantsidis
Milena Mihail
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 du and dv we have O(du dv) units of demand. Thus the total demand is O(n2). 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 log2 n). This is to be compared with a bound O(n2) 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.
- L. Adamic. Zipf, power-laws, and pareto, a ranking tutorial. http://www.hpl.hp.com/shl/papers/ranking/, 2002.]]Google Scholar
- 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.]]Google Scholar
- W. Aiello, F. R. K. Chung, and L. Lu. A random graph model for power law graphs. In Proc. 41st Symposium on Foundations of Computer Science (FOCS), pages 171--180. IEEE, 2000.]] Google ScholarDigital Library
- W. Aiello, F. R. K. Chung, and L. Lu. Random evolution in massive graphs. In Proc. 42nd Symposium on Foundations of Computer Science (FOCS), pages 510--519. IEEE, 2001.]] Google ScholarDigital Library
- D. Alderson, J. Doyle, and W. Willinger. Toward an optimization-driven framework for designing and generating realistic internet topologies. In HotNets, 2002.]]Google Scholar
- A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.]]Google ScholarCross Ref
- C. Berge. Graphs and Hypergraphs. North Holland Publishing Company, 1973.]] Google ScholarDigital Library
- Bob metcalfe eats his words. Internet Computing Online, 1(3), 1997. http://www.computer.org/internet/v1n3/eats9702.htm.]]Google Scholar
- B. Bollobás. Random Graphs, 2nd Ed. Cambridge University Press, 2001.]]Google Scholar
- B. Bollobás and O. Riordan. The diameter of scale-free graphs. Combinatorica, To appear.]]Google Scholar
- B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády. The degree sequence of a scale-free random graph process. Random Structures and Algorithms, 18(3):279--290, 2001.]] Google ScholarDigital Library
- A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomikns, and J. Wiener. Graph structure in the web. 9th International World Wide Web Conference (WWW9)/Computer Networks, 33(1-6):309--320, 2000.]] Google ScholarDigital Library
- A. Broido and K. Claffy. Internet topology: Connectivity of ip graphs. http://www.caida.org/outreach/papers/2001/OSD/, 2001.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- F. Chung and L. Lu. Connected components in random graphs with given degree sequences. http://www.math.ucsd.edu/~1fan, 2002.]]Google Scholar
- F. R. Chung. Spectral Graph Theory. American Mathematical Society Book Series, 1997.]]Google Scholar
- C. Cooper and A. Frieze. A general model for web graphs. In ESA, pages 500--511, 2001.]] Google ScholarDigital Library
- 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.]]Google Scholar
- A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. Heuristically optimized tradeoffs: A new paradigm for powerlaws in the internet. ICALP 2002, 2002.]] Google ScholarDigital Library
- M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. In Proc. SigComm. ACM, 1999.]] Google ScholarDigital Library
- N. L. for Applied Retwork Research. Route views archive. http://moat.nlanr.net/Routing/rawdata, 2002.]]Google Scholar
- A. Frieze. Disjoint Paths in Expander Graphs via Random Walks: A Short Survey, volume 1518 of Lecture Notes in Computer Science. Springer Verlag, 1998.]] Google ScholarDigital Library
- L. Gao. On inferring autonomous system relationships in the internet. IEEE Glogal Internet, 2000.]]Google Scholar
- 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.]]Google Scholar
- C. Gkantsidis, M. Mihail, and E. Zegura. Spectral analysis of internet topologies. In Proc. Infocom. IEEE, 2003. To appear.]]Google ScholarCross Ref
- C. Jin, Q. Chen, and S. Jamin. Inet: Internet topology generator. Technical Report CSE-TR-433-00, U. Michigan, Ann Arbor, 2000.]]Google Scholar
- J. Kleinberg. Navigation in small world. Nature, 406, 2000.]]Google Scholar
- J. Kleinberg and R. Rubinfeld. Short paths in expander graphs. In Proc. 37th Symposium on Foundations of Computer Science (FOCS), pages 86--95. IEEE, 1996.]] Google ScholarDigital Library
- R. Kumar, P. Raghavan, S. Rajagopalan, S. D., A. Tomkins, and E. Upfal. Stochastic models for the web graphs. In Proc. 41st Symposium on Foundations of Computer Science (FOCS), pages 57--65. IEEE, 2000.]] Google ScholarDigital Library
- C. Law and K.-Y. Siu. Distributed construction of random expander networks. In Proc. Infocom. IEEE, 2003. To appear.]]Google ScholarCross Ref
- F. Leighton. Parallel Algorithms and Architectures. Morgan Kaufmann, 1992.]]Google Scholar
- F. Leighton and S. Rao. Circuit switching: Multicommodity flow based approach. In Workshop on Randomized Parallel Computing, 1996.]]Google Scholar
- F. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46:787--832, 1999.]] Google ScholarDigital Library
- N. Linial, E. London, and Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215--245, 1995.]]Google ScholarCross Ref
- A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261--278, 1988.]]Google ScholarCross Ref
- A. Medina, I. Matta, and J. Byers. On the origin of power-laws in internet topologies. ACM Computer Communications Review, April 2000.]] Google ScholarDigital Library
- B. Metcalfe. Internet Collapses and Other InfoWorld Punditry. Hungry Minds, Inc., May 2000.]] Google ScholarDigital Library
- M. Mihail and C. Papadimitriou. Random 2002, 2002.]]Google Scholar
- M. Mihail, C. Papadimitrious, and A. Saberi. On certain connectivity properties of internet graphs. submitted, 2003.]]Google Scholar
- M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms, 6:161--180, 1995.]] Google ScholarDigital Library
- M. Molloy and B. Reed. The size of the largest component of a random graph on a fixed degree sequence. Combinatorics, Probability and Computing, 7:295--306, 1998.]] Google ScholarDigital Library
- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.]] Google ScholarDigital Library
- M. Newman. Assortativity mixing in networks. Phys. Rev. Lett., 89, 2002.]]Google Scholar
- V. Padmanabhan, L. Qiu, and H. Wang. Server-based inference of internet performance. In Proc. Infocom. IEEE, 2003. To appear.]]Google Scholar
- C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.]]Google Scholar
- N. Pippinger. Information theory and the complexity of switching networks. In Proc. 16th Symposium on Foundations of Computer Science (FOCS), pages 113--118, 1975.]]Google ScholarDigital Library
- N. Pippinger. Superconcentrators. SIAM Journal on Computing, 6(2):298--304, 1977.]]Google ScholarCross Ref
- N. Pippinger. On rearrangeable and non-blocking switching networks. Journal of Computer and System Sciences, 17(2):145--162, 1978.]]Google ScholarCross Ref
- 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.]]Google Scholar
- Y. Rehkter and P. Gross. Application of the border gateway protocol in the internet. RFC 1655, IETF, July 1994.]]Google Scholar
- A. Sinclair. Algorithms for Random Generation and Counting: A Markov Chain Approach. Springer-Verlag, 1997.]] Google ScholarDigital Library
- L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the internet hierarchy from multiple vantage points. In Proc. Infocom. IEEE, 2002.]]Google ScholarCross Ref
- H. Tagmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Network topology generators: Degree-based vs structural. In Proc. SigComm. ACM, 2002.]] Google ScholarDigital Library
- H. Tagmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Network topology generators: Degree-based vs structural. Technical Report 02-760, USC, 2002.]]Google Scholar
- D. Towsley. Modeling the internet: Seeing the forest through the trees. Keynote Address, Sigmetrics, 2002.]]Google Scholar
- V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.]] Google ScholarDigital Library
- W. Willinger and J. Doyle. Robustness and the internet: Design and evolution. http://netlab.caltech.edu/internet/, 2002.]]Google Scholar
- H. Zhang, A. Goel, and R. Govindan. Using the small-world model to improve freenet performance. In Proc. Infocom. IEEE, 2002.]]Google ScholarDigital Library
Index Terms
- Conductance and congestion in power law graphs
Recommendations
Conductance and congestion in power law graphs
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 ...
Comparing the Structure of Power-Law Graphs and the Internet AS Graph
ICNP '04: Proceedings of the 12th IEEE International Conference on Network ProtocolsIn this work we devise algorithmic techniques to compare the interconnection structure of the Internet AS Graph with that of graphs produced by topology generators that match the power-law degree distribution of the AS graph. We are guided by the ...
Crossing graphs of fiber-complemented graphs
Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-...
Comments