节点文献

Internet拓扑的社团特性分析及建模

The Analysis and Modeling on Internet Topology’s Community Structure

【作者】 袁韶谦

【导师】 赵海;

【作者基本信息】 东北大学 , 计算机应用技术, 2008, 硕士

【摘要】 自Internet拓扑的幂律特性被发现以后,Internet拓扑复杂性的研究就越来越受到人们的关注,对其宏观拓扑特性的分析与建模是当前的研究热点。近年来该领域取得了长足的发展,发现了许多隐藏的网络特征规律,但仍存在着一些研究空白点,比如,社团结构是许多真实网络都存在着的一种结构,而目前没有针对于Internet拓扑社团结构特性的研究,也没有相关的建模分析。本文采用CAIDA (The Cooperative Association for Internet Data Analysis)提供的海量Internet拓扑数据,对Internet拓扑的社团结构特性进行了分析。首先采用模块度分裂曲线对几种简单网络模型的社团特性进行了分析,发现随机网络所具有的独特社团特性。Internet拓扑的社团结构进行了分析的显示,Internet拓扑的模块度在0.40左右,这表明Internet拓扑也是具有社团结构的网络。而当前流行的Internet拓扑模型的模块度大多小于0.30,表明了这些模型在社团特性上与真实Internet的不符合。对Internet拓扑的社团结构成因的分析发现,处于同一个社团内的AS大多属于相同或者邻近的国家,揭示了地理因素是Internet的社团结构形成的一个重要原因。而AS类型对Internet社团结构划分的影响则比较小。对Internet国家级拓扑的社团分析显示,Internet国家级拓扑的几个主要社团正好对应到世界的几个主要大洲,进一步说明了地理因素对Internet结构的影响。线路开销是建立网络时需要考虑到一个问题,出于降低成本的考虑,邻近地区建立Internet连接的倾向性更强。为此设计了一种基于地理演化的AS级拓扑模型——GeoPFP模型,该模型在建立节点连接时,考虑了地理距离的影响,优先在邻近节点之间建立连接。实际的实验分析表明,该模型在大多数性质上都能重现Internet,并且具有和Internet相接近的模块度,这在某种程度上也验证了本文的结论。相对于当前的模型,GeoPFP模型具有明显的优势,可以进一步的应用于与Internet拓扑有关的研究中。比如可以用来实现更完善的Internet拓扑生成器。而其对于下一代Internet的建设和Internet路由协议的设计也有一定的参考价值及应用意义。

【Abstract】 Since the discover of the power-law relationship in Internet topology, research on the complexity of Internet topology brought more and more people’s concern, the analysis and modeling on Internet topology is a popular topic. There is great achievement in this area in recent years and many unknown topology characteristics have been revealed in recent years. However, there is still some blank in this area, for example, community structure is a common property in many real networks, but there isn’t any research on the community structure of Internet topology, or related modeling method.In this work, the community property of Internet topology is analyzed, on the basis of the mass topology data provided by CAIDA. First, a basic analysis on community property for simple network models using modularity curve shows that random network has a very strange behaviors compared with other simple network models. And the analysis on real Internet topology shows that Internet AS-level topology has a modularity around 0.40, which indicates that Internet is also a network with community structure, while at the same time, most of the popular Internet models’modularity is less than 0.30, indicating their inconsistence with the real Internet.The analysis on the origin of community structure of Internet topology shows that most ASes in the same community belongs to the same country or adjacent countries, which means that geographical consideration is an important cause of the community structure in Internet topology. The influence of AS classes on this property is relatively weak. A further analysis on Internet country-level topology shows that the several communities correspond to the several continents in the world, which further strength our conclusion.Connection cost is important aspect which should be considered when deploying real networks. Because of the consideration to reduce the cost, the probability to establish connections between adjacent areas is relatively large. A new model which has taken geographical location into consideration is introduced to model the evolution of Internet topology. In the new model, which is called GeoPFP model, there is more preference for new nodes to connect with nearby nodes. And the experiment show that the new model is in consistent with the real Internet in most graph properties, and has a similar modularity as Internet, which further proved our conclusion.Compared with current Internet models, GeoPFP model has obvious advantages and can be further used in topology-related researches, such as being used to develop a more precise topology generator. Also, it is significant for the development of next-generation Internet and better routing protocols.

  • 【网络出版投稿人】 东北大学
  • 【网络出版年期】2012年 03期
节点文献中: 

本文链接的文献网络图示:

本文的引文网络