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

因特网拓扑特征的系统化分析技术研究

作　者: 杨国强
导　师: 窦文华
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 因特网拓扑特征系统化分析技术 dK特征序列拓扑图生成算法自治系统AS 关系标注的AS拓扑图
分类号: TP393.02
类　型: 博士论文
年　份: 2010年
下　载: 69次
引　用: 0次
阅　读: 论文下载

内容摘要

因特网拓扑作为因特网的基本特征,对于运行于因特网之上的各种协议和应用具有本质的影响。因特网拓扑研究对于许多其它因特网相关研究具有重要意义。因特网拓扑特征的系统化分析技术和dK特征序列是因特网拓扑研究领域的最新研究成果,对因特网拓扑的特征分析和建模研究起到了重要的推进作用,对其它相关研究领域(如复杂网络研究)也具有重要的借鉴意义。dK特征序列由一系列的拓扑特征组成,这些拓扑特征被称为dK特征。dK特征序列能够在不同的精度刻画拓扑图的特征,且精度随着d的增大而增加。这种用一系列的精度不断增加的拓扑特征来分析因特网拓扑的特性的方法,被称为系统化的拓扑特征分析技术。本文在dK特征序列的基础上深入研究了因特网拓扑的系统化分析技术,论文创新点如下:(1)提出了性能优于现有算法的dK图生成算法,并提出了用于增加dK图连通性的算法。dK图定义为dK特征与待研究的拓扑图的dK特征相同的拓扑图。由于dK特征序列具有强大的拓扑特征描述能力,因此研究dK图生成算法对于因特网拓扑研究具有重要意义。本文针对现有dK图生成算法存在的主要问题(精度低和生成的拓扑图连通性差),提出了一种改进的2K图生成算法以及一种3K图直接生成算法。实验结果表明,本文算法在精度和生成的拓扑图的连通性方面明显优于已有算法。本文进一步提出了一种基于重连的增加dK图连通性的算法,实验结果表明,该算法能够显著减少各种dK图生成算法生成的拓扑图的非连通子图的个数。(2)提出了用于计算关系标注的AS(自治系统)拓扑图的最短路径和Betweenness的快速算法。由于AS之间存在复杂的路由关系,因此因特网AS级拓扑通常用一张部分有向图(partially directed graph)表示,图中的边标注了AS之间的路由关系。在这样一个部分有向图中,传统的计算拓扑图的最短路径和Betweenness的算法将不再适用。本文基于宽度优先搜索(BFS)算法提出了一种计算关系标注的AS拓扑图中最短路径和Betweenness的快速算法。算法的时间复杂度为O(nm),优于现有的时间复杂度为O(n3)的算法(其中n为拓扑图节点个数,m为拓扑图边个数),因此更适合于因特网AS级拓扑研究。(3)研究了关系标注的AS拓扑图的系统化分析方法。dK特征序列的定义是基于无向图的,因此不能用于关系标注的AS拓扑图的特征分析。本文提出了一种用于系统化分析关系标注的AS拓扑图的特征序列:dK′特征序列,dK′特征序列在dK特征序列的基础上增加了边类型的描述信息。本文进一步通过对dK图生成算法进行扩展,提出了dK′图生成算法。实验结果表明:dK′特征序列具有与dK特征序列类似的系统化拓扑特征描述能力;当d=3时,3K′图生成算法生成的拓扑图能够在各种重要的拓扑特征方面与关系标注的AS拓扑图保持一致。(4)提出了一种新的简洁的系统化拓扑特征分析方法。dK特征序列存在状态空间膨胀的问题,随着d的增加,拓扑图中节点个数为d的子图个数迅速增大。这个问题导致dK图生成算法比较复杂,在d>3的情况下没有有效的dK图生成算法。本文定义了一种邻接图的概念,并在此基础上提出了一种新的特征序列:dM特征序列。本文进一步提出了dM图的生成算法,与dK图生成算法相比该算法步骤更简单,而且该算法对任意的d都适用,因此更适合于大规模拓扑图的系统化特征分析研究。实验结果表明dM特征序列具有与dK特征序列相同的拓扑特征描述能力:随着d的增加,dM特征的描述精度不断增大;2M图已经能够在各种重要的拓扑特征方面与原始拓扑图保持一致。

全文目录

摘要  13-15
Abstract  15-17
第一章绪论  17-39
  1.1 研究背景和意义  17-18
  1.2 研究现状  18-29
    1.2.1 拓扑数据的采集  19-20
    1.2.2 拓扑数据的分析和加工  20-21
    1.2.3 拓扑数据的可视化  21-24
    1.2.4 拓扑特征分析  24-25
    1.2.5 拓扑建模  25-29
  1.3 相关研究工作  29-35
    1.3.1 实验数据来源  29-30
    1.3.2 拓扑布局算法  30-31
    1.3.3 因特网拓扑的系统化特征分析技术  31-35
  1.4 论文研究内容  35-36
  1.5 论文组织结构  36-39
