ABSTRACT
Researchers have proposed a variety of metrics to measure important graph properties, for instance, in social, biological, and computer networks. Values for a particular graph metric may capture a graph's resilience to failure or its routing efficiency. Knowledge of appropriate metric values may influence the engineering of future topologies, repair strategies in the face of failure, and understanding of fundamental properties of existing networks. Unfortunately, there are typically no algorithms to generate graphs matching one or more proposed metrics and there is little understanding of the relationships among individual metrics or their applicability to different settings. We present a new, systematic approach for analyzing network topologies. We first introduce the dK-series of probability distributions specifying all degree correlations within d-sized subgraphs of a given graph G. Increasing values of d capture progressively more properties of G at the cost of more complex representation of the probability distribution. Using this series, we can quantitatively measure the distance between two graphs and construct random graphs that accurately reproduce virtually all metrics proposed in the literature. The nature of the dK-series implies that it will also capture any future metrics that may be proposed. Using our approach, we construct graphs for d=0, 1, 2, 3 and demonstrate that these graphs reproduce, with increasing accuracy, important properties of measured and modeled Internet topologies. We find that the d=2 case is sufficient for most practical purposes, while d=3 essentially reconstructs the Internet AS-and router-level topologies exactly. We hope that a systematic method to analyze and synthesize topologies offers a significant improvement to the set of tools available to network topology and protocol researchers.
- W. Aiello, F. Chung, and L. Lu. A random graph model for massive graphs. In STOC 2000. Google ScholarDigital Library
- M. Boguòá and R. Pastor-Satorras. Class of correlated random networks with hidden variables. Physical Review E 68:036112, 2003.Google ScholarCross Ref
- M. Boguòá R. Pastor-Satorras, and A. Vespignani. Cut-offs and finite size effects in scale-free networks. European Physical Journal B 38:205--209, 2004.Google ScholarCross Ref
- T. Bu and D. Towsley. On distinguishing between Internet power law topology generators. In INFOCOM 2002.Google Scholar
- CAIDA. Macroscopic topology AS adjacencies. http://www.caida.org/tools/measurement/skitter/asadjacencies.xmlGoogle Scholar
- H. Chang, S. Jamin, and W. Willinger. To peer or not to peer: Modeling the evolution of the Internet's AS-level topology. In INFOCOM 2006.Google ScholarCross Ref
- F. Chung and L. Lu. Connected components in random graphs with given degree sequences. Annals of Combinatorics 6:125--145, 2002.Google ScholarCross Ref
- F. K. R. Chung. Spectral Graph Theory volume 92 of Regional Conference Series in Mathematics American Mathematical Society, Providence, RI, 1997.Google Scholar
- S. N. Dorogovtsev. Networks with given correlations. http://arxiv.org/abs/cond-mat/0308336v1Google Scholar
- S. N. Dorogovtsev. Clustering of correlated networks. Physical Review E 69:027104, 2004.Google ScholarCross Ref
- S. N. Dorogovtsev and J. F. F. Mendes. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, Oxford, 2003. Google ScholarDigital Library
- P. Erdós and A. Rényi. On random graphs. Publicationes Mathematicae 6:290--297, 1959.Google Scholar
- M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the Internet topology. In SIGCOMM 1999. Google ScholarDigital Library
- P. Fraigniaud. A new perspective on the small-world phenomenon: Greedy routing in tree-decomposed graphs. In ESA 2005.Google Scholar
- C. Gkantsidis, M. Mihail, and E. Zegura. The Markov simulation method for generating connected power law random graphs. In ALENEX 2003.Google Scholar
- P. Harremoës. Binomial and Poisson distributions as maximum entropy distributions. Transactions on Information Theory 47(5):2039--041, 2001. Google ScholarDigital Library
- Internet Routing Registries. http://www.irr.net/.Google Scholar
- D. Krioukov, K. Fall, and X. Yang. Compact routing on Internet-like graphs. In INFOCOM 2004.Google ScholarCross Ref
- L. Li, D. Alderson, W. Willinger, and J. Doyle. A first-principles approach to understanding the Internets router-level topology. In SIGCOMM 2004. Google ScholarDigital Library
- P. Mahadevan, D. Krioukov, M. Fomenkov, B. Huffaker, X. Dimitropoulos, kc claffy, and A. Vahdat. The Internet AS-level topology:Three data sources and one definitive metric. Computer Communication Review 36(1), 2006. Google ScholarDigital Library
- S. Maslov, K. Sneppen, and A. Zaliznyak. Detection of topological patterns in complex networks:Correlation profile of the Internet. Physica A 333:529--540, 2004.Google ScholarCross Ref
- A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE:An approach to universal topology generation. In MASCOTS 2001. Google ScholarDigital Library
- N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. Equation-of-state calculations by fast computing machines. Journal of Chemical Physics 21:1087, 1953.Google ScholarCross Ref
- M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms 6:161--179, 1995. Google ScholarDigital Library
- M. E. J. Newman. Assortative mixing in networks. Physical Review Letters 89:208701, 2002.Google ScholarCross Ref
- University of Oregon RouteViews Project. http://www.routeviews.org/.Google Scholar
- M. A. Serrano and M. Boguòá Tuning clustering in random networks with arbitrary degree distributions. Physical Review E 72:036133, 2005.Google ScholarCross Ref
- N. J. A. Sloane. Sequence A001349. The On-Line Encyclopedia of Integer Sequences. http://www.research.att.com/projects/OEIS?Anum=A001349Google Scholar
- H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Network topology generators:Degree-based vs. structural. In SIGCOMM 2002. Google ScholarDigital Library
- A. Vázquez, R. Pastor-Satorras, and A. Vespignani. Large-scale topological and dynamical properties of the Internet. Physical Review E 65:066130, 2002.Google ScholarCross Ref
- F. Viger and M. Latapy. Efficient and simple generation of random simple connected graphs with prescribed degree sequence. In COCOON 2005. Google ScholarDigital Library
- J. Winick and S. Jamin. Inet-3. 0:Internet topology generator. Technical Report UM-CSE-TR-456-02, University of Michigan, 2002.Google Scholar
Index Terms
- Systematic topology analysis and generation using degree correlations
Recommendations
Systematic topology analysis and generation using degree correlations
Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communicationsResearchers have proposed a variety of metrics to measure important graph properties, for instance, in social, biological, and computer networks. Values for a particular graph metric may capture a graph's resilience to failure or its routing efficiency. ...
Orbis: rescaling degree correlations to generate annotated internet topologies
SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communicationsResearchers involved in designing network services and protocols rely on results from simulation and emulation environments to understand their application performance and scalability. To better understand the behavior of these applications and predict ...
TopGen - internet router-level topology generation based on technology constraints
Simutools '08: Proceedings of the 1st international conference on Simulation tools and techniques for communications, networks and systems & workshopsIn order to realistically simulate algorithms or evaluate P2P overlay topologies, a detailed model of the underlying router topology is required. Since actively measuring this topology is extremely laborious and furthermore a waste of network resources, ...
Comments