AS级Internet拓扑幂律和节点时效分析

Internet拓扑,尤其是AS级拓扑,是目前研究的热点问题.研究Internet拓扑的演化趋势,可以更好地了解网络的内在连接机制.基于CAIDA项目授权的海量数据(数据采集时间为2004年1月至2008年6月),首先介绍了必要的基本概念,然后给出了CCDF(d)-degree幂律分析、degree-rank幂律分析、节点时效分析.结果表明,随着网络拓扑结构的演化,AS级Internet的高度值节点部分较为稳定,保持了网络的聚集性与幂律性,但这部分节点随时间变化逐渐丧失有效连接,网络拓扑呈缓慢均匀化趋势.     

AS级Internet拓扑度和连通性演化分析

Internet拓扑,尤其是AS级拓扑,是目前研究的热点。研究Internet拓扑的演化趋势,可以更好地了解网络的内在连接机制。该项研究基于CAIDA项目授权的海量数据,数据采集时间为2004年1月至2008年6月。首先介绍了必要的基本概念,然后给出了节点平均度、最大节点度值、高度值节点平均度、富人俱乐部连通性和聚集系数的演化分析。研究发现,度值较高的节点,其影响力随时间变化逐渐下降,高度值节点之间的连接也逐渐减少,但网络整体上仍表现出明显的富人俱乐部性质和聚集性。     

中国AS级拓扑测量与分析

为描绘中国自治域(Autonomous Systems,AS)级拓扑图景,文中运用综合集成的思想来考察不同拓扑数据之间在数据本身和统计特征上的差异.首先,采用基于BGP、基于traceroute和基于IRR的方法从不同数据源获取了拓扑快照和十年间历史.其次,对快照进行基于集合运算的分组比较,并得到了一幅较完整可信的图.接着,从生灭过程角度,分析三类增长机制,指出了‘灭’过程的缺失.然后,运用复杂网络特征化方法,比较了三幅图的特征及显著性,发现平均度主导了多数差异,并指出有关Rich-Club现象的争议根源之一在于数据差异.最后,给出了特征演化的四点观察,包括相关模型中未能重演的平均度增长现象.     

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

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

SOAST-1：一种综合优化的AS级拓扑推理算法

网络拓扑推理是网络管理系统的基本功能之一，AS级拓扑推理是其重点和难点。本文概括了目前已提出的，基于路径和基于Traceroute的两类AS级拓扑推理算法；针对它们的优缺点，提出了一种综合优化的AS级拓扑推理算法：SOAST-1。SOAST-1以BGP路由表作为路由信息的主要来源，以Traceroute探测作为辅助手段，综合了上述两类AS级拓扑推理算法的优点。算法分析和实际运行结果表明SOAST-1算法能够取得良好效果。     

因特网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容错拓扑的健壮性也显著优于原拓扑.     

面向AS级动态拓扑的改进PFP模型

针对传统PFP模型不能很好模拟Internet动态演化的问题,提出面向自治系统(AS)级动态拓扑的改进PFP模型。改进模型充分考虑Internet中AS节点的消亡与连接边的相应连接补偿,符合Internet拓扑成长和演化过程,生成的Internet拓扑图与实际Internet具有更大相似度。实验结果表明,改进模型能较好满足幂律分布和小世界特性,更适合于Internet建模。     

复合型路由器级拓扑模型

针对HOT模型的路由器级拓扑在大规模节点下的不足,通过结合自治域级拓扑和路由器级拓扑两种方法,实现了一种复合型Internet路由器级拓扑模型A2R。A2R模型仅依靠路由器规模完成网络拓扑图,解决了自治域拓扑间商业关系推测依靠BGP表的问题,以及自治域间路由连接的问题。实验证明A2R拓扑模型在大规模节点下比其他路由器级拓扑模型拥有更好的性能。     

低冗余主动测量IP级Internet拓扑的一种数据修正方法

Internet拓扑的研究对于网络的应用与发展具有重要意义.由于交叉路由的存在,目前主动测量Internet拓扑大多采用多源点高冗余探测的方法,以发现单探测点情况下相对隐藏的链路.为降低探测难度与代价,避免由架设多探测点所带来的高度复杂性及重复性,给出一种针对单点测量数据的修正方法.基于授权的海量实测数据,提取隐藏链路的多核连接特征,使产生的测量结果更完整.实验表明,该方法可以大幅提高单点测量Internet拓扑的精确性,从而增强低冗余测量数据的可用性.     

基于最短路径树覆盖的AS拓扑监测点部署方法*

面向互联网AS级拓扑监测应用,提出了一种基于最短路径树SPT覆盖的算法,用于选择部署最少的监测点,发现尽量完整的AS拓扑。该算法求出所有顶点的最短路径树,按照启发式策略选择最小的顶点集合,使集合中节点的最短路径树可以覆盖全图的边。采用CAIDA AS -links的数据对算法进行验证,SPT算法选择了750个左右的监测点,即可发现互联网中16 500多个AS之间（约30 000条左右）的链路。与随机选择节点进行覆盖的方法相比,该方法选择的监测点数目减少了近37.5%。     

AS关系标注的因特网拓扑图的dK序列分析技术

