Internet拓扑建模综述

Internet拓扑建模是在更高层次上开发、利用Internet的基础.Internet拓扑模型研究经历了从随机型到层次型,再到无尺度(scale-free)网络的过程.对包括幂率(power law)在内的多种Internet拓扑特征及其相应度量进行了分析,对现有的拓扑模型、拓扑生成算法以及拓扑生成器进行了全面的综述.最后论述了目前研究中遇到新的问题与挑战,并对今后技术路线进行了总结.     

一种基于幂率的层次型拓扑生成算法HIPL

拓扑建模是网络性能研究的关键技术.层次性和幂率分布是大型网络拓扑结构的两个固有的性质,现有的拓扑模型只反映了其中的某一个性质.将幂率分布规律和层次型拓扑生成算法结合起来,提出了一种基于幂率的层次型网络拓扑生成算法HIPL.实验通过对群集系数、直径、平均度数等拓扑参数的比较,表明了HIPL的可行性和有效性.     

Skitter与Ark探测架构下AS级Internet拓扑分析

选取CAIDA授权的AS级2003年1月—2007年12月的Skitter数据及2008年1月—12月的Ark数据进行层层深入的对比分析,以说明Internet拓扑探测架构的改变对拓扑探测结果的影响。首先统计了Skitter及Ark架构下AS级Internet拓扑的多种宏观特征,分析了Skitter与Ark在各特征值上的异同,进而分析了网络的幂率特征与网络连通性以及拓扑核数的演化,指出幂率性质以及高聚类性质在Internet拓扑中是真实存在的,不随探测方式的改变而消失。     

一种基于AS的Internet拓扑模型

分析Internet中AS的变化规律,提出一种拓扑模型。根据对Internct拓扑变化的统计计算出模型参数。仿真结果表明,该模型生成拓扑的特性比BA模型更接近Internet。     

基于拓扑势的网络拓扑建模方法

针对现有拓扑建模研究中层次型模型不满足幂率分布规律的问题,提出一种基于节点拓扑势与幂率特性的层次化网络拓扑建模方法,给出拓扑生成算法PPHM。通过计算拓扑势实现网络节点的分层,能准确发现网络中的重要连接。对平均最短路径长度等拓扑参数的比较结果证明了该方法的有效性。     

基于拓扑势的网络拓扑建模方法

针对现有拓扑建模研究中层次型模型不满足幂率分布规律的问题,提出一种基于节点拓扑势与幂率特性的层次化网络拓扑建模方法,给出拓扑生成算法PPHM。通过计算拓扑势实现网络节点的分层,能准确发现网络中的重要连接。对平均最短路径长度等拓扑参数的比较结果证明了该方法的有效性。     

基于复杂网络的 Internet 流量分析

基于复杂网络理论对 Internet 网络结构进行分析,模拟 Internet 网络中选择服务器的过程,建立一个基于距离和流量的 Internet 自组织网络结构模型(FDM).通过仿真Internet 网络数据传输过程,分析比较 FDM 与 BBV 模型的丢包率,研究 Interact 网络中心连接节点的缓存器容量、...     

Internet AS幂律建模及其参数估计

为了精确建模Internet自治系统层面上的拓扑结构,提出了基于最小节点度和最大节点度的拓扑幂律模型及其参数估计新算法。针对Internet自治系统层拓扑实际测量数据,利用新算法对拓扑幂律模型中的最小节点度、最大节点度以及标度参数进行计算。实验结果表明,由新算法估计的Internet自治系统层拓扑幂律模型的最小节点度为1,最大节点度随网络规模的增大而增大,标度参数的误差与使用最大然似估计法误差一样均非常小,约为2.25。     

复杂网络理论在Internet拓扑特性分析中的应用

利用复杂网络理论对Intemet进行研究,探索Internet复杂系统的现象,揭示这些现象背后的起源、不变特性以及动态规律,已成为计算机科学领域所关心的重要问题之一。介绍了复杂网络的研究简史,研究的主要内容、方法与工具,以及复杂网络的基本概念和特征量,并对目前在Intemet拓扑特性分析研究方面的研究成果及经验结果进行了归纳总结,同时给出了复杂网络理论在Intemet研究中的发展方向。     

Internet自治系统级拓扑复杂网络特征分析与验证

为深入理解和认清Internet复杂巨系统的不变特征和动态规律,分析研究Internet自治系统级拓扑的复杂网络特征,给出幂律分布和无标度条件的数学描述以及寻找两者之间的关系,分析小世界网络的两个重要特征,即较短平均路径长度和较大聚集系数,讨论匹配性问题和富人俱乐部现象,基于上述理论结果和BGP经验数据计算自治系统级拓扑的最大节点度、平均节点度、聚集系数和最大团数,发现自治系统级拓扑具有幂律分布、异配性以及富人俱乐部现象等复杂网络特征,得到幂指数、匹配系数以及富人俱乐部系数等重要特征参数。     

Internet网络的关联性研究

网络的关联性在Internet网络拓扑的研究中具有重要作用.目前的研究分别集中于聚集特性、mixing特性和rich-club现象.深入研究了这3种网络关联特征:在指出刻画网络聚集特性的两个衡量参数——平均聚集系数与聚集系数可能存在不一致性的同时,发现AS(autonomoussystem)网络的局部聚集系数和节点度高度相关;揭示并验证了PFP(positive-feedbackpreference)模型中rich-club现象的内在形成机制.在此基础上,对这些网络关联特征之间的关联关系进行了研究.     

