Internet自治域层拓扑特性研究与建模

论文摘要

Internet的迅猛发展带来了一系列问题，例如路由、资源预留和网络管理等问题。由于在Internet上实验非常昂贵，且因为一些商业因素的限制，研究者不可能直接在Internet上模拟和仿真实验，一般都利用网络拓扑模型进行实验。Internet拓扑建模能为网络问题的分析提供一个抽象模型结构，使很多问题易于分析。所以，对于Internet拓扑建模的研究一直都是网络研究的热点问题。Internet拓扑模型的研究经历了从随机型到层次型，再到无尺度网络的过程。然而目前为止，研究者们没有找到公认统一的理论去解释Internet的演化机理，都只能根据自己的分析建立演化模型，然后对尽可能多的参数进行实验评估，希望模型能更好地“逼近”Internet的实际拓扑，以及更合理地解释Internet拓扑的形成原因。本文首先介绍了当前Internet拓扑的四个基本统计特性：无尺度、小世界、集聚性及异配性，并就这些特性对当前Internet拓扑做了统计分析。其次，本文研究和分析了几种主流的Internet拓扑模型及其算法，包括BA、AB、Inet、PLRG和GLP模型，并对他们做了仿真分析。结果显示，这些模型都能得到与Internet某些特性相符的拓扑图，不过都还存在不足之处，尤其是集聚程度都低于Internet。然后，具体分析了这些模型的演化算法存在的局限。Inet和PLRG模型是静态的，目的是产生一副与现有Internet幂律特性相符合的拓扑图，这种模型不能解释Internet的动态演化过程。动态模型如BA、AB和GLP通过建立演化机制来模拟Internet的发展过程，但这些模型的增长都是人为假设的均匀增长，与Internet规模的指数增长现象不符合，且建连机制具单一性。最后，根据对Internet层次性和规模增长特性的分析，提出了基于生灭过程的层次模型(Hierarchical model based on birth and death process，BDHM)。与传统模型不同的是，BDHM考虑了Internet中AS节点之间的商业关系以及网络规模的指数增长。BDHM用最大度支配子网冗余节点算法构造骨干网来实现Internet的分层；且引入生灭过程理论计算新节点的产生概率，从而用均匀时间步实现了规模的指数增长。另外，借助生灭过程理论推导出了网络特征路径长度随时间的极限值。实验结果表明，BDHM模型的拓扑特征与实际Internet较符合，且在集聚性和特征路径长度上比主流模型表现更好。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 Internet拓扑研究的背景和意义
• 1.2 Internet拓扑研究现状
• 1.2.1 拓扑模型
• 1.2.2 拓扑生成器
• 1.3 Internet建模的难点问题与研究路线
• 1.4 本文工作
• 1.5 本文组织结构
• 2 Internet拓扑特性分析
• 2.1 网络的表示
• 2.2 无尺度特性
• 2.3 小世界效应
• 2.4 聚类特性
• 2.5 异配性
• 2.6 小结
• 3 Internet拓扑模型的研究与性能分析
• 3.1 BA模型
• 3.2 AB模型
• 3.3 Inet模型
• 3.4 PLRG模型
• 3.5 GLP模型
• 3.6 各模型的性能比较与结果分析
• 3.7 小结
• 4 一种新的基于生灭过程的层次模型（BDHM）
• 4.1 引言
• 4.2 传统模型的不足
• 4.3 新模型BDHM的提出
• 4.4 Internet拓扑数据来源
• 4.5 新模型BDHM中骨干网的构造
• 4.5.1 Internet的层次结构
• 4.5.2 支配子网构造算法
• 4.5.3 支配子网生成算法分析
• 4.5.4 最大度支配子网冗余节点算法构造BDHM模型的骨干网
• 4.6 新模型BDHM的建连机制
• 4.7 新模型BDHM规模的生灭过程增长机制
• 4.7.1 Internet规模的指数增长
• 4.7.2 生灭过程介绍
• 4.7.3 Internet规模增长的生灭过程模拟
• 4.8 新模型BDHM的建模步骤
• 4.9 新模型BDHM的性能分析
• 4.9.1 度分布比较
• 4.9.2 集聚特性比较
• 4.9.3 异配性比较
• 4.9.4 特征路径长度比较
• 4.10 小结
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