应用层多播与Steiner算法的研究

论文摘要

随着网络带宽和处理能力的提高,网络为我们提供了更多的多媒体业务,其中许多业务都要求网络具有多播(multicast)能力。IP多播是最早出现的有效多播方式,但由于IP多播方案的技术性问题和IP多播方案所带来的市场问题,使得IP多播没有在全球范围内成功推广,即使在IP多播方案在提出几年以后仍然没有在Internet上成功的部署起来。因此提出了应用层多播的解决方案。它的基本思想是：在不改变网络基础设施,不依赖网络层提供多播服务的情况下,在应用层实现多播服务功能,供用户使用。目前已经提出了许多解决应用层多播问题的算法,本文中有简单描述。而Steiner树问题是一个历史性的数学难题,在网络设计、多播路由、VLSI设计等方面有广泛的应用。考虑到多播路由与Steiner树之间存在的对应关系,本文确定了Steiner树启发式算法作为本文的研究重点。本文详细介绍了多播技术,区分了IP多播和应用层多播的特点,对应用层多播做了概述。基于Steiner树的启发式算法是目前解决多播问题的有效方法,文中给出了Steiner树问题定义,并简要叙述了其精确求解算法、典型的启发式算法和贪心算法。通过分析概括了典型启发式算法的框架,并在此基础上分别设计了基于路径中重用关键边和关键顶点的Steiner树的启发式算法,使每次添加的路径尽可能得到了重用关键的边和点,并且通过示例与实验分析和验证了所设计算法的正确性和优越性。本文最后设计了改进的基于加权的Steiner树启发式算法,该算法在基本启发式算法的基础上,结合关键节点和关键边的重要信息,在此基础上提出了加权的启发式算法。实验结果证明,该算法运算时间短,求得解的质量高。

论文目录

• 摘要
• Abstract
• 引言
• 1 研究背景
• 1.1 选题背景及理论意义
• 1.2 多播通信国内外研究现状
• 1.3 基于Steiner的多播路由算法研究现状
• 2 多播相关技术概述
• 2.1 多播路由
• 2.1.1 多播路由产生的背景
• 2.1.2 多播路由的特点
• 2.1.3 多播路由算法分类
• 2.1.4 多播路由的策略
• 2.2 应用层多播概述
• 2.2.1 IP多播的介绍
• 2.2.2 应用层多播的现状及意义
• 2.2.3 应用层多播的特点
• 2.2.4 应用层多播的算法
• 2.3 小结
• 3 启发式算法分析
• 3.1 Steiner树问题
• 3.2 问题定义与分析
• 3.3 Steiner启发式算法
• 3.3.1 基于最短路径的Steiner树启发式算法
• 3.3.2 基于最小生成树的Steiner启发式算法
• 3.3.3 最短距离启发式算法
• 3.3.4 平均费用启发式算法
• 3.3.5 改进型平均费用启发式算法
• 3.3.6 收缩启发式算法
• 3.3.7 2-TH启发式算法
• 3.3.8 3-TH启发式算法
• 3.3.9 P3-TH启发式算法
• 3.3.10 各种启发式算法的性能比较
• 3.4 基于重用边的启发式算法
• 3.4.1 n-平均边数费用启发式算法
• 3.4.2 最短路的平均边数费用的启发式算法
• 3.4.3 子树平均边费用启发式算法
• 3.4.4 基于关键边的启发式算法
• 3.5 基于重用顶点的启发式算法
• 3.5.1 平均度数最短路启发式算法
• 3.5.2 子树平均度费用启发式算法
• 3.5.3 基于关键节点的启发式算法
• 3.6 基于重用边和顶点的启发式算法的实验
• 3.7 小结
• 4 基于加权的Steiner树启发式算法
• 4.1 算法分析与设计
• 4.2 MPH算法的分析
• 4.3 KBMPH算法的分析
• 4.4 MPH-BW的设计与实现
• 4.4.1 算法原理
• 4.4.2 相关概念及公式
• 4.4.3 算法的流程图
• 4.4.4 算法过程描述
• 4.5 小结
• 5 MPH-BW在应用层多播中的应用
• 5.1 应用层组播路由的问题
• 5.2 WSF-ALM算法
• 5.2.1 算法关键步骤
• 5.2.2 处理环路和失效
• 5.3 实验部分
• 5.3.1 实验数据描述
• 5.3.2 实验结果分析
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