生成Internet自治系统层次拓扑图算法研究与实现

论文摘要

随着网络技术的发展和互联网的广泛应用,人们对网络的研究也在逐步的深入。Internet拓扑图为大范围开发、利用Internet提供了一个有力的工具。网络研究者可以利用拓扑生成器生成的网络拓扑图进行网络仿真实验,但在目前的研究中,还没有形成统一的参数集来全面评估Internet拓扑图。因而,研究者只能尽可能使用更多参数来分析和实验,希望能使拓扑图更好的“逼近”实际Internet拓扑。首先,本文研究和分析了Internet拓扑研究的现状,对Internet拓扑研究的意义、方法以及评估参数进行了详细的探讨并对Internet拓扑研究的历程、成果和难点作了分析,勾画了当前Internet拓扑研究的概貌。接着,对Internet拓扑在自治系统级和路由器级两个层次的研究进行分析。分析了Internet自治系统的机理及工作方式,对Internet自治系统拓扑图的研究现状进行总结,指出Internet自治系统拓扑图的应用、方法和前景。Internet自治系统拓扑图在自治系统的层次上刻画Internet特征,它在当前很多领域有着广泛应用。另一方面,探讨了路由器级拓扑的应用、研究方式并把Internet自治系统级拓扑图和路由器级拓扑图进行对比分析,总结各自优缺点。然后,深入研究了Internet自治系统层次拓扑模型,对目前两个比较成熟的层次拓扑模型Transit-Stub模型和Tiers模型从平均结点度、冗余度和平均每跳直径等参数进行对比分析,发现传统自治系统级层次拓扑模型不能很好的反映实际网络的可靠性。最后,本文提出了生成Internet自治系统拓扑图的Core-Tree算法及其改进算法Complete-Waxman-Tree算法,这两个算法把Internet自治系统拓扑图分为树形拓扑和高层网络。Core-Tree算法生成两个层次的自治系统拓扑图,其生成图具有一些Internet的基本特征,如多层次、自治系统、低平均结点度、主干网络强连通等;生成图的拓扑性质与从实际数据分析的结果比较接近并且与其它层次模型相比具有相似的性质。但是Core-Tree拓扑图存在局部网络不稳定以及主干网络重要性不突出的缺点。为了解决上述两个问题,本文接着提出了其改进算法Complete-Waxman-Tree算法,改进算法的生成图突出了主干网络并且把局部网络不稳定性范围缩小,比Core-Tree生成图更为合理。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 Internet拓扑建模简介
• 1.1.1 Internet拓扑建模的应用
• 1.1.2 Internet拓扑建模的研究方向
• 1.1.3 拓扑建模研究历程
• 1.1.4 拓扑模型
• 1.2 拓扑生成器
• 1.2.1 拓扑生成器规范与要求
• 1.2.2 现有拓扑生成器
• 1.3 Internet拓扑模型的评估参数
• 1.4 Internet拓扑建模的难点与研究路线
• 1.5 本文工作及结构
• 第2章 Internet自治系统拓扑研究现状
• 2.1 自治系统
• 2.1.1 自治系统概念
• 2.1.2 自治系统拓扑概念
• 2.2 自治系统选路协议
• 2.2.1 域间路由
• 2.2.2 域内路由
• 2.2.3 区别
• 2.3 研究自治系统关系的意义
• 2.3.1 自治系统关系代表着Internet结构中最关键的部分
• 2.3.2 自治系统关系是一种重要的网络资源
• 2.3.3 自治系统间的关系在网络服务方面有重要指导意义
• 2.4 研究自治系统关系的几种方法
• 2.4.1 WHOIS数据库
• 2.4.2 主动探测方式
• 2.4.3 利用BGP路由表数据
• 2.4.4 以上几种方式的比较
• 2.5 路由器级拓扑和自治系统级拓扑
• 2.5.1 路由器级拓扑
• 2.5.2 自治系统级拓扑
• 2.5.3 自治系统拓扑和路由器拓扑的比较
• 2.5.4 自治系统拓扑研究现状
• 2.6 小结
• 第3章 自治系统层次拓扑模型
• 3.1 对层次模型的研究和分析
• 3.1.1 Tiers模型
• 3.1.2 Transit-Stub模型
• 3.2 层次型模型间的比较
• 3.2.1 层次模型和随机模型对比
• 3.2.2 层次模型之间的对比
• 3.3 传统层次型模型的不足
• 3.4 评测层次结构的参数
• 3.4.1 链路权值分布
• 3.4.2 路径使用率与结点度的相关系
• 3.5 小结
• 第4章 Core-Tree算法
• 4.1 引言
• 4.2 C-T算法思想
• 4.3 定义
• 4.3.1 C-T生成图结点定义
• 4.3.2 C-T算法参数定义
• 4.4 算法描述
• 4.5 算法分析及实验分析
• 4.5.1 时间复杂度分析
• 4.5.2 生成图性质分析
• 4.5.3 实验结果分析
• 4.5.4 与其它模型对比
• 4.6 小结
• 第5章 Complete-Waxman-Tree算法
• 5.1 引言
• 5.2 CWT算法基本思想
• 5.3 参数定义
• 5.4 算法描述
• 5.5 算法分析及实验结果
• 5.5.1 时间复杂度分析
• 5.5.2 生成图性质分析
• 5.5.3 实验结果分析
• 5.5.4 与其它层次模型及CT算法对比
• 5.6 小结
• 结论
• 参考文献
• 致谢
• 附录A：攻读学位期间所发表学术论文
• 附录B：攻读学位期间参与项目