论文部分内容阅读
Internet,意为“网络的网络”,由上万个被称为自治系统(Autonomoussystem, AS)的网络互联而成,每个AS又由一组路由器互联而成。这两个层次的互联结构分别称为网络的AS级拓扑和IP级拓扑。大规模网络拓扑的测量与分析已经受到来自计算机科学、物理学、数学领域的广泛关注,因为人们相信,认识网络拓扑的本质不仅是开发高效、鲁棒、可扩展互联网络的基础,更是寻找复杂系统中普适定律的一条关键途径。然而,当前有三个问题亟待解决:(1)缺乏完整、准确的网络拓扑数据;(2)大规模网络特征化框架尚未建立;(3)网络拓扑的起源和演化机理尚未明确。为此,本文以准确描述网络拓扑的结构性质和演化趋势为目标。首先,完整地测量大规模网络IP级拓扑;然后,比较不同完整性的IP级拓扑之间的特征差异;接着,测量AS级拓扑并分析AS级拓扑特征差异;最后,分析AS级拓扑演化历史。鉴于IP级拓扑测量实践中目标采样的不充分以及测量模型中存在的失真,实施了蛮力测量实验,发现通常的低密度随机采样丢失了大量信息。通过分析路由行为,发现信息丢失的主要原因在于子网结构多样性,次要原因在于路径多样性;同时证明一种优化采样方法适用于长期测量实践。开发了一个测量工具fastrace,其中所采用的新技术可在保证完整性的同时将探测负载降低一半。2004年底对中国IP级拓扑的测量发现了约8万个节点,这是CAIDA skitter所测得拓扑规模的四倍。基于这一结果,考察了地区网络规模与其经济情况之间的相关性。为考察不同完整性IP级拓扑数据在特征上的共性与差异,首先,给出了拓扑特征化的度量列表,并分析了度量间相关性。然后,基于可视化技术,观察了拓扑间的直观差异。接着,提出了子图覆盖模式的概念,来描述子图对全图中不同重要性部分的覆盖程度。使用子图覆盖模式发现,中国网络处于Internet的边缘,表现为离心性;而skitter和fastrace测得的中国拓扑在合并拓扑中分别表现为向心性和离心性。最后,将子图覆盖模式应用于特征差异分类,发现多数幂律指数是鲁棒的,而其他度量对图规模或覆盖模式是敏感的。为了解AS级拓扑测量数据的多样性,运用综合集成的思想来广泛收集拓扑数据并比较其间差异。采用基于BGP(Border Gateway Protocol)、基于traceroute和基于IRR(Internet Routing Registry)的方法从不同数据源获取了多幅拓扑快照。其间,提出了基于更新时间的IRR信息过滤法,以及一种基于层次的互连关系推断法。基于集合运算对快照进行了分组比较,发现基于BGP更新消息的数据具有较好完整性和一致性,而基于traceroute的数据一致性较差。进而得到了一幅较完整可信的中国AS图,比通常采用的RouteViews路由表多出近65%的链接。通过对典型拓扑数据的特征进行比较后发现:在定量上,平均度是主导差异的主特征;在定性上,多数特征本身相同,但其统计显著性不同;基于BGP测量和基于traceroute测量分别低估和高估了连通性。对全球AS级拓扑特征的比较印证了上述发现,为最近关于Rich-club现象的争论提供了一条新的解决途径。为了解AS级拓扑演化趋势与机理,对AS级拓扑历史进行了全面观测。首先,提出了拓扑生长方式和优先附着函数的测量方法。接着,对中国AS级拓扑历史进行观察,发现具有非交互性的拓扑灭过程,以及平均度增长、特征显著性累积现象。然后,通过观察全球AS级拓扑历史,发现最大度增长受抑制现象,提出了无尺度是一个阶段性特征的假设;发现非相配性减弱现象,提出了度相关性将向中立性转变的假设;发现最大核能够代替Rich-club连通性来描述核心生长现象。最后,测量了拓扑生长方式和优先附着函数,报告了相关演化模型在描述性、预测性、解释性三方面的失真,并提出了改进建议。