因特网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拓扑的结构与连通性研究

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

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

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

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

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

Internet宏观拓扑结构的可视化

针对Internet宏观拓扑结构的复杂性,研究了AS级Internet宏观拓扑结构的可视化问题。首先利用常用的几种布点策略,对Internet宏观拓扑结构进行了可视化设计。结果表明,这些策略均不能展现Internet宏观拓扑结构的结构特性,因此并不适用于Internet的可视化。为此设计了一种新的方法,即中心层次布点策略。结果表明,该种策略能很好地体现Internet宏观拓扑结构的幂率性质和层次性质,对直观地观察Internet宏观拓扑结构提供了有力的手段。     

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

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

路由级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拓扑建模研究的重要内容.     

互联网新生节点连接偏好探究

IP级拓扑是Internet拓扑的细粒度表示,AS级拓扑是Internet拓扑的粗粒度化表示,是Internet宏观结构的抽象。从IP级拓扑及AS级拓扑粗细粒度两个层面来对互联网新生节点的连接偏好及连接稳定性进行探索,验证是否存在BA网络的优先连接的偏好。     

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

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

大规模软件与AS级Internet宏观拓扑结构分析比较

大规模软件与AS级Internet宏观拓扑结构的研究.对两者结构的进一步理解和应用具有重要意义.根据大规模软件结构与AS级Intemet宏观拓扑结构体现出来的复杂网络特征,分别将其抽取为网络拓扑,然后采用复杂网络的度量分析方法,从连通性、度分布特征、小世界特征和层次性4个方面进行了分析比较,得到了大规模软件与AS级Internet在宏观拓扑结构上的若干异同之处,并讨论了其产生原因.     

基于MPBGP协议的IPv6自治域间网络拓扑发现技术

分析了基于MPBGP协议进行IPv6自治域间网络拓扑发现的方法.提出综合利用MPBTDs(mpbgp table dump)和MPBUDs(mpbgp update dump)构建IPv6 AS级网络拓扑图可极大提高拓扑完整性,对MPBTDs和MPBUDs构建IPv6自治域间网络拓扑完整性方面的性能差异进行了比较,并用实验结果进行了验证.     

复合型路由器级拓扑模型

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

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

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

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

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

IP子网物理拓扑结构发现研究

将IP子网的拓扑结构看做一棵拓扑树,对互连的交换机的地址转发表中的交换机的MAC地址进行了分析,给出一组判定定理用以确定交换机间的连接关系。基于上述定理,提出了一个新的自顶向下的拓扑发现算法,该算法能够利用地址转发表构造出整个网络拓扑结构。与已有的物理拓扑发现算法相比,该算法具有高效、实用的优点。     

基于核数分层的AS级网络拓扑可视化布局算法

分析了当前几种常见的网络拓扑布局算法,针对Internet自治域级网络拓扑结构的特征和发现现状,提出了一种核数分层的混合拓扑布局算法,在网络核心层采用力导向布局算法,在网络非核心层采用树型布局算法,较好地解决了节点合理布局问题和计算效率问题。实验证明该算法能够反映自治域网络的基本特征,布局清晰、直观,具有较强的可读性。     

The impact of IXPs on the AS-level topology structure of the Internet

The AS-level topology of the Internet has been quite a hot research topic in the last few years. However, only a small number of studies have been developed that give a structural interpretation of this graph. Such an interpretation is crucially important in order to test protocols and optimal routing algorithms, to design efficient networks, and for failure detection purposes. Moreover, most research does not highlight the role that IXPs have on the AS-level structure of the Internet, although their role is recognized as fundamental.The initial contribution of this study is an analysis of the most important AS-level topologies that are publicly found on the web and an analysis of the topology obtained when they are merged. We compiled structural information from this topology making considerable use of the k-core decomposition technique to delineate various particular classes of nodes. Next, we associated node properties with a reasonable modus operandi of the ASs on the Internet. The second contribution is a study of the impact that ASs connected to IXPs and BGP connections crossing IXPs have on the AS-level topology. To achieve this, we developed a procedure to gather reliable information related to IXPs and their participants.     

Internet网络拓扑建模

首先概述Internet网络拓扑建模的意义和分类;总结现阶段已发现的主要网络拓扑特性与度量指标;然后分析、讨论自治域级和路由器级的Internet网络拓扑建模与最新的研究成果;最后针对目前拓扑建模中存在的难点和问题给出总结,并展望未来的研究发展方向.