WDM光网络中的多播算法研究

论文摘要

近年来随着网络技术的不断发展和用户需求的不断变化,各种带宽需求较高的多播业务(如视频会议、高清晰数字电视、远程教学、网络游戏等)日益流行。另一方面,WDM技术的出现使得一根光纤可以提供巨大的带宽,从而使得在网络中支持大量高带宽需求的多播业务成为可能。因此,如何在WDM光网络中实现对多播业务的支持成了近年来光网络研究的热点之一。在WDM光网络中支持多播业务需要网络数据平面和控制平面的支持。目前,这两方面都还有许多问题需要深入的研究。本文主要研究了WDM光网络控制平面中与多播算法相关的问题,主要集中在以下几个方面:WDM网络中的多播约束路由问题、多播专用保护设计问题、多播共享保护设计问题和多播业务量疏导问题。在WDM光网络中,多播路由可能受到设备或光层传输限制的约束。本文第二章研究WDM光网络中的多播约束路由问题。主要贡献在于:(1)为了减少网络建设成本,WDM光网络中分光节点很可能是稀疏配置的。现有文献中提出的分光节点稀疏配置约束下的多播路由算法在建立路由所需的代价、建立光树的数目和计算复杂度方面均存在不同缺点。针对这些问题,本文提出了一种有效的分光节点稀疏配置约束下的多播路由算法并分析了其性能。(2)光信号在网络中传输还要受到一些物理层的传输约束,比如波长连续性约束和传输损伤约束。为了保证通信的目的节点能正确可靠的接收到信号,多播路由算法则需要考虑这些约束。据我们所知,目前尚无文献研究满足这些传输约束下的多播路由问题。针对这一问题,本文研究了光层传输约束(包括波长连续性约束、偏振模散射约束和放大器自激散射约束)下的多播路由问题并提出了一种多播路由算法。该算法在考虑传输约束的情况下,尽量使得计算出的多播路由所使用的代价小。计算机仿真结果表明,该算法可以在满足约束的同时有效地降低建树所使用的代价。在WDM光网络中,一根光纤的失效可能会导致多播业务的多个目的节点不能正常接收数据。因此,对多播业务提供保护是很重要的。本文第三章研究WDM光网络中的多播专用保护设计问题。主要贡献在于:(1)现有多播专用保护算法计算出的多播生存性路由中可能含有一些多余链路。针对这一问题,文中首先用改进的ILP(整数线性规划)模型重新描述了多播的专用保护问题,然后提出了两种启发式算法。这两种算法分别在计算多播生存性路由的过程中删除和避免形成多余链路。计算机仿真表明,这两种算法可以有效地减少多播生存性路由中的多余链路,因而比现有算法有更好的性能。在大多数情况下两种算法的性能和ILP最优解相当接近。(2)在无波长变换器和分光节点稀疏配置的网络中,现有的多播专用保护算法计算出来的保护路不能和工作树共享波长,从而增加使用的波长资源和计算保护路由失败的概率。针对这一问题,本文提出了一种分光节点稀疏配置和波长连续性约束下的多播专用保护算法。该算法通过构造辅助图的方法,使得找出的保护路满足与工作树共享波长的条件,从而减少建立生存性路由所需要的波长资源。另一方面,在波长连续性约束下,由于可以和工作树共享波长,该算法计算保护路由的成功率也是很高的。计算机仿真表明,在分光节点稀疏配置和波长连续性约束下,该算法能有效地提高波长利用率和降低网络阻塞率。共享备份资源可以有效减少消耗的保护资源,从而可以有效地提高资源的利用率。目前研究多播共享保护设计问题的文献还较少。本文第四章研究WDM网络中的多播共享保护设计问题。主要贡献在于:(1)研究了SRLG(共享链路风险组)约束下的多播共享保护问题。在SRLG约束下,有可能找不到和工作路SRLG分离的保护路径。这就是所谓的“陷阱(trap)”问题。分段保护可以有效地解决“陷阱”问题。然而,现有的多播分段算法都采用固定分段方式。固定分段方式有两个主要的缺点:第一,在有些情况下不能有效地避免“陷阱”问题;第二,采用固定分段方式不能有效地保证波长利用率的优化。为此,本文提出了一种更灵活的多播共享分段保护算法。该算法可以根据网络状态和多播树所经过的SRLG链路来确定多播树的分段方式,从而有效地避免“陷阱”问题和提高资源的利用率。(2)据我们所知,目前还没有文献研究分光节点稀疏配置下约束下的多播共享保护问题。为此,本文对分光节点稀疏配置约束下的多播共享保护问题进行了研究,并且提出了一种分光节点稀疏配置约束下的多播共享保护算法。该算法可以在分光节点稀疏配置的网络中实现自共享(同一棵多播树的保护路和工作树间的波长共享)和空闲容量共享(不同多播树的保护路间的波长共享)。仿真结果表明,通过共享可以大大地提高资源利用率和降低网络的阻塞概率。在WDM网络中,每个波长可以提供高达数十Gbps的传输容量。但是,很多多播业务连接请求的带宽都小于一个波长容量。为了提高波长的利用率,可以将低速的多播业务连接疏导在一根波长上进行传输。目前研究动态多播业务量疏导的文献还较少。现有的动态多播业务量疏导算法可以分成两类:第一类采用疏导图的方法来疏导动态多播业务;第二类采用尽量使用已有光树的方法来疏导新到的业务。第一类动态多播业务量疏导算法使用的疏导图的节点数目相当多,从而算法的复杂度很高;而第二类算法的波长利用率又比较低。为此,本文第五章研究动态多播业务量疏导问题。主要贡献在于:针对现有动态多播业务量疏导算法的缺点,本文提出了两种动态多播业务量疏导算法。这两种算法的基本思想是通过尽量扩展已有的光树来为新业务提供连接,从而提高波长利用率和避免构建分层图来进行疏导带来的高复杂度。仿真结果表明这两种算法可以有效地提高波长利用率和降低网络阻塞概率。

