Internet中QoS多播路由技术研究

论文摘要

QoS多播路由技术是在Internet中应用多媒体业务的关键性技术，目前，QoS多播路由领域中还存在着许多期待解决的问题。本文针对该领域中的多QoS约束、非精确网络状态、ACO的应用、路由的扩展性等问题，围绕着NP-完全问题的求解以及状态信息的非精确性这两个主题进行了深入地研究。本学位论文所作的工作如下： 1) 首先，需要一个专门的网络仿真平台来分析和验证本文所提出的协议或算法，但现有的网络仿真软件却不能满足我们对网络动态和QoS路由进行模拟的要求。为此，本文对NS2的状态更新模型作了修改，采用了带三个更新元素的混合更新模型，并加入了新的流量发生器，同时对其链路对象进行扩展，使之具有检测和控制QoS的功能。最终设计出一套基于NS2、能对网络动态和非精确状态信息进行有效模拟且支持QoS路由的网络仿真软件—DRS，并附带一套拓扑仿真软件—Top-Builder。该拓扑仿真软件整合了现有拓扑仿真器各自的优点，它不仅能精确地描述Internet的拓扑结构，还能构造实验性的网络拓扑，同时具有良好可扩展性。 2) 现有的QoS多播路由算法都没有考虑到状态信息的非精确性对其路由性能的影响。通过概率分布假设，本文提出了一种描述非精确状态信息的新模型，并在此基础上提出了一种分布式、多QoS约束的多播路由算法—QMRI。在QMRI中，我们采用了基于交通灯的分布式计算方式来化解多QoS约束的NP-完全问题。实验结果表明，QMRI不仅能够适应状态信息的非精确性，而且具有较高的呼叫成功率和适度的消息负载。 3) 在目前所有应用ACO的QoS多播路由算法中，状态信息的不及时性和非精确性对蚂蚁选路过程的影响都没有被考虑到。为此，本文设计出了一种考虑了状态信息的非精确性、有带宽和延迟保证、基于蚂蚁代理的多播路由算法—QMRA。在QMRA中，蚂蚁使用链路满足QoS约束的概率以及它所经过路径的代价，而不是它的旅行时间或年龄来决定信息素的铺设。仿真结果显示了QMRA在状态信息不精确的情况下，具有较低的路由阻塞率和数据包的平均延迟，并且能够快速收敛。 4) QoS参数的数量和特征是影响拓扑聚集策略和层次路由算法的决定性因素，然而，现有的QoS层次多播路由算法都只考虑了一个QoS约束的

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究的背景和意义
• 1.2 相关内容的研究现状
• 1.2.1 Qos多播路由
• 1.2.1.1 QoS多播路由算法
• 1.2.1.2 路由算法的评价
• 1.2.2 动态路由
• 1.2.3 网络仿真
• 1.3 本文的工作与贡献
• 1.4 论文的组织结构
• 第2章 QoS多播路由的研究基础
• 2.1 概述
• 2.2 QoS多播路由模型
• 2.2.1 网络模型
• 2.2.2 QoS度量及特征
• 2.2.2.1 QoS度量（metric）
• 2.2.2.2 QoS度量特征
• 2.2.3 路由模型
• 2.2.4 路由模型的求解
• 2.3 动态路由与蚁群优化
• 2.3.1 动态路由
• 2.3.1.1 Guérin概率模型及其分支
• 2.3.1.2 Chen概率模型
• 2.3.2 蚁群优化
• 2.3.2.1 ABC系统及其分支
• 2.3.2.2 AntNet及其扩展
• 2.4 本章小结
• 第3章 网络拓扑的建模与仿真
• 3.1 引言
• 3.2 网络拓扑的建模
• 3.2.1 拓扑特征的表示
• 3.2.2 随机拓扑的建模
• 3.2.2.1 几种随机拓扑模型
• 3.2.2.2 模型参数的选择
• 3.2.2.3 模型特征的比较
• 3.2.2.4 BarabasiAlbert随机拓扑模型
• 3.2.3 规则拓扑的建模
• 3.2.4 Internet拓扑的建模
• 3.2.4.1 Internet的拓扑结构
• 3.2.4.2 混合建模方法
• 3.2.4.3 几种 Internet拓扑模型
• 3.3 拓扑仿真器的设计与实现
• 3.3.1 Top-Builder的体系结构
• 3.3.2 拓扑图的生成过程
• 3.3.3 Top-Builder的接口设计
• 3.3.3.1 用户接口
• 3.3.3.2 配置文件格式
• 3.3.3.3 输出文件格式
• 3.4 本章小结
• 第4章 动态路由仿真系统的设计与实现
• 4.1 引言
• 4.2 NS2的体系结构
• 4.2.1 模拟引擎
• 4.2.2 网络元素
• 4.2.3 协议模型
• 4.2.4 流量模型
• 4.2.5 跟踪与监视模型
• 4.2.6 后续处理工具
• 4.3 DRS的设计与实现
• 4.3.1 模拟引擎
• 4.3.2 协议模型
• 4.3.2.1 非精确状态的仿真
• 4.3.2.2 更新参数的选择
• 4.3.3 流量模型
• 4.3.3.1 流量类型
• 4.3.3.2 流的特征
• 4.4 实现网络协议
• 4.4.1 DRS的仿真过程
• 4.4.2 DRS的对象空间
• 4.4.3 数据包的格式
• 4.4.4 开发协议的方法
• 4.4.4.1 用 C++编程的方法
• 4.4.4.2 用 OTcl编程的方法
• 4.4.5 评价协议性能
• 4.5 本章小结
• 第5章 平面网络中的QoS多播路由算法
• 5.1 引言
• 5.2 网络模型
• 5.2.1 路由模型
• 5.2.2 非精确状态模型
• 5.2.2.1 捕捉状态信息的非精确性
• 5.2.2.2 计算路径满足 QoS约束的概率
• 5.3 QMRI算法描述
• 5.3.1 基本思想
• 5.3.2 详细描述
• 5.3.2.1 加入过程
• 5.3.2.2 资源预留
• 5.3.2.3 退出过程
• 5.4 正确性与复杂性
• 5.4.1 正确性
• 5.4.2 复杂性
• 5.5 仿真实验
• 5.5.1 实验环境
• 5.5.2 实验结果
• 5.5.2.1 路由成功率
• 5.5.2.2 网络代价
• 5.6 本章小结
• 第6章 基于蚂蚁代理的 QoS多播路由算法
• 6.1 引言
• 6.2 系统模型
• 6.2.1 信息素表的结构
• 6.2.2 路由模型
• 6.2.3 非精确状态信息
• 6.3 QMRA算法描述
• 6.3.1 主要思想
• 6.3.2 详细描述
• 6.4 相关问题的讨论
• 6.4.1 收敛规则与蚂蚁数
• 6.4.2 正确性和复杂性
• 6.5 仿真实验
• 6.5.1 实验环境
• 6.5.2 实验结果
• 6.6 本章小结
• 第7章 层次网络中QoS多播路由的算法框架
• 7.1 引言
• 7.2 系统模型
• 7.2.1 层次网络模型
• 7.2.2 QoS多播路由模型
• 7.3 拓扑聚集
• 7.3.1 构造Full-Mesh图
• 7.3.2 构造生成树
• 7.3.3 构造Star模型
• 7.4 路由算法
• 7.4.1 概述
• 7.4.2 状态信息
• 7.4.3 算法描述
• 7.4.3.1 加入计算
• 7.4.3.2 资源预留
• 7.4.3.3 退出计算
• 7.5 复杂性分析
• 7.5.1 空间复杂度
• 7.5.2 计算复杂度
• 7.6 仿真实验
• 7.6.1 仿真环境
• 7.6.2 实验结果
• 7.7 本章小结
• 第8章 总结与展望
• 8.1 研究成果总结
• 8.2 进一步工作展望
• 参考文献
• 致谢
• 附录 A 相关路由算法的伪代码
• 附录 B 攻读博士学位期间发表的论文、科研项目及发明专利情况