Comparing Trade-off Based Models of the Internet

• Autorzy: Spathari A. , Foudalis I. , Sideri M. , Papadimitriou C.
• Języki publikacji: EN

Abstrakty

EN

We introduce and evaluate several new models of network growth. Our models are extensions of the FKP model, modifying and improving it in various dimensions. In all these models nodes arrive one by one, and each node is connected to previous nodes by optimizing a trade-off between a geometric objective ("last mile cost") and a topological objective ("position in the network"). Our new models differ from the original FKP model in directions inspired by the real Internet: two or more edges are attached to each arriving node (while the FKP model produces a tree); these edges are chosen according to various criteria such as robustness; edges may be added to the network between old nodes; or only certain "fertile" nodes (an attribute that changes dynamically) are capable of attracting new edges. We evaluate these models, and compare them with the graph of the Internet's autonomous systems, with respect to a suite of many test parameters (such as average degree, power law exponent, and local clustering rank) proposed in the literature; to this end we have developed the network generation and measurement system Pandora.

Słowa kluczowe

EN

Internet topology; power law; scale-free graphs; network generators; network modeling and simulation; complex networks

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 92, nr 4
• Strony: 363--372
• Opis fizyczny: Bibliogr. 22 poz., wykr.

Twórcy

autor

Spathari A.

autor

Foudalis I.

autor

Sideri M.

autor

Papadimitriou C.

• Departmrnt of Computer Science, Athens University of Economics and Business, Patision 76, 10434 Athens, Atiki, Greece,

Bibliografia

• [1] Albert, R., Barabási, A.: Statistical Mechanics of Complex Networks, Reviews of Modern Physics, 74, 2002, 47.
• [2] Alvarez-Hamelin, J. I., Schabanel, N.: An Internet Graph Model Based on Trade-off Optimization, The European Physical Journal B - Condensed Matter and Complex Systems, 38, 2004, 231-237.
• [3] Barabási, A., Albert, R.: Emergence of Scaling in Random Networks, SCIENCE: Science, 286, 1999, 509-512.
• [4] Berger, N., Bollobás, B., Borgs, C., Chayes, J., Riordan, O.: Degree Distribution of the FKP Network Model, TCS: Theoretical Computer Science, 379, 2007, 306-316.
• [5] Bollobás, B., Riordan, O.: Mathematical Results on Scale-free Random Graphs, in: Handbook of Graphs and Networks: From the Genome to the Internet, Bornholdt and Schuster, 2003.
• [6] Bonato, A.: A Survey of Models of the Web Graph, Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN), LNCS, 1, 2004.
• [7] Brandes, U., Erlebach, T., Eds.: Network Analysis: Methodological Foundations [outcome of a Dagstuhl seminar, 13-16 April 2004], vol. 3418 of Lecture Notes in Computer Science, Springer, 2005.
• [8] CAIDA: The Cooperative Association for Internet Data Analysis. In http://www.caida.org/. BGP: http://bgp.potaroo.net/. Internet Data Catalog: http://imdc.datacat.org.
• [9] Chen, Q., Chang, H., Govindan, R., Jamin, S., Shenker, S., Willinger, W.: The Origin of Power-Laws in Internet Topologies Revisited, INFOCOM, 2002.
• [10] Costa, L., Rodrigues, F., Travieso, G., Boas, A. V.: Characterization of complex networks: A survey of measurements, Advances in Physics, 56, 2005, 167 - 242.
• [11] Dhamdhere, A., Dovrolis, C.: Ten years in the evolution of the internet ecosystem, Internet Measurement Conference (K. Papagiannaki, Z.-L. Zhang, Eds.), ACM, 2008.
• [12] Dorogovtsev, S., Mendes, J.: Evolution of Networks : from Biological Nets to the Internet and WWW, Oxford University Press, 2003.
• [13] Fabrikant, A., Koutsoupias, E., Papadimitriou, C.: Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet, ICALP: Annual International Colloquium on Automata, Languages and Programming, 2002.
• [14] Faloutsos, M., Faloutsos, P., Faloutsos, C.: On Power-Law Relationships of the Internet Topology, ACM SIGCOMM'99, 1999.
• [15] Foudalis, I.: Pandora Topology Generator, http://pages.cs.aueb.gr/aiw/projects.html.
• [16] Haddadi, H., Rio, M., Iannaccone, G., Moore, A., Mortier, R.: Network topologies: inference, modeling, and generation, Communications Surveys & Tutorials, IEEE, 10, 2008, 48-69.
• [17] Krioukov, D., Chung, F., Claffy, K., Fomenkov,M., Vespignani, A.,Willinger, W.: The Workshop on Internet Topology (WIT) Report, ACM SIGCOMM Computer Communication, 37(1), December 07 2006, 69-73.
• [18] Mitzenmacher, M., Siganos, G., Faloutsos, M., Faloutsos, P., Faloutsos, C.: Brief History of Generative Models for Power Law and Lognormal Distributions, Internet Math, 1, 2004, 226 - 251.
• [19] Park, K., Lee, H.: On the effectiveness of route-based packet filtering for distributed DoS attack prevention in power-law internets, SIGCOMM, 2001.
• [20] Spatharis, A., Foudalis, I., Sideri, M.: Competition-Induced Tradeoff-based Modeling of the Internet, Technical report, Athens University Of Economics And Business, 2007.
• [21] Strogatz, S.: Exploring Complex Networks, NATURE: Nature, 410, 2001, 268-276.
• [22] Winick, J., Jin, C., Chen, Q., Jamin, S.: Inet-3.0 Topology Generator, http://topology.eecs.umich.edu/inet/.