一种新的因特网拓扑的序列分析方法:dM序列分析方法

摘要

网络拓扑研究的一项重要内容是分析网络拓扑的特征并生成满足这些特征的拓扑图.拓扑图特征的dK序列分析技术是一种系统化的拓扑分析技术,它能够以不同的精度描述拓扑图的特征,随着d的增加,其生成的拓扑图能够在各种重要的拓扑度量方面越来越接近原始拓扑图,因而对因特网拓扑研究具有重要意义.dK序列分析技术的问题在于状态数较多,生成算法复杂,当d>2时没有直接的生成算法.本文提出了一种新的基于邻接图分布的拓扑图特征的序列分析技术:dM序列分析技术.与dK序列分析技术相比,dM序列分析技术具有状态数少、生成算法简单的优势,因此更适合于大规模拓扑图如因特网AS拓扑的研究.%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 dK-series 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 dK-series 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 dM-series analysis technique.The dM-series analysis technique has less states and easier algorithm generation compared with the dK-series analysis technique, so it is more practical when analyzing large scale networks like the Internet AS-level topology.