保证服务质量的多播源路由算法研究

论文摘要

多播技术已有广泛的应用。对于实时性要求高的多播应用,多播路由必须保证服务质量。为此,本文研究保证服务质量的多播路由问题,并提出三个多播源路由算法以保证服务质量。 多播路由问题实质上就是构建覆盖源端和接收端,并满足应用服务质量要求的路由树的问题。构建代价最小且保证服务质量的多播路由树问题是NP难的。目前已出现了很多启发式多播路由算法,有的算法可以构建低代价的多播树,但是时间复杂度很高,对于大规模的网络来说,应用价值不大;有的算法具有较低的时间复杂度,但是,构建的多播树代价不甚理想。本文在研究已有算法的基础上,提出新的多播路由算法,试图在算法的有效性与算法的时间复杂度之间取得平衡。 首先,本文有效地分析了经典的时延约束多播路由算法—KPP算法,并提出了一个改进的KPP算法。新算法在构造多播树过程中,考虑到了KPP算法未考虑的转发节点加入带来的影响,并通过路径的动态选择来消除此影响;同时,使用两个策略对多播树进行优化,得到低代价的多播树。实验表明,新算法构造的多播树与KPP算法构造的多播树相比,代价低9%到10%。 其次,在多播路由中,使用的链路共享程度越高越能节约网络资源。基于对链路共享重要性的理解,本文提出了链路可共享性的新概念,链路可共享性是对链路共享程度的定量。同时,基于链路可共享性,提出了一个快速有效的时延约束多播路由算法SBMR。实验表明,SBMR算法构建的多播树有72%比KPP算法构建的多播树更优,代价降低13%,启用的链路数减少9%,而且CPU时间减少15%。与DCSP算法相比,SBMR算法以增加28%的CPU时间为代价,构建的82%的多播树比DCSP算法更优,代价降低15%,而且启用的链路数减少11%,达到了更好的链路共享。 最后,考虑到时延抖动是服务质量的重要因素,本文提出满足时延和时延抖动约束的多播路由算法EDDVCMR。EDDVCMR算法首先对Dijkstra最短路径算法进行扩展,使得扩展后的Dijkstra算法不仅可以找到多播源到各接收端的时延最小路径,还可以找到时延介于某一区间段的路径;然后,从找到的若干路径中抽取一组满足时延抖动约束的路径,从而组建一棵满足时延和时延抖动约束的多播树。实验表明,EDDVCMR算法与DVMA算法相比,有高出7%的求解成功率,同时,执行的CPU时间减少36%。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 引言
• 1.1 多播技术概述
• 1.2 多播技术基本原理
• 1.2.1 多播地址分配
• 1.2.2 多播组成员管理
• 1.2.3 多播报文转发
• 1.2.4 多播路由协议
• 1.3 多播技术最新发展
• 1.3.1 保证服务质量
• 1.3.2 无线网络中的多播
• 1.4 本文工作及结构
• 第2章 保证服务质量的多播路由
• 2.1 服务质量路由概述
• 2.2 网络模型
• 2.3 QoS度量
• 2.4 多播路由主要算法介绍
• 2.4.1 KPP算法
• 2.4.2 BSMA算法
• 2.4.3 SL算法
• 2.4.4 Widyono算法
• 2.4.5 RB算法
• 2.5 小结
• 第3章 多播路由KPP算法的改进
• 3.1 引言
• 3.2 多播树的优化
• 3.3 算法描述
• 3.4 算法正确性
• 3.5 模拟实验
• 3.5.1 目的节点密度为10％时的比较
• 3.5.2 目的节点密度为15％时的比较
• 3.5.3 目的节点密度为20％时的比较
• 3.6 小结
• 第4章 基于链路可共享性的多播路由算法
• 4.1 引言
• 4.2 链路可共享性的概念
• 4.3 基于链路可共享性的算法
• 4.4 算法的正确性和复杂性
• 4.5 算法模拟实验
• 4.5.1 多播树代价的比较
• 4.5.2 多播树所含链路数的比较
• 4.5.3 算法执行时间比较
• 4.6 小结
• 第5章 时延及抖动约束的多播路由算法
• 5.1 引言
• 5.2 带有时延和抖动约束的多播路由问题
• 5.3 算法描述
• 5.3.1 扩展的Dijkstra最短路径算法
• 5.3.2 满足时延及抖动约束的多播路由算法
• 5.4 算法分析
• 5.5 模拟实验
• 5.5.1 算法求解成功率比较
• 5.5.2 算法执行时间比较
• 5.6 小结
• 结论
• 参考文献
• 致谢
• 附录A 攻读学位期间所发表的学术论文目录
• 附录B 攻读学位期间所参与的项目目录