论文部分内容阅读
Internet作为一个典型的复杂网络实例,对其宏观拓扑结构的特征分析及建模研究是目前研究的热点问题,受到学术界广泛关注。近年来人们在该领域的研究取得了长足的进展,尤其是在自治系统层面(autonomous system, AS-level)。但是由于路由级Internet拓扑结构的复杂性,人们至今也未能对其有个清楚的认识,在这个看似混沌的网络之中还蕴涵着一些不为人知的规律有待进行深入的挖掘。对Internet路由级宏观拓扑结构的层次分析以及建模研究,可以帮助人们更好地理解Internet基础架构的特点,这对下-代Internet的设计,及与Internet有关的协议体系的研究都将产生巨大的促进作用,因此具有重要的意义。本文首先分析了Internet路由级拓扑的k-核结构,通过对CAIDA2007年5月各监测点的实测数据进行横向分析,发现各监测点的k-核结构与整体相似,说明采样偏见问题对Internet的k-核结构影响不大;继续对CAIDA riesling监测点在2006年12个月的采样数据进行纵向分析,结果表明Internet的k-核结构受时间演化的影响很小,只有网络拓扑核数的大小在变,而各核中节点分布的规律是不变的。在此基础上,定性定量地分析了节点的度值与核数的关系,实验证明,这两者之间并没有明显的联系。其次,本文对Internet路由级拓扑结构的层次特征进行了详细的分析,以k-核解析作为主要分析手段,通过对CAIDA实测数据的分析,表明Internet路由级拓扑具有明显的层次结构:从最高核开始,节点由高核到低核,由内层至外层分布,在最内层,节点集中在有限的几个网段地址上,慢慢向外层发散,网络分布越来越广,节点度分布的幂率性体现越来越明显,至最外层,节点数达到最多,分布的网段地址也达到最广,幂率性体现最明显。再次,在k-核解析的基础上研究了Internet路由级拓扑的分形特征。通过对CAIDA实测数据各核内的度分布、度相关性以及聚集性等主要特征量的分析,发现随着网络由外到内的逐层剪切,不仅度分布,而且聚类性质以及相关结构也被保留了下来。这意味着一种对逐渐趋于网络中心的区域的全局的自相似性,以及根据网络中心性定义的Internet的任意区域都有和整个网络相同的性质的一种结构。进一步对各核拓扑图分别进行谱密度-特征值分布分析以及无符号拉普拉斯谱(SLS)分布分析,发现各核分析结果表现出高度的一致性,从另一方面证明了Internet拓扑结构具有自相似性,从而说明了Internet路由级拓扑具有分形特征。接下来,对Internet路由级拓扑的可视化进行了研究。首先提出了一个基于k-核解析的算法:基于节点的核数由内核至外核逐层演化的算法。并以CAIDA Riesling监测点在2007年5月份的Internet路由级拓扑测量数据为例,描绘了Internet的可视化结果。从可视化结果中可以看出,该算法在描绘Internet拓扑的层次性演化上是比较突出的,但是这一算法没有考虑最高核有几个连通成分的情况。因此,接下来,对这一算法进行了改进,并以CAIDA2007年5月份的路由级拓扑数据为例,描绘了Internet的可视化结果,结果表明该算法可以适应最高核中含有多个连通成分的网络,演化的结果突出了Internet路由级拓扑的某些特征,如聚类特性以及社团特性。通过对两种算法的时间复杂度的分析,表明这两种算法运行时间较短,适合巨大网络的可视化。最后,通过对各层中节点的分布分析以及节点的高层连接分布分析,提出了一个基于k-核解析的Internet路由级拓扑的层次模型并实现了该模型。对模型的分析表明,该模型在大多数性质上都能重现Internet,并且具有和Internet相接近的拓扑核数。实验结果表明,与传统的经典模型相比,本文模型在满足幂率分布的前提下,充分体现了Internet路由级拓扑的层次性。