基于IP网络的QoS约束组播路由算法研究

论文摘要

随着网络技术的飞速发展,当前通信网络带宽和处理能力的提高使网络能够提供更多的多媒体业务,也使得支持“点到多点”或“多点到多点”的组播通信方式成为网络支持多媒体业务的必要形式。组播路由是网络层具备的功能,组播问题的关键在于组播路由的确定,寻找简单、高效、健壮的组播路由算法一直是网络界致力研究但未完全解决的问题。另一方面,许多分布式的多媒体应用对时延、时延抖动、带宽以及包丢失率有不同的要求,这需要当前网络能够传送具有这些QoS要求的实时多媒体信息。因此,作为QoS为中心的网络体系结构中不可缺少的组成部分,基于IP网络的QoS约束组播路由算法的研究成为网络研究领域的重要内容和热点问题。 本文系统的研究了IP QoS的体系结构、典型服务模型和机制,并对相关的关键技术进行了介绍;阐述了IP QoS组播路由原理;并将现有QoS约束组播路由算法的研究成果进行了归纳、分类,其中详细分析了IP QoS约束的Steiner树算法;重点介绍了时延约束最小代价组播路由问题及其相关算法。 本文工作重心在于:分析总结了传统遗传算法、禁忌搜索算法和模拟退火算法各自的优缺点,并在此基础上结合禁忌搜索算法和模拟退火算法各自的优点,提出了一种改进的混合遗传算法TSSAGMA。该算法的适应度函数采用模拟退火算法的思想来确保在后期快速收敛,同时引入禁忌搜索算法的交叉和变异算子,来防止算法早熟。通过仿真实验表明,TSSAGMA混合遗传算法在解决时延约束最小代价组播路由的问题上优于传统算法,能够在较小的代价下搜索到较好的解。另外,本文还引入了边交换和路径交换的概念,提出了两种改进模拟退火算法:基于边交换的退火组播路由算法(SAESMA)和基于路径交换的退火组播路由算法(SAPSMA),并分别对它们的时间复杂度进行了证明。

论文目录

• 摘要
• Abstract
• 目录
• 第1章 绪论
• 1.1 本课题的选题意义
• 1.2 本文相关研究现状
• 1.3 论文研究内容和组织结构
• 1.3.1 论文的研究内容
• 1.3.2 论文的组织结构
• 1.3.3 论文的创新之处
• 第2章 IP QoS的体系结构
• 2.1 IP Qos概述
• 2.2 IntServ/RSVP服务模型
• 2.2.1 IntServ基本概念
• 2.2.2 IntServ/RSVP主要构件
• 2.2.3 资源预留协议RSVP
• 2.2.4 IntServ/RSVP的局限性
• 2.3 DiffServ服务模型
• 2.3.1 DS域采用的逐跳行为
• 2.3.2 流量管理
• 2.3.3 DS域的业务分类和业务调节
• 2.3.4 DiffServ的优缺点
• 2.4 MPLS与流量工程
• 2.4.1 MPLS原理
• 2.4.2 流量工程
• 2.5 子网带宽管理
• 2.6 小结
• 第3章 IP QoS组播路由技术研究
• 3.1 组播路由技术的发展背景
• 3.2 QoS组播路由
• 3.2.1 QoS组播路由网络模型定义
• 3.2.2 QoS组播路由问题的分类
• 3.3 组播路由算法
• 3.3.1 组播路由算法的分类
• 3.3.2 Steiner树问题及算法
• 3.3.3 QoS约束的Steiner树问题及算法
• 3.3.4 其它组播路由问题及算法
• 3.4 组播路由协议
• 3.5 小结
• 第4章 时延约束最小代价组播路由算法
• 4.1 时延约束最小代价组播路由
• 4.1.1 时延约束最小代价组播路由问题描述
• 4.1.2 时延约束最小代价组播路由相关算法
• 4.4 遗传算法
• 4.3 禁忌搜索算法
• 4.4 模拟退火算法
• 4.5 混合遗传算法TSSAGMA
• 4.5.1 TSSAGMA算法设计思想
• 4.5.2 适应度函数设计
• 4.5.3 编码
• 4.5.4 树的生成方法
• 4.5.5 初始群体的生成
• 4.5.6 选择
• 4.5.7 交叉
• 4.5.8 变异
• 4.5.9 收敛性说明
• 4.5.10 仿真分析
• 4.6 小结
• 第5章 基于模拟退火算法的时延约束最小代价组播路由算法
• 5.1 概述
• 5.2 基于边交换的模拟退火算法SAESMA
• 5.3 基于路径交换的模拟退火算法SAPSMA
• 5.4 时间复杂度分析
• 5.5 小结
• 第6章 总结与展望
• 6.1 总结
• 6.2 IP QoS约束组播路由技术展望
• 参考文献
• 在学研究成果
• 致谢