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

网络拓扑研究的一项重要内容是分析网络拓扑的特征并生成满足这些特征的拓扑图。拓扑图特征的dK序列分析技术是一种系统化的拓扑分析技术,它能够以不同的精度描述拓扑图的特征,随着d的增加,其生成的拓扑图能够在各种重要的拓扑度量方面越来越接近原始拓扑图,因而对因特网拓扑研究具有重要意义。dK序列分析技术的问题在于状态数较多,生成算法复杂,当d>2时没有直接的生成算法。本文提出了一种新的基于邻接图分布的拓扑图特征的序列分析技术:dM序列分析技术。与dK序列分析技术相比,dM序列分析技术具有状态数少、生成算法简单的优势,因此更适合于大规模拓扑图如因特网AS拓扑的研究。     

因特网拓扑特征之间的关联性研究

研究拓扑特征之间的关联性对于简化拓扑建模具有重要的意义。dK特征序列理论上能够计算得到所有的网络拓扑特征,因此可以用来进行拓扑特征的关联性研究。在分析dK序列定义的基础上,推导出一些重要的网络拓扑特征与dK序列之间的关系,这些关系可以用来简化拓扑图特征比较,因此有助于减少因特网拓扑建模研究的模型验证部分的工作量。     

因特网AS级拓扑测量和分析的进展

测量和分析因特网AS级拓扑是研究因特网宏观特征和选路行为的基本手段。概述了两种测量AS级拓扑的方法,即从包含BGP选路信息的数据中发现AS级拓扑和从traceroute测量数据生成AS级拓扑;对比了不同测量数据的涵义和完整性;综述了多种分析因特网拓扑特性的测度;讨论了AS商业关系及相关选路行为的研究现状;给出了当前面临的技术挑战。     

一种计算因特网AS拓扑的最短路径的快速算法

最短路径是因特网AS(autonomous system)拓扑的一个重要特征,AS间的路由路径一般是AS之间的最短路径.因特网服务提供商之间复杂的商业关系导致AS之间存在复杂的路由关系,从而影响AS路由路径的选择,因此在计算AS拓扑中最短路径时需要考虑AS间的路由关系.提出了一种计算AS拓扑中最短路径的算法,算法基于无向图的宽度优先最短路径算法,时间复杂度为O(nm),这里n和m分别为拓扑图中节点和边的个数.通过实验发现,与现有的计算AS拓扑最短路径的时间复杂度为O(n3)的算法相比,该算法在实现同样精确度的前提下大幅缩短了计算时间.     

大型ISP网络拓扑多点测量及其特征分析实例

深入了解Internet拓扑的结构性质有利于更好地设计和发展Internet.由于Internet规模巨大,以及获得完整的路由器级Internet拓扑方面的困难,目前无法研究整个路由器级Internet拓扑.因此,分别研究每个国家级或跨国因特网服务供应商(Internet service provider,简称ISP)网络拓扑结构成为了解Internet拓扑特征的一种可选方法.以中国教育科研网为例,简要描述了多点测量其路由器级拓扑结构的测量结果.分析了该实例拓扑图的节点度分布特征、较大特征值的有关性质以及谱密度分布特征.分析了该实例拓扑图的无符号拉普拉斯谱(SLS)、规格化拉普拉斯谱(NLS)以及群集系数等度量特征.分析结果表明,大型ISP拓扑确实具有某些幂律特征;不同于自治系统级拓扑的情形,对ISP拓扑的节点度补累积分布来说,幂律分布未必拟合得最好;ISP拓扑是一种无标度图,但不符合Barabasi-Albert(BA)生长模型;SLS和NLS具有区分不同的路由器级拓扑结构的能力;Internet路由器级拓扑的发展可能遵循一种不同于BA模型的生长过程.     

PLDA：AS级的Internet拓扑生成算法

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

生成Internet As级拓扑图的Core-Tree算法研究

Internet拓扑图为大范围开发、利用Internet提供了一个有力的工具。InternetAs级拓扑图在自治系统的层次上刻画Internet特征,它在当前很多领域有着广泛的应用。论文提出了一种生成InternetAs级拓扑图的Core-Tree(C-T)算法,它生成具有核心网络和树形拓扑两层结构的As级拓扑图,生成图在结点度分布、树大小分布以及树深度分布等方面比较符合Internet特征。     

Internet自治系统级拓扑发现系统的研究与实现

Internet由多个自治系统相互连接而成,AS间的互联结构体现了Internet的宏观结构。研究AS间的连接关系可以辅助分析网络特性。该文研究了Internet AS级拓扑发现,实现了一个Internet AS级拓扑发现系统。该系统分析BGP路由表得到Internet AS级拓扑并直观显示出来。分析了AS级拓扑的度分布属性,分析结果显示生成的拓扑具有幂律分布特性。     

面向二维工程CAD图的拓扑完整性校验算法

拓扑信息是工程CAD图的核心,其完整性直接影响着工程设计的效率和质量.针对二维异构工程CAD图的拓扑完整性认证问题,提出一种基于半脆弱数字水印技术的通用拓扑校验算法.首先根据对象间的连接关系构造拓扑图,并对各对象进行统一编码,实现异构图纸拓扑关系的统一描述;然后根据拓扑图建立对应的拉普拉斯矩阵,利用拉普拉斯谱计算各对象的拓扑特征值;最后将拓扑特征值嵌入到各对象的几何不变量中.该算法通过比较提取的特征值序列与对象当前的拓扑特征值来验证其拓扑完整性.理论分析和实验结果表明,文中算法对于全局和局部相似性变换、拷贝、镜像和文件格式转换等非恶意操作具有较强的鲁棒性,同时对于各种恶意拓扑攻击具有精确的定位能力,可以广泛应用于各种工程CAD领域.     

因特网AS级拓扑的健壮性测度与健壮性演化

以自治系统(autonomous system,AS)为基本组成单元的域间路由系统是因特网(Internet)的核心组成部分,研究Internet AS级拓扑的健壮性对于整个Internet的健壮性设计具有重要意义.2003年的北美停电事故与2006年、2010年的台湾地震表明,当今Internet的健壮性仍亟待增强.本文结合基本的拓扑理论与实际的路由策略约束,利用Internet AS级拓扑的层次特性,从"单个AS"和"全局拓扑"两个不同的层面研究AS级拓扑的健壮性测度与健壮性演化:1)提出了对单个AS的健壮性测度的方法;2)对全局AS级拓扑的健壮性测度提出了k容错模型---任意k个AS级的节点/链路故障不影响任何其他两个AS之间的连通性;3)基于健壮性测度方法和k容错模型,提出了健壮性演化的机制与方法.对当今Internet AS级拓扑的统计分析表明:1)25.8%的AS节点还不能承受1个AS级的链路故障,26.4%的AS节点还不能承受1个AS节点故障;2)将现有的AS级拓扑演化为k容错拓扑不仅能保证任意节点对之间可达性的k容错,在故障数超过k的情况下,k容错拓扑的健壮性也显著优于原拓扑.