论文目录

• 中文摘要
• Abstract
• 第一章 绪论
• 1.1 WDM光网络技术概述
• 1.1.1 WDM光网络节点
• 1.1.2 光交换技术
• 1.1.3 WDM光网络结构
• 1.1.4 光网络控制和管理:GMPLS
• 1.2 国内外光网络研究现状
• 1.3 WDM光网络中的多播技术
• 1.3.1 WDM光网络中的多播机制
• 1.3.2 支持多播的节点
• 1.3.3 多播路由
• 1.3.4 多播业务的生存性
• 1.3.5 多播业务的疏导
• 1.4 WDM光网络多播研究现状及不足
• 1.5 全文主要贡献与内容安排
• 第二章 WDM光网络中的多播约束路由算法研究
• 2.1 研究背景
• 2.2 分光器稀疏配置约束下的多播路由算法研究
• 2.2.1 问题描述
• 2.2.2 ILP模型
• 2.2.3 MCNFH算法
• 2.2.4 仿真结果与分析
• 2.3 光层传输约束下的多播路由算法研究
• 2.3.1 光层传输约束分析
• 2.3.2 问题描述
• OLTC算法'>2.3.3 MRA_OLTC算法
• 2.3.4 仿真结果与分析
• 2.4 本章小结
• 第三章 WDM光网络中的多播专用保护算法研究
• 3.1 研究背景
• 3.2 无约束的多播专用保护算法
• 3.2.1 问题描述和ILP模型
• RRL算法'>3.2.2 OPP_RRL算法
• ARL算法'>3.2.3 SLP_ARL算法
• 3.2.4 仿真结果与分析
• 3.3 分光节点稀疏配置和波长连续性约束下的多播专用保护算法研究
• 3.3.1 研究动机
• 3.3.2 问题描述
• 3.3.3 SLPP算法
• 3.3.4 仿真结果与分析
• 3.4 本章小结
• 第四章 WDM光网络中的多播共享保护算法研究
• 4.1 研究背景
• 4.2 基于SRLG约束的多播共享分段保护算法研究
• 4.2.1 研究动机
• 4.2.2 问题描述及符号定义
• 4.2.3 链路代价设置
• 4.2.4 ESSP算法
• 4.2.5 仿真结果与分析
• 4.3 分光节点稀疏配置约束下的多播共享保护算法研究
• 4.3.1 研究动机
• 4.3.2 问题描述及符号定义
• 4.3.3 分光节点稀疏配置约束下的波长共享
• 4.3.4 链路代价设置
• 4.3.5 SSSMP算法
• 4.3.6 仿真结果与分析
• 4.4 本章小结
• 第五章 WDM光网络中的多播业务量疏导算法研究
• 5.1 研究背景
• 5.2 网络节点结构
• 5.2.1 支持疏导的OXC
• 5.2.2 支持多播业务疏导的OXC
• 5.3 问题描述
• 5.4 多播疏导策略
• 5.5 动态多播业务量疏导算法描述
• 5.5.1 SETG算法
• 5.5.2 METG算法
• 5.6 仿真结果与分析
• 5.7 本章小结
• 第六章 WDM光网络中的多播算法的仿真实现
• 6.1 概述
• 6.2 仿真软件的总体框架
• 6.3 保护算法仿真软件的实现
• 6.4 重要伪代码
• 第七章 全文总结
• 7.1 研究工作总结
• 7.2 展望
• 致谢
• 参考文献
• 个人简历
• 本文作者在攻读博士期间发表、录用和投稿的论文
• 攻读博士期间参加的科研项目
• 作者在攻读博士学位期间的获奖情况