微信服务号

微信订阅号

2025-4-5- 11
Home > Archive>Volume 20, Issue 1, 2009 >109-123
PDF HTML XML Export Cite reminder
Modeling the Complex Internet Topology
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [70]
    • |
  • Related
    • |
  • Cited by [7]
    • | |
  • Comments
    Abstract:

    This paper presents the basic concept of topology's properties and modeling metrics; categorizes and analyzes both AS-level models and router-lever models. Moreover, this paper summarizes current research achievements on Internet topology's modeling, especially at the router-level. Finally, it identifies future directions and open problems of the topology modeling research.

    Reference
    [1] Krioukov D, Chung F, Claffy KC. The workshop on Internet topology (WIT) report. ACM SIGCOMM Computer Communication Review, 2007,37(1):69-73.
    [2] Alderson D, Li L, Willinger W. Understanding Internet topology: Principles, models and validation. ACM Trans. on Networking, 2005,13(6):1205-1218.
    [3] Mahadevan P, Hubble C, Krioukov D. Orbis: Rescaling degree correlations to generate annotated Internet topologies. In: Proc. of the ACM SIGCOMM. 2007.
    [4] Newman M. The structure and function of complex networks. SIAM Review, 2003,45:167-256.
    [5] Viger F, Barrat A, Dall'Asta L, Zhang CH, Kolaczyk ED. What is the real size of a sample network? The case of the Internet. Physical Review E, 2007,75(5):056111.
    [6] Guo L, Xu XM. The Complex Network. Shanghai: Shanghai Scientific and Technological Education Publication, 2006 (in Chinese).
    [7] Dall'Asta L, Hamelin IA, Barrat A. Exploring networks with traceroute-like probes: Theory and simulations. Theoretical Computer Science, 2005,355:6-24.
    [8] Oliveira R, Zhang BC, Zhang LX. Observing the evolution of Internet AS topology. In: Proc. of the ACM SIGCOMM. 2007.
    [9] Mahadevan P, Krioukov D, Fomenkov M. The Internet AS-level topology: Three data sources and one definitive metric. Computer Communication Review, 2006,36(1):17-26.
    [10] Mahadevan P, Krioukov D, Fall K. Systematic topology analysis and generation using degree correlations. In: Proc. of the ACM SIGCOMM. 2006.
    [11] Zhang Y, Zhang HL, Fang BX. A survey on Internet topology modeling. Journal of Software, 2004,15(8):1220-1226 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/15/1220.htm
    [12] Zeng W, Xu MW, Wu JP. Survey of network topology models. Application Research of Computers, 2005,(7) (in Chinese with English abstract).
    [13] Li L, Alderson D, Willinger W. A first-principles approach to understanding the Internet's router-level topology. In: Proc. of the ACM SIGCOMM. 2004.
    [14] Doyle JC, Alderson D, Li L, Low S, Roughan M, Shalunov S, Tanaka R, Willinger W. The "robust yet fragile" nature of the Internet. Proc. of the National Academy of Sciences USA, 2005,102(41):14497-14502.
    [15] Spring N, Mahajan R, Wetherall D. Measuring ISP topologies with Rocketfuel. In: Proc. of the ACM SIGCOMM. 2002.
    [16] Skitter AS adjacency list. http://www.caida.org/tools/measurement/skitter/as adjacencies.xml
    [17] Skitter destination list. http://www.caida.org/analysis/topology/macroscopic/list.xml
    [18] Dorogovtsev SN, Mendes JFF. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, 2003.
    [19] Carmi S, Havlin S, Kirkpatrick S. A model of Internet topology using k-shell decomposition. Proc. of the National Academy of Sciences of the USA, 2007,104(27):11150-11154.
    [20] Chang H, Govindan R, Jamin S. Toward capturing representative AS-level Internet topologies. Computer Networks, 2004, 44(6):737-755.
    [21] Chang H, Jamin S, Willinger W. Internet connectivity at the AS-level: An optimization-driven modeling approach. In: Proc. of the ACM SIGCOMM Workshop on Models, Methods and Tools for Reproducible Network Research. 2003.
    [22] Dimitropoulos X, Riley G. Modeling autonomous-system relationships. In: Proc. of the 20th Workshop on Principles of Advanced and Distributed Simulation, Vol.26. 2006. 143-149.
    [23] Gkantsidis C, Mihail M, Zegura E. The Markov chain simulation method for generating connected power law random graphs. In: Proc. of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX). 2003.
    [24] Gao L. On inferring autonomous system relationships in the Internet. ACM Trans. on Networking, 2001,9(6):733-745.
    [25] Chang H, Jamin S, Willinger W. An empirical approach to modeling inter-AS traffic matrices. In: Proc. of the Internet Measurement Conf. (IMC). 2005.
    [26] Faloutsos C, Faloutsos M, Faloutsos P. On power-law relationships of the Internet topology. In: Proc. of the ACM SIGCOMM. 1999.
    [27] Albert R, Jeong H, Barabasi AL. Error and attack tolerance in complex networks. Nature, 2000,406:387-482.
    [28] Newman M. Properties of highly clustered networks. Physical Review E, 2003,68:026121.
    [29] Newman M. Power laws, Pareto distributions and Zipf's law. Contemporary Physics, 2005,46:323-351.
    [30] Erd?s P, Rényi A. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 1960,5:17-61.
    [31] Erd?s P, Rényi A. On random graphs. Publicationes Mathematicae, 1959,6:290-297.
    [32] Erd?s P, Rényi A. On the strength of connectedness of a random graph. Acta Mathematica Scientia Hungary, 1961,12:261-267.
    [33] Breitbart Y, Garofalakis M, Rastogi R. Efficiently monitoring bandwidth and latency in IP networks. In: Proc. of the IEEE INFOCOM. 2001.
    [34] Park K, Lee H. On the effectiveness of route-based packet filtering for distributed DoS attack prevention in power-law Internets. In: Proc. of the ACM SIGCOMM. 2001.
    [35] Hethcote HW. The mathematics of infectious diseases. SIAM Review, 2000,42(4):599-653.
    [36] Leveille J. Epidemic spreading in technological networks. Technical Report, HPL-2002-287, HP Laboratories Bristol, 2002.
    [37] Pastor-Satorras R, Vespignani A. Epidemic dynamics and endemic states in complex networks. Physical Review E, 2001, 63(6):066117.
    [38] Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks. Physical Review Letters, 2001,86(14):3200.
    [39] Lloyd AL, May RM. How viruses spread among computers and people. Science, 2001,292:1316?1317.
    [40] Dorogovtsev SN, Mendes JFF. Evolution of networks. Advances in Physics, 2002,51:1079-1187.
    [41] Barabási AL, Bonabeau E. Scale-Free networks. Scientific American, 2003,288:50-59.
    [42] Dorogovtsev SN. Clustering of correlated networks. Physical Review E, 2004,69(2):027104.
    [43] Bollobas B, Riordan OM. Mathematical results on scale-free random graphs. In: Handbook of Graphs and Networks. Berlin: Wiley-VCH, 2003.
    [44] Carlson JM, Doyle J. Complexity and robustness. Proc. of the National Academy of Sciences of the USA, 2002,99(1):2539-2545.
    [45] Bollobas B, Riordan O. Robustness and vulnerability of scale-free random graphs. Internet Math, 2003,1:1-35.
    [46] Holme P, Kim BJ, Yoon CN, Han SK. Attack vulnerability of complex networks. Physical Review E, 2002,65(5):056109.
    [47] Goh KI, Kahang B, Kim D. Spectra and eigenvectors of scale-free networks. Physical Review E, 2001,64(5):1-5.
    [48] Mahadevan P, Krioukov D, Fomenkov M, Huffaker B, Dimitropoulos X, Claffy KC, Vahdat A. Lessons from three views of the Internet topology. Technical Report, CAIDA, 2005.
    [49] Chung F, Lu L. The average distance in a random graph with given expected degrees. Internet Math, 2003,1:91-113.
    [50] Soule A, Nacci A, Leonardi E. How to identify and estimate the largest traffic matrix elements in a dynamic environment. In: Proc. of the ACM SIGMETRICS. 2004.
    [51] Waxman BM. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 1988,6(9):1617-1622.
    [52] Doar M. A better model for generating test networks. In: Proc. of the IEEE GLOBECOM. 1996.
    [53] Calvert KL, Doar M, Zegura E. Modeling Internet topology. IEEE Communications Magazine, 1997,35(6):160-163.
    [54] Zegura EW, Calvert K, Bhattacharjee S. How to model an internetwork. In: Proc. of the IEEE INFOCOM. 1996.
    [55] Winick J, Jamin S. Inet-3.0: Internet topology generator. Technical Report, CSE-TR-456-02, Department of EECS, University of Michigan, 2002.
    [56] Albert R, Barabari AL. Topology of evolving networks: local events and university. Physical Review Letters, 2000, 85(24):5234-5237.
    [57] Medina A, Lakhina A, Matta I, Byers J. BRITE: An approach to universal topology generation. In: Proc. of the IEEE MASCOTS. 2001.
    [58] Bu T, Towsley D. On distinguishing between Internet power-law topology generators. In: Proc. of the IEEE INFOCOM. 2002.
    [59] Park ST, Pennock DM, Giles CL. Comparing static and dynamic measurements and models of the Internet's AS topology. In: Proc. of the IEEE INFOCOM. 2004.
    [60] Zhou S, Mondragon RJ. Accurately modeling the Internet topology. Physical Review E, 2004,70(6):066108.
    [61] Sagy B, Mira G, Avishai W. An incremental super-linear preferential Internet topology model. In: Proc. of the Passive and Active Measurement Workshop (PAM). 2004.
    [62] Aiello W, Chung F, Lu L. A random graph model for massive graphs. In: Proc. of the ACM Symp. on Theory of Computing (STOC). 2000.
    [63] Palmer C, Steffan G. Generating network topologies that obey power laws. In: Proc. of the IEEE GLOBECOM. 2000.
    [64] Wang XF, Li X, Chen GR. Complex Network: Theories and Applications. Beijing: Tsinghua University Press, 2006 (in Chinese).
    [65] Alderson D, Doyle J, Govindan R, Willinger W. Toward an optimization-driven framework for designing and generating realistic internet topologies. In: Proc. of the ACM SIGCOMM. 2003.
    [66] Pansiot J, Grad D. On routes and multicast trees in the Internet. ACM SIGCOMM Computer Communication Review, 1998, 28(1):41-50.
    [67] Magoni D, Pansiot JJ. Internet topology modeler based on map sampling. In: Proc. of the IEEE Symp. on Computers and Communications Conf. (ISCC). 2002.
    [68] Broido A, Claffy KC. Internet topology: Connectivity of IP graphs. In: Proc. of the Int'l Symp. on Convergence of IT and Communication (ITCOM). 2001.
    [69] Fabrikant A, Koutsoupias E, Papadimitriou CH. Heuristically optimized trade-offs: A new paradigm for power laws in the Internet. In: Proc. of the Int'l Colloquium on Automata, Languages and Programming (ICALP). 2002.
    [70] Mei YK. Router-Level topology modeling and assessment [MS. Thesis]. Hong Kong: City University of Hong Kong, 2007.
    Related
    Comments
    Comments
    分享到微博
    Submit
Get Citation

周 苗,杨家海,刘洪波,吴建平. Internet网络拓扑建模.软件学报,2009,20(1):109-123

Copy
Share
Article Metrics
  • Abstract:9693
  • PDF: 14901
  • HTML: 0
  • Cited by: 0
History
  • Received:January 08,2008
  • Revised:May 05,2008
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033157Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063