Internet AS拓扑的“73/27”规律

为了深入理解和认清Internet AS拓扑中节点度的分配规律,提出适合Internet AS拓扑的幂律模型,利用该模型推导Internet AS拓扑中最富有节点数占网络总节点数的比例与这些最富有节点所拥有的节点度数占网络节点总度数的比例之间的关系,分析研究幂律指数和最大节点度等拓扑参数对该比例关系的影响,通过数值分析发现Internet AS拓扑中27%的最富有节点拥有约73%的节点度数（简称为“73/27”规律）,基于Internet AS拓扑经验数据对上述结果进行验证分析,结果表明该幂律模型对Internet AS拓扑是有效的,Internet AS拓扑存在“73/27”规律。     

一种遵循幂率分布的网络拓扑生成算法PLOD+*

拓扑建模是进行网络性能研究的基础。PLOD是一种基于幂率的网络拓扑生成算法,但该算法不能保证生成拓扑图的连通性,且存在“出度贷款过剩”现象。对PLOD算法进行了改进,在节点连接时添加了连通性检测,并对出度大的节点实行优先连接,较好地解决了PLOD算法存在的问题。实验结果表明了PLOD+算法的可行性和有效性。     

Internet建模的关键:研究AS间路由器级连接

AS-域内路由器双层建模方式是目前构建Internet规模的路由器级网络模型的最优方案,而该方案需要建模者首先了解域间路由器级连接的特点。指出AS类型对域间路由器级连接具有较大影响,通过定义域间参数映射,利用现网数据对域间参数映射进行了现象学分析,获取了不同类型AS相关参数的分布函数,解决了双层模型的组合问题。在此基础上,进一步对Internet建模尚需解决的若干问题进行了讨论。     

一种启发式Internet路由器级拓扑建模方法

针对Internet网络拓扑研究现状,总结了当前Internet所具有的一系列重要属性特征,并对现有基于度分布的网络拓扑模型进行了分析,指出了这些模型在表述Internet路由器级网络时存在的局限性。从实际路由器网络制约因素出发,引入了构建松散网络核心的限制条件和保留节点度属性的重连机制,在增长—优先连接机制的基础上提出了一种启发式非线性优先连接（HNLPA）拓扑建模算法。实验表明,本算法构造的拓扑能够较好地描述Internet路由器级网络特征。     

TF法则嵌入机制的动态局域加权网络模型

分析目前加权局域世界演化模型已取得的研究成果,在其基础上进行综合改进与完善,提出一种TF法则嵌入机制的动态局域加权网络模型(TF-DLW),该模型在演化过程中融入了TF法则和BBV权值动态演化机制。平均场理论和计算机模拟仿真均验证了该模型强度分布具有幂率特性。同时,计算机仿真中强度分布、边权分布以及度分布均出现了幂率肥尾现象,三角形结构的嵌入使得模型能更平稳地调节聚类系数的大小。实验表明,TF-DLW演化模型继承了许多复杂模型具有的幂率分布特性,而且可以快速平稳地调控簇系数的范围大小。     

Internet路由级拓扑的自相似分形统计

由于多角度多度量的统计方法存在种种问题,提出了通过分形维数从整体上刻画互联网拓扑性质。以传统分形理论为基础,结合互联网拓扑所具有的自相似性质,给出网络拓扑维数的相关概念,并通过网络拓扑与欧氏空间的映射关系,对拓扑维数进行了深入的解释。分析了理想分形拓扑的迭代膨胀过程,指出简单分形方法的不足,并进一步给出加权分形的相关定义及计算方法。通过统计互联网路由级拓扑的几个主要特征量,分析了拓扑维数与传统统计度量方法的关系,说明了拓扑维数在适用于统计观察互联网宏观拓扑的整体特性方面的作用。     

考虑故障排除率和引入率的软件可靠性建模

软件测试中排错过程的故障排除率并不是100％的,并且由于检测到的尚未被排除的故障影响还会引入新的故障,即存在故障排除率和故障引入率,两者是具有不同的下降趋势的减函数.针对上述问题,提出一种新的非齐次泊松过程软件可靠性增长模型,考虑了随时间变化的故障排除率函数和故障引入率函数.利用一组公开发表的包含故障检测数和故障排除数的软件失效数据集进行仿真与验证,实验结果表明,改进模型具有更好的拟合效果和预测能力.     

Internet建模技术研究和实现

Internet建模是研究Internet网络传输技术的基础,分析了各种建模方法,比较了不同建模方法所产生的拓扑图,并给出能够产生特定性质拓扑图的有效方法及Transit-Stub方法的具体实现步骤。     

Internet拓扑抽样探测的偏向性研究

利用traceroute探测网络拓扑结构是研究Internet拓扑属性的主要方法,然而由于这种方法的局限性,使得该方法对正确分析Internet拓扑属性产生很大影响。采用几种网络模型来分析traceroute探测得到的抽样网络属性的偏向性问题,包括节点发现率、边发现率和度分布等。同时针对网络探测参数设置的局限性,还定性分析了在总体抽样粒度不变的情况下,如何设定探测源和目标节点的密度才能达到优化探测网络特征属性的目的。