学位论文 > 优秀研究生学位论文题录展示

大规模网络拓扑测量与分析研究

作　者: 张宇
导　师: 方滨兴
学　校: 哈尔滨工业大学
专　业: 计算机系统结构
关键词: 网络测量复杂网络网络拓扑测量网络拓扑建模网络拓扑演化
分类号: TP393.02
类　型: 博士论文
年　份: 2009年
下　载: 348次
引　用: 1次
阅　读: 论文下载

内容摘要

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连通性来描述核心生长现象。最后,测量了拓扑生长方式和优先附着函数,报告了相关演化模型在描述性、预测性、解释性三方面的失真,并提出了改进建议。

全文目录

摘要  4-6
Abstract  6-15
第1章绪论  15-33
  1.1 背景及意义  15-19
    1.1.1 网络拓扑  15-16
    1.1.2 网络拓扑测量  16-17
    1.1.3 网络拓扑建模  17-19
  1.2 网络拓扑测量与分析研究现状  19-29
    1.2.1 IP 级拓扑测量技术与实践  19-21
    1.2.2 AS 级拓扑测量技术与实践  21-22
    1.2.3 网络拓扑特征化  22-26
    1.2.4 AS 级拓扑演化机理  26-29
  1.3 本文工作  29-33
    1.3.1 研究目标  29-30
    1.3.2 研究框架  30-31
    1.3.3 研究内容与章节安排  31-33
第2章完整的IP 级拓扑测量  33-47
  2.1 引言  33-34
  2.2 基于路由行为的目标采样完整性研究  34-39
    2.2.1 均匀随机目标采样的完整性  34-35
    2.2.2 目标采样不完整性因素  35-37
    2.2.3 优化目标采样  37-39
  2.3 拓扑测量工具fastrace  39-40
  2.4 实验结果  40-45
    2.4.1 fastrace 测量技术评价  40-41
    2.4.2 中国IP 级拓扑测量结果  41-44
    2.4.3 地区经济与网络规模相关性  44-45
  2.5 本章小结  45-47
第3章基于子图覆盖模式的IP 级拓扑特征比较  47-62
  3.1 引言  47-48
  3.2 网络拓扑特征化方法  48-51
    3.2.1 度量的定义  48-51
    3.2.2 度量间相关性  51
  3.3 子图覆盖模式  51-53
  3.4 实验结果分析与验证  53-60
    3.4.1 基于可视化的比较  53-54
    3.4.2 子图覆盖模式结果  54-56
    3.4.3 基于子图覆盖模式的特征差异分类  56-59
    3.4.4 验证  59-60
  3.5 本章小结  60-62
第4章基于综合集成的AS 级拓扑测量与分析  62-83
  4.1 引言  62-64
  4.2 基于综合集成的AS 级拓扑测量  64-68
    4.2.1 基于BGP 的测量  64-65
    4.2.2 基于traceroute 的测量  65-66
    4.2.3 基于IRR 的测量  66-67
    4.2.4 互连关系推断  67-68
  4.3 AS 级拓扑测量结果  68-72
  4.4 AS 级拓扑特征比较分析  72-81
    4.4.1 中国AS 级拓扑特征比较结果  72-78
    4.4.2 全球AS 级拓扑特征比较结果  78-81
  4.5 本章小结  81-83
第5章 AS 级拓扑演化分析  83-97
  5.1 引言  83-84
  5.2 演化机理分析方法  84-85
    5.2.1 生长历史分析方法  84-85
    5.2.2 描述性验证方法  85
  5.3 观察拓扑特征演化历史  85-90
    5.3.1 中国AS 级拓扑特征演化历史  86-87
    5.3.2 全球AS 级拓扑特征演化历史  87-90
  5.4 AS 级演化机理分析结果  90-96
    5.4.1 PFP 模型与拓扑特征关系  90-91
    5.4.2 描述性分析  91
    5.4.3 预测性分析  91-92
    5.4.4 解释性分析  92-95
    5.4.5 演化模型改进  95-96
  5.5 本章小结  96-97
结论  97-99
参考文献  99-112
攻读博士学位期间所发表的论文  112-114
致谢  114-115
个人简历  115

大规模网络拓扑测量与分析研究

内容摘要

全文目录

相似论文