网络中带约束的组播路由算法

论文摘要

随着通信技术的发展，组播技术正成为计算机网络中支持多媒体应用的关键技术。一般来说，用户对不同的分布式多媒体应用有着不同的服务质量要求，这就要求网络应能根据用户的要求分配和调度资源。组播是一种允许一个主机向多个目的主机(但不是所有主机)发送同一信息的通信方式。带约束的组播路由问题就是要寻求一棵满足给定约束且费用最小的组播树。本文主要研究带约束的组播路由算法，即建立一棵满足QoS(Quality of Service，服务质量)约束的组播树。目前组播路由算法的研究大多都针对无约束组播路由问题和时延受限组播路由问题。本文针对QoS约束的组播路由问题，提出了一种新的时延受限组播路由算法，证明了该算法具有多项式时间复杂性。仿真结果表明，该算法在费用上优于CDKS算法，与KPP和BSMA算法接近，在时间复杂度上小于KPP和BSMA算法。所以，该算法是一种满足时延约束的，具有较低时间复杂度且费用适中的Steiner树算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 组播技术产生的背景
• 1.2 QoS组播路由面对的问题
• 1.3 本课题的来源及研究意义
• 1.4 时延受限组播问题的数学模型
• 1.5 相关的研究工作
• 1.5.1 Steiner树算法和CBT算法
• 1.5.2 静态和动态组播路由算法
• 1.5.3 集中式和分布式组播路由算法
• 1.5.4 QoS组播路由算法
• 1.5.5 分层组播路由算法
• 1.6 本文的主要工作
• 第二章 组播技术概述
• 2.1 为什么要使用组播
• 2.2 组播特点及应用
• 2.2.1 组播的特点
• 2.2.2 组播的应用
• 2.3 组播技术的内容
• 2.3.1 组播协议的体系结构
• 2.3.2 组播地址分配
• 2.3.3 Internet组管理协议
• 2.3.4 组播报文转发
• 2.3.5 组播路由协议
• 2.3.6 组播技术研究组织
• 第三章 组播路由算法
• 3.1 组播树的理论基础及算法介绍
• 3.1.1 组播树理论的数学基础
• 3.1.2 Steiner树问题的定义
• 3.1.3 Steiner树问题的启发式算法
• 3.2 QoS组播路由问题
• 3.3 QoS组播路由算法
• 3.4 典型的时延约束Steiner树启发式算法
• 3.5 时延受限的组播路由算法
• 3.5.1 算法的基本思想
• 3.5.2 算法描述
• 3.5.3 算法性能分析
• 3.5.4 应用举例
• 3.6 算法仿真
• 3.6.1 随机网络产生模型
• 3.6.2 算法的仿真及分析
• 第四章 结束语
• 4.1 全文总结
• 4.2 展望
• 参考文献
• 致谢