第二章重要的拓扑特征与dK 特征序列的关系研究  39-59
  2.1 重要的拓扑特征  39-51
    2.1.1 节点度分布  40-41
    2.1.2 节点关联性相关分布  41-43
    2.1.3 Assortativity 系数  43-44
    2.1.4 Rich-club 系数  44-45
    2.1.5 聚类系数  45-47
    2.1.6 最短路径  47-49
    2.1.7 Betweenness  49-50
    2.1.8 特征值  50-51
  2.2 dK 特征序列与重要的拓扑特征之间的关系  51-57
    2.2.1 节点和边个数  52
    2.2.2 节点度分布  52
    2.2.3 节点联合度分布  52-53
    2.2.4 Assortativity 系数  53-54
    2.2.5 Rich-club 系数  54-55
    2.2.6 聚类系数  55-56
    2.2.7 其它拓扑特征  56
    2.2.8 结论  56-57
  2.3 本章小结  57-59
第三章 dK 图的生成算法研究  59-95
  3.1 研究现状  59-66
    3.1.1 随机生成算法  59-61
    3.1.2 伪图算法  61-63
    3.1.3 重连算法  63-66
  3.2 2K 图的生成算法研究  66-74
    3.2.1 VFPG 算法  66-67
    3.2.2 基于VFPG 算法的2K 图生成算法  67-71
    3.2.3 实验与结果分析  71-74
  3.3 3K 图的生成算法研究  74-89
    3.3.1 基本原理  74-76
    3.3.2 节点的邻居节点度与3K 特征的关系  76-77
    3.3.3 3K 图直接生成算法  77-84
    3.3.4 实验与结果分析  84-89
  3.4 增加dK 图连通性的算法研究  89-93
    3.4.1 基本原理  89-90
    3.4.2 交换边前后dK 特征不变的条件  90-92
    3.4.3 增加dK 图连通性的算法  92
    3.4.4 实验与结果分析  92-93
  3.5 本章小结  93-95
第四章关系标注的AS 拓扑图中的最短路径和Betweenness 算法研究  95-115
  4.1 关系标注的AS 拓扑图  95-98
    4.1.1 BGP 路由策略与AS 关系  95-96
    4.1.2 关系标注的AS 拓扑图及符合BGP 路由策略的AS 路径  96-98
  4.2 关系标注的AS 拓扑图中的最短路径算法研究  98-110
    4.2.1 现有的AS 拓扑的最短路径算法  98-99
    4.2.2 基于宽度优先的AS 拓扑的最短路径算法  99-107
    4.2.3 实验与结果分析  107-110
  4.3 关系标注的AS 拓扑图中的Betweenness 算法研究  110-113
    4.3.1 现有的AS 拓扑的Betweenness 算法  110
    4.3.2 基于宽度优先的AS 拓扑的Betweenness 算法  110-112
    4.3.3 实验与结果分析  112-113
  4.4 本章小结  113-115
第五章关系标注的AS 拓扑图的系统化分析技术研究  115-133
  5.1 dK′特征序列的定义及性质  115-120
    5.1.1 关系矩阵  115-116
    5.1.2 关系标注的AS 拓扑图的dK′特征序列定义  116-120
  5.2 dK′图的生成算法研究  120-125
    5.2.1 0K′和1K′图的生成算法  120-121
    5.2.2 2K′图的生成算法  121-123
    5.2.3 3K′图的生成算法  123-125
  5.3 实验与结果分析  125-132
    5.3.1 dK′图生成算法性能分析  125-126
    5.3.2 dK′特征序列的特征描述能力分析  126-132
  5.4 本章小结  132-133
第六章 dM 特征序列分析技术研究  133-149
  6.1 dM 特征序列的定义  133-138
    6.1.1 节点的d 阶邻接图  134-135
    6.1.2 dM 特征序列的定义  135-138
    6.1.3 dM 特征与dK 特征的关系  138
  6.2 dM 图生成算法  138-141
    6.2.1 1M 图的生成算法  139-140
    6.2.2 dM 图的生成算法  140-141
  6.3 实验与结果分析  141-147
  6.4 本章小结  147-149
第七章结束语  149-153
  7.1 论文的主要贡献  149-150
  7.2 进一步研究工作  150-153
致谢  153-155
参考文献  155-163
作者在学期间取得的学术成果  163-164
附录主要术语中英文对照表  164

因特网拓扑特征的系统化分析技术研究

内容摘要

全文目录

相似论文