WDM网络及IP网络中的多播算法研究

论文摘要

多播传输能有效节约带宽资源,并具有高效、灵活、可控等诸多优点,是实现多媒体应用的重要方法。近年来,光网络的迅速普及,WDM（Wavelength Division Multiplexing）网络成为未来Internet骨干支撑网的首选。随着光学技术日益成熟,原来需要在业务交换层面完成的多播业务被移植到了光层,光网络多播技术正是近年来广受关注的热点之一。本文主要研究了WDM网络和IP网络中的多播算法,针对以下三方面的问题进行了深入研究:WDM网络中的多播保护算法,OBS网络中多播汇聚机制以及基于网络编码的多播业务静态规划算法。WDM技术可以大大提高链路的传输容量,同时也使网络部件失效时可能遭受比传统网络更大的损失,网络的生存性问题日渐突出,WDM网络中多播保护问题受到了广泛的关注。本文第二章首先对现有的启发式保护算法进行分析,发现大多数启发式算法没有考虑工作树与保护树之间的链路复用问题,导致其带宽利用率低,阻塞率高;然后通过数学模型描述了针对单链路失效情况下的多播保护树;再提出了两种基于路径分离的改进启发式算法。这两种改进算法分别从不同的角度描述了工作树与保护树之间的相互影响关系,再由此确定了路由过程中的冗余链路,并分别根据冗余边的特点设计路由算法,减少多播保护的资源消耗。光突发交换（OBS, Optical Burst Switching）作为一种IP-over-WDM的光交换技术,结合了波长路由交换和光分组交换的优点,同时也克服了二者的不足,能提高带宽利用率、减少波长资源消耗,降低业务阻塞率,对OBS网络中的多播实现方式的研究具有现实意义。本文第三章提出一种基于稀疏分光配置的OBS网络的共享多播机制。该机制对包含相同分光节点的业务进行汇聚,并且在资源预约过程中引入了优先级来区分主干链路和分枝链路,保证多播树的主干链路能优先抢占资源。相比传统多播机制,该方式的多播树汇聚算法的冗余度更低,且能减少多播业务的丢包率和冗余包的数量,提高资源利用率。本文最后研究了IP网络中基于网络编码的多播业务静态规划问题。网络编码是近年来IP网络中的研究热点,通过中间节点对传输数据编码的方式实现多播最大流传输。使用网络编码可以在很大程度上提高网络吞吐量,但是不可避免地会增加网络的复杂性。现有的启发式路由算法通常只能为单个多播业务寻找最优路由,无法优化网络的整体吞吐量;而用普通整数线性规划（ILP, Integer LinearProgramming）模型描述网络编码业务,通常会因为网络编码业务的多播图复杂,导致问题规模变大,求解困难。运用column generation算法解决静态业务规划问题,对多个约束条件进行拉格朗日松弛,再为松弛系数赋予具体的物理含义,使系数之间存在相互关联关系,并根据物理含义进行路径更新。与启发式算法相比,column generation从整体上提高了网络的吞吐量,改善了网络的负载均衡。同时,与普通ILP规划算法相比,column generation的路径更新更有针对性,无需计算大量备选路径,问题规模小,收敛速度更快,且能够解决部分ILP无法处理的大规模规划问题。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 IP 多播发展概述
• 1.1.1 多播的原理及优势
• 1.1.2 多播生成树
• 1.1.3 IP 多播的发展方向
• 1.2 光多播技术的发展概述
• 1.2.1 WDM 网络发展简介
• 1.2.2 WDM 网络中多播研究进程
• 1.2.3 光多播所面临的主要问题
• 1.3 全文的研究思路及内容安排
• 第二章 WDM 网络中的多播保护算法
• 2.1 研究背景
• 2.1.1 现有的保护机制算法及其优缺点
• 2.1.2 单链路失效情况下多播保护模型描述
• 2.2 基于路径分离机制的改进算法
• 2.2.1 合并路径对算法
• SDP 算法中冗余边的产生'>2.2.1.1 OPP_SDP 算法中冗余边的产生
• 2.2.1.2 合并路径对算法
• 2.2.2 动态重路由算法
• 2.2.2.1 工作树与保护树的相互影响关系
• 2.2.2.2 动态重路由算法
• 2.3 仿真与结果分析
• 2.4 本章小结
• 第三章 OBS 网络中的多播机制
• 3.1 OBS 网络中的多播实现
• 3.1.1 OBS 网络的基本结构
• 3.1.2 稀疏分光配置网络的多播
• 3.2 OBS 多播机制研究
• 3.2.1 现有的OBS 多播汇聚机制
• 3.2.2 基于优先级抢占的资源预约机制
• 3.2.3 算法实现
• 3.3 仿真以及结果分析
• 3.4 本章小结
• 第四章 基于网络编码的静态多播业务规划
• 4.1 网络编码的基本原理
• 4.1.1 多播最大流传输概念
• 4.1.2 网络编码的定义
• 4.1.3 网络编码的性能分析
• 4.1.4 网络编码现有的路由算法及优缺点
• 4.2 用 column generation 求解多播业务规划
• 4.2.1 两种基本的ILP 模型描述
• 4.2.1.1 Node-link 模型
• 4.2.1.2 Link-path 模型
• 4.2.2 网络编码业务的模型描述
• 4.2.3 松弛变换
• 4.2.3.1 可用拉格朗日松弛的约束特征
• 4.2.3.2 column generation 中的松弛方法
• 4.2.3.3 松弛系数的关联关系及物理含义
• 4.2.4 迭代求解
• 4.3 仿真及结果分析
• 4.4 本章小结
• 第五章 全文总结
• 致谢
• 参考文献
• 攻读硕士学位期间的研究成果
• 个人简历