满足QoS约束的多播路由算法

论文摘要

当前许多多媒体业务都要求网络具有多播(multicast)能力,例如：音频、视频会议、交互式仿真、网络游戏、分布式数据库等。多播技术,将同样的数据从一个源节点同时传输给大量的目的节点,从而大大节省了网络带宽,减少了数据冗余,在一定程度上解决了多媒体通信中的带宽瓶颈问题,将成为未来的一项重要技术。多播路由算法的目标是寻找一棵连接源节点和多个目的节点的多播树,同时满足各种服务质量需求。在实时交互性多播应用中,时延和时延抖动等服务质量因素尤为重要。为此,论文主要研究满足QoS约束中时延和时延抖动约束的多播路由问题。论文首先研究时延约束下的多播路由问题,该问题的目标是创建一棵覆盖源节点和目的节点的代价最小树,且满足端到端时延要求。这个问题被证明是NP完全问题。我们在研究已有算法的基础上,提出两个新的启发式算法。一种算法充分考虑链路共享对网络费用和链路时延的影响,提出了关键节点的概念。使得算法可以在满足时延约束的情况下,找到费用最小的多播树。另一种算法提出了节点优先函数和链路选择函数的概念,在构造满足时延约束低代价的树时运用了单播策略。分析的结论是这两种算法都是低复杂度、低费用并符合时延约束的多播路由算法。然后,论文分析限制时延抖动对某些多播应用的重要意义,并就时延和时延抖动约束的多播路由问题提出了一种新的链路选择函数。基于这个函数我们提出了一个时延和时延抖动约束的启发式Steiner树算法,通过仿真表明,该算法在时延抖动方面有较好的性能。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 多播路由技术简介
• 1.2.1 多播路由的主要概念
• 1.2.2 QoS约束多播路由的主要概念
• 1.3 多播路由算法
• 1.3.1 多播路由算法的分类
• 1.3.2 多播路由算法简介
• 1.4 多播路由协议
• 1.5 论文的主要工作及结构
• 第2章 QoS多播路由理论基础
• 2.1 基本概念
• 2.1.1 QoS度量
• 2.1.2 QoS多播路由的网络模型
• 2.2 Steiner树问题及启发式算法
• 2.2.1 Steiner树问题
• 2.2.2 Steiner树的启发式算法
• 2.3 多播路由算法的性能评价
• 2.3.1 源路由算法的性能评价
• 2.3.2 分布式路由算法的性能评价
• 2.4 QoS多播路由的难度
• 2.5 本章小结
• 第3章 满足时延约束的QoS多播路由算法
• 3.1 时延约束最小代价多播路由问题描述
• 3.2 几种满足时延约束的Steiner树问题的典型的启发式算法
• 3.3 时延受限低代价多播路由算法（一）
• 3.3.1 网络模型与问题定义
• 3.3.2 算法的基本思想和概念定义
• 3.3.3 算法基本过程
• 3.3.4 算法性能分析
• 3.3.5 仿真实验
• 3.4 时延受限低代价多播路由算法（二）
• 3.4.1 网络模型与问题描述
• 3.4.2 算法基本过程
• 3.4.3 算法性能分析
• 3.4.4 仿真实验
• 3.5 本章小结
• 第4章 满足时延和时延抖动约束的QoS多播路由算法
• 4.1 时延和时延抖动约束的多播路由问题的定义
• 4.2 典型的时延和时延抖动约束的多播路由启发式算法
• 4.3 典型的时延和时延抖动约束的Steiner树启发式算法
• 4.4 满足时延和时延抖动约束的低代价多播路由算法
• 4.4.1 问题描述
• 4.4.2 算法描述
• 4.4.3 算法性能分析
• 4.4.4 仿真实验
• 4.5 本章小结
• 第5章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