一种新的因特网拓扑的序列分析方法：dM序列分析方法
收稿日期: 2009-08-28
修回日期: 2009-12-25
网络出版日期: 2010-03-25
基金资助
国家自然科学基金资助项目（60603064）
A New Analysis Technique on the Internet Topology:The dMSeries Analysis Method
Received date: 2009-08-28
Revised date: 2009-12-25
Online published: 2010-03-25
网络拓扑研究的一项重要内容是分析网络拓扑的特征并生成满足这些特征的拓扑图。拓扑图特征的dK序列分析技术是一种系统化的拓扑分析技术，它能够以不同的精度描述拓扑图的特征，随着d的增加，其生成的拓扑图能够在各种重要的拓扑度量方面越来越接近原始拓扑图，因而对因特网拓扑研究具有重要意义。dK序列分析技术的问题在于状态数较多，生成算法复杂，当d>2时没有直接的生成算法。本文提出了一种新的基于邻接图分布的拓扑图特征的序列分析技术：dM序列分析技术。与dK序列分析技术相比，dM序列分析技术具有状态数少、生成算法简单的优势，因此更适合于大规模拓扑图如因特网AS拓扑的研究。
杨国强，窦文华 . 一种新的因特网拓扑的序列分析方法：dM序列分析方法[J]. 计算机工程与科学, 2011 , 33(3) : 1 -6 . DOI: 10.3969/j.issn.1007130X.2011.
It is an important task for the network topology research to analyze the properties of topologies and generate topologies that share the same properties with the original topologies. The dKseries analysis is an efficient technique to analyze the properties of the Internet topology. Increasing the values of the d capture progressively more properties of the original topology are at the cost of more complex states. The drawback of the dKseries is that the states increase fast when d increasess, and also the generation algorithm is too complicate. We present a new series analysis technique based on the neighbor graph distribution, called the dMseries analysis technique. The dMseries analysis technique has less states and easier algorithm generation compared with the dKseries analysis technique, so it is more practical when analyzing large scale networks like the Internet ASlevel topology.
［1］张宇, 张宏莉, 方滨兴. Internet 拓扑建模综述［J］.软件学报,2004,15(8):12201226.
［2］Watts D, Strogatz S. Collective Dynamics of ‘SmallWorld’ Networks［J］. Nature, 1998,393(6684):440442.
［3］Tangmunarunkit H, Govindan R, Jamin S, et al. Network Topology Generators:DegreeBased vs. Structural［J］. ACM SIGCOMM Computer Communication Review, 2002,31(4):147159.
［4］Gkantsidis C, Mihail M, Zegura E. Spectral Analysis of Internet Topologies［C］∥Proc of the IEEE INFOCOM’03,2003:364374.
［5］Krioukov D, Chung F, Claffy K C. The Workshop on Internet Topology (WIT) Report［J］. ACM SIGCOMM Computer Communication Review, 2007,37(1):6973.
［6］Mahadevan P, Krioukov D,Fall K. Systematic Topology Analysis and Generation Using Degree Correlations［C］∥Proc of ACM SIGCOMM,2006:135146.
［7］Mahadevan P, Hubble C, Huffaker B, et al. Orbis: Rescaling Degree Correlations to Generate Annotated Internet Topologies［J］. ACM SIGCOMM Computer Communication Review, 2007,37(4):325336.
［8］The Skitter AS Links Dataset［EB/OL］.［20080510］. http://www.caida.org/data/active/skitter_aslinks_dataset.xml.
［9］Li L, Alderson D, Willinger W, et al. A FirstPrinciples Approach to Understanding the Internet's RouterLevel Topology［C］∥Proc of ACM SIGCOMM’04,2004:314.
［10］The CAIDA AS Relationships Dataset［EB/OL］.［20080510］. http://www.caida.org/data/active/asrelationships/.
［11］University of Oregon RouteViews Project［EB/OL］.［20080510］. http://www.routeviews.org/.
［12］Goh KI, Oh E,Kahng B, et al. Betweenness Centrality Corelation in Social Networks［J］. Physical Review E, 2003,67(12):01710110171012.
［13］Bu T,Towsley D. On Distinguishing Between Internet Power Law Topology Generators［C］∥Proc of the IEEE INFOCOM’02, 2002:638647.
/
| 〈 |
|
〉 |