微信服务号

微信订阅号

2025年5月1日 19:59 星期四
首页 > 过刊浏览>2009年第20卷第1期 >109-123
PDF HTML阅读 XML下载 导出引用 引用提醒
Internet网络拓扑建模
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.60473083 (国家自然科学基金)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [70]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    首先概述Internet网络拓扑建模的意义和分类;总结现阶段已发现的主要网络拓扑特性与度量指标;然后分析、讨论自治域级和路由器级的Internet网络拓扑建模与最新的研究成果;最后针对目前拓扑建模中存在的难点和问题给出总结,并展望未来的研究发展方向.

    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.

    参考文献
    [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.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

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

复制
分享
文章指标
  • 点击次数:9709
  • 下载次数: 14984
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2008-01-08
  • 最后修改日期:2008-05-05
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19894302位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号