拓扑特征分析和拓扑图生成是因特网拓扑研究的一个重要研究方向.dK特征序列被证明是一种有效的系统化拓扑特征分析方法,2K图已经能够在各种重要的拓扑度量方面与实际因特网拓扑图保持一致.在使用dK特征序列分析因特网拓扑时是用无向图来对因特网拓扑进行抽象的,然而对于自治系统(AS)级拓扑,由于AS之间存在复杂的商业关系,使用AS关系标注的拓扑图才能更精确地描述AS级拓扑特征.对dK特征序列进行了改进,提出了能够分析AS关系标注的拓扑图的dK'特征序列,并给出了生成满足指定2K'特征的拓扑图的算法.分析实验结果发现,2K'特征已经能够描述AS关系标注的拓扑图的各种重要特征.     

IPv6 AS级Internet抗毁性研究

随着互联网和物联网的飞速发展,通信协议从IPv4过渡到IPv6已是必然趋势。采集了CAIDA Ark项目的最新数据(时间为2014年6月),通过对IPv6 AS级Internet建模,验证了该网络所具有的小世界和无标度特性。在分析Internet结构及常用抗毁性测度的基础上,提出了IPv6 AS级Internet的抗毁性测度指标和抗毁性实验方法。实验结果表明,在不同的攻击策略下,网络具有鲁棒且脆弱的特性,在遭到基于度的蓄意攻击时,网络抗毁性最差,同时也表明构建的抗毁性测度可以很好地表征Internet的抗毁性水平。     

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

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

互联网拓扑测量技术与工程实践

互联网拓扑测量是网络空间测绘的重要手段之一,相关技术与平台已经日趋成熟。首先介绍当前互联网拓扑测量技术与平台;然后介绍一个基于虚拟专用服务器的拓扑测量系统VTopo;最后,给出一次地区互联网拓扑测量试验,结果表明VTopo独立发现大量拓扑信息,与CAIDA Ark数据集具有很大的互补性。     

互联网AS拓扑的结构与连通性研究

基于BGP协议的域间路由系统是Internet的核心基础设施。研究域间路由系统在自治系统AS级的拓扑结构,深入理解并揭示AS拓扑的结构及连通性方面的特性,对于提高互联网路由系统的安全性、健壮性以及性能都具有重要的指导意义。AS之间的商业关系模型是互联网域间路由系统的基本模型之一,是AS拓扑研究的基础。受商业关系的约束,AS拓扑的结构与连通性呈现出了与普通无向图或有向图所不具备的特性:层次结构特性与AS路径的无谷底约束。本文提出了针对AS拓扑的层次划分算法,对AS拓扑的连通性做了深入研究,分析并验证了顶级AS的全互联结构,并进一步阐述了从宏观上对单个AS的连通性的评估方法。     

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

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

路由级Internet宏拓扑结构的谱密度分析

针对路由级Internet宏拓扑结构进行了谱密度分布分析与无符号拉普拉斯谱(SLS)分布分析.首先通过对拓扑结构各异的5种采样拓扑图,分别进行谱密度-特征值分布分析,发现5组分析结果表现出高度的一致性,证明了Internet拓扑结构的自相似性,也证明了采样拓扑可以再现局部Internet拓扑结构特征.然后通过采样拓扑图的谱密度-特征值分布函数与ER图、BA无尺度网络拓扑图进行比较,发现三者具有明显区别,得出谱密度-特征值分布函数可作为分辨图谱拓扑结构有效方法的结论.最后通过4组3000点采样拓扑进行SLS分布分析,发现尽管4组3000点采样路由与连接互不相同,但SLS谱分布却非常相似,4组采样拓扑在特征值λ=1处重数均较高,重数次高的特征值都群聚在λ=2处.在特征值从2～103变化过程中表现出较明显的幂律分布特性,其幂指数值保持在3.2813至3.8013之间,特征指数接近.该结论为Internet宏观拓扑结构建模研究提供了量化判据,是Internet拓扑建模研究的重要内容.     

基于频繁闭图关联规则的AS级Internet链路预测方法

目前大多数链路预测方法都是针对丢失链路的结构性预测,缺乏针对未来时刻网络链路的时序性预测,为此提出了一种基于频繁闭图关联规则的链路预测方法。将形式化后的动态网络划分为训练集和测试集,基于Apriori思想从训练集中提取频繁闭图,并根据频繁闭图的时间间隔建立时延分布矩阵,用于表征频繁闭图之间的时序关联规则,在此基础上预测测试集中的网络结构。将该方法运用于不同时间尺度下的AS级Internet动态网络中,结果表明,该方法能够以很高的精确率预测波动型动态网络的链路。     

基于AS5045的磁旋转编码器的研究和应用

本文介绍了智能轴角传感器的原理和实现方法,给出了磁旋转编码器的应用原理和设计方法,同时详细介绍了AS5045的关键应用技术,提出了一种新的轴角采集与测量的实现途径。     

基于属性演化和空间影响的路由级拓扑建模

引入吸引度的概念,对国家级ISP网络拓扑结构进行分析,认为Internet网络拓扑的生长是节点带宽等内在因素与地理位置等外在因素共同作用的结果。综合考虑节点属性的演化及地理空间对网络拓扑的影响,给出一种新的Internet路由级拓扑建模算法,通过实验分析幂律及无符号拉普拉斯谱等度量特征,证明该算法能较真实地模拟Internet路由级拓扑结构。