微信服务号

微信订阅号

2025年4月4日 4:11 星期五
首页 > 过刊浏览>2005年第16卷第5期 >846-856
PDF HTML阅读 XML下载 导出引用 引用提醒
大型ISP网络拓扑多点测量及其特征分析实例
作者:
基金项目:

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


An Example of Analyzing the Characteristics of a Large Scale ISP Topology Measured from Multiple Vantage Points
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [31]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    深入了解Internet拓扑的结构性质有利于更好地设计和发展Internet.由于Internet规模巨大,以及获得完整的路由器级Internet拓扑方面的困难,目前无法研究整个路由器级Internet拓扑.因此,分别研究每个国家级或跨国因特网服务供应商(Internet service provider,简称ISP)网络拓扑结构成为了解Internet拓扑特征的一种可选方法.以中国教育科研网为例,简要描述了多点测量其路由器级拓扑结构的测量结果.分析了该实例拓扑图的节点度分布特征、较大特征值的有关性质以及谱密度分布特征.分析了该实例拓扑图的无符号拉普拉斯谱(SLS)、规格化拉普拉斯谱(NLS)以及群集系数等度量特征.分析结果表明,大型ISP拓扑确实具有某些幂律特征;不同于自治系统级拓扑的情形,对ISP拓扑的节点度补累积分布来说,幂律分布未必拟合得最好;ISP拓扑是一种无标度图,但不符合Barabasi-Albert(BA)生长模型;SLS和NLS具有区分不同的路由器级拓扑结构的能力;Internet路由器级拓扑的发展可能遵循一种不同于BA模型的生长过程.

    Abstract:

    A detailed understanding of the structural properties of Internet topology will benefit the further design and development of the Internet. It seems infeasible to study the whole Internet at router level due to its extremely large size and the difficulty in obtaining a whole topology at this level. Studying each national or continental Internet service provider (ISP) topology individually becomes an alternative method for this goal. In this paper, the measured China Education and Research Network topology, a nationwide ISP topology, is basically taken as an example. The results of mapping the topology from multiple vantage points are briefly presented. The properties of the degree distribution, large eigenvalues, and the spectral density of the measured topology graphs are analyzed. The characteristics of the signless Laplacian spectra (SLS), the normalized Laplacian spectra (NLS), and the clustering coefficients of the measured graphs are also presented. The results suggest that some power laws indeed hold in some large-scale ISP topologies; in contrast to the case of autonomous system level topologies, the power law fit is not the best choice for some ISP topologies in terms of the complementary cumulative distribution function of the degree; some real ISP topologies are a kind of scale-free graphs which are not consistent with the Barabási-Albert (BA) growth model; router level topologies are distinguishable in terms of the SLS or the NLS; router level Internet topology may have developed over time following a different set of growth processes from those of the BA model.

    参考文献
    [1]Floyd S, Kohler E. Internet research needs better models. ACM SIGCOMM Computer Communication Review, 2003,33(1)29-34.
    [2]Jiang Y, Fang BX, Hu MZ, Zhang HL, Yun XC. A distributed architecture for Internet router level topology discovering systems.In: Fan PZ, Shen H, eds. Proc. of the 4th Int'l Conf. on Parallel and Distributed Computing, Applications and Technologies(PDCAT'2003). New York: IEEE Press, 2003.47-51.
    [3]Jiang Y, Fang BX, Hu MZ. Mapping router-level Internet topology from multiple vantage points. Telecommunications Science,2004,20(9): 12-17 (in Chinese with English abstract).
    [4]Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology. ACM SIGCOMM Computer Communication Review, 1999,29(4):251-262.
    [5]Mitzenmacher M. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 2003,1(2):226-251.
    [6]Chen Q, Chang H, Govindan R, Jamin S, Shenker S J, Willinger W. The origin of power laws in Internet topologies revisited. In:Proc. of the IEEE INFOCOM 2002. New York: IEEE Press, 2002. 608-617.
    [7]Farkas IJ, Derenyi I, Barabasi A, Vicsek T. Spectra of ‘real-world' graphs: Beyond the semicircle law. Physical Review E, 2001,64(2):1-12.
    [8]Albert R, Barabasi A. Statistical mechanics of complex networks. Reviews of Modern Physics, 2002,74(1):47-97.
    [9]Dam E, Haemers WH. Which graphs are determined by their spectrum? Linear Algebra and its Applications, 2003,373:241-272.
    [10]Magoni D, Pansiot J-J. Analysis of the autonomous system network topology. ACM Computer Communication Review, 2001,31(3):26-37.
    [11]Vukadinovic D, Huang P, Erlebach T. On the spectrum and structure of Internet topology graphs. In: Unger H, Bohme T, Mikler A,eds. Proc. of the Innovative Internet Computing Systems (I2CS). LNCS 2346, Berlin: Springer-Verlag, 2002. 83-95.
    [12]Gkantsidis C, Mihail M, Zegura E. Spectral analysis of Internet topologies. In: Proc. of the IEEE INFOCOM 2003. New York:IEEE Press, 2003. 364-374.
    [13]Medina A, Matta I, Byers J. On the origin of power laws in Internet topologies. ACM SIGCOMM Computer Communication Review, 2000,30(2): 18-28.
    [14]Siganos G, Faloutsos M, Faloutsos P, Faloutsos C. Power laws and the AS-level Internet topology. IEEE/ACM Trans. on Networking, 2003,11 (4):514-524.
    [15]Carlson JM, Doyle J. Highly optimized tolerance: A mechanism for power laws in designed systems. Physical Review E, 1999,60(2):1412-1427.
    [16]Fabrikant A, Koutsoupias E, Papadimitriou CH. Heuristically optimized trade-offs: A new paradigm for power laws in the Internet.In: Widmayer P, Triguero F, Morales R, Hennessy M, Eidenbenz S, Conejo R, eds. Proc. of the ICALP. LNCS 2380, Berlin:Springer-Verlag, 2002. 110-122.
    [17]Li L, Alderson D, Willinger W, Doyle J. A first-principles approach to understanding the Internet's router-level topology. ACM SIGCOMM Computer Communications Review, 2004,34(4):3-14.
    [18]Pansiot J, Grad D. On routes and multicast trees in the Internet. ACM SIGCOMM Computer Communication Review, 1998,28(1):41-50.
    [19]Broido A, Claffy KC. Internet topology: Connectivity of IP graphs. In: Fahmy S, Park K, eds. Scalability and Traffic Control in IP Networks (Proc. of the SPIE ITCom Vol. #4526). Washington: SPIE Press, 2001. 172-187.
    [20]Spring N, Mahajan R, Wetherall D. Measuring ISP topologies with rocketfuel. ACM SIGCOMM Computer Communication Review, 2002,32(4):133-145.
    [21]Magoni D, Pansiot J-J. Internet topology modeler based on map sampling. In: Proc. of the 7th IEEE Symp. on Computers and Communications (ISCC 02). New York: IEEE Press, 2002. 1021-1027.
    [22]Jiang Y, Hu MZ, Fang BX, Zhang HL. An Internet router level topology automatically discovering system. Journal of China Institute of Communications, 2002,23(12):54-62 (in Chinese with English abstract).
    [23]Chou H. A note on power laws of Internet topology. 2000. http://arxiv.org/abs/cs.NI/0012019
    [24]Mihail M, Papadimitriou CH. On the eigenvalue power law. In: Rolim JDP, Vadhan S, eds. Proc. of the Randomization and Approximation Techniques: 6th Int'l Workshop (Random 2002). LNCS 2483, Berlin: Springer-Verlag, 2002.254-262.
    [25]Watts D, Strogatz S. Collective dynamics of ‘small-world' networks. Nature, 1998,393(6684):440-442.
    [26]CERNET Topology. 2003. http://www.edu.cn/20010101/21585.shtml
    [27]Lakhina A, Byers JW, Crovella M, Xie P. Sampling biases in IP topology measurements. In: Proc. of the IEEE INFOCOM 2003.New York: IEEE Press, 2003. 332-341.
    [28]Mehta ML. Random Matrices. 2nd ed., New York: Academic Press, 1991.
    [29]Goh KI, Kahang B, Kim D. Spectra and eigenvectors of scale-free networks. Physical Review E, 2001,64(5):1-5.
    [30]姜誉,方滨兴,胡铭曾.多点测量Internet路由器级拓扑.电信科学,2004,20(9):12-17.
    [31]姜誉,胡铭曾,方滨兴,张宏莉.一个Internet路由器级拓扑自动发现系统.通信学报,2002,23(12):54-62.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

姜誉,方滨兴,胡铭曾,何仁清.大型ISP网络拓扑多点测量及其特征分析实例.软件学报,2005,16(5):846-856

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

京公网安备 11040202500063号