（通信与信息系统专业论文）wdm光网络中基于网络编码的多播业务疏导研究.pdf

重庆邮电大学硕士论文摘要 摘要 随着光网络的发展与普及，作为未来i n t e m e t 骨干支撑的w d m 光网络组网技 术成为主流趋势。同时，随着光学技术的日益成熟以及视频会议、远程教学等多播 业务的日益兴起，使得光网络多播技术倍受关注。本文着手研究w d m 光网络多播 技术的相关问题，主要包括光层多播路由算法、光层多播业务疏导算法以及具有抗 毁能力的光层多播业务疏导算法。 传统的w d m 光层多播路由算法均是通过存储转发的路由机制构建多播光树， 但此类算法无法最大化网络吞吐量、均衡网络负载，网络资源无法充分利用。为有 效解决此问题，本文第二章介绍了网络编码的基本理论及优势，并结合已有的基于 网络编码的多播路由算法，将网络编码技术引入到w d m 光网络中，分析了光网络 中基于网络编码的多播路由算法和1 + n 保护算法。 w d m 光网络中波长传输速率和业务请求带宽之间的巨大差距，使得为每个业 务请求分配独立波长通道的资源利用率低且不经济。因此，需要研究w d m 光网络 中如何将多个低速业务请求聚合起来传输，有效实现业务的疏导。本文第三章研究 了w d m 光网络中的多播业务疏导问题，分析了一种具有多播分光、业务疏导以及 编解码功能的交叉连接结构( g m c c o x c ) ，并给出了一种基于网络编码的动态多播 业务疏导算法。该算法结合网络编码均衡网络负载的优势，使链路上的波长带宽资 源能够得到更为充分的利用。仿真结果表明，该算法有效的降低了多播业务请求的 带宽阻塞概率，提高了链路资源利用率。 传统光网络生存性机制主要包括保护和恢复两大类，保护机制的资源预留性以 及恢复机制的动态寻路性均会影响网络的生存性性能。本文第四章研究了w d m 光 网络中多播业务疏导的生存性问题，给出了一种基于网络编码的具有抗毁能力的多 播业务疏导算法。该算法充分利用网络编码均衡网络负载以及提高网络生存性的优 势，通过网络编码疏导多播业务请求，同时通过网络编码码字构造并引入少量冗余 信息使网络具有抗毁特性。仿真结果表明，该算法使网络具备抗毁能力的同时大大 降低了业务带宽阻塞概率。 j f 关键词：波分复用，多播网络，业务疏导，网络编码，抗毁 重庆邮电大学硕士论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fo p t i c a ln e t w o r k , t h et e c h n o l o g yo fw d mn e t w o r k s b e c o m e st h ec o r et e c h n o l o g yo fn e x tg e n e r a t i o ni n t c r n c tb a c k b o n en e t w o r k a tt h es a m e t i m e ，t h em a t u r eo fo p f i c st e c h n i c a ls k i l l sa n dt h ep o p u l a r i z a t i o no fm u l t i c a s ta p p l i c a t i o n s s u c h 勰v i d e oc o n f c r e n c i n ga n di n t e r a c t i v ed i s t a n c el e a r n i n gm a k em u l t i c a s ts k i l l sm o r e a n dm o r ea t t e n t i o n t h i sp a p e rm a i n l yf o c u so nt h ep r o b l e r no fm u l t i c a s ts k i l l si nw d m n e t w o r k s ，i n c l u d i n gm u l t i c a s tr o u t i n ga l g o r i t h m 、m u l t i c a s tt r a f f i cg r o o m i n ga n dm u l t i c a s t t r a f f i cg r o o m i n gw i ms u r v i v a b i l i t y f o rt r a d i t i o n a lw d mn e t w o r k s ，t h er o u t i n ga l g o r i t h mo fm u l t i c a s ti no p t i c a ll a y e ri s t h r o u g hs t o r e f o r w a r dr o u t i n gm e c h a n i s mt ob u i l dt h em u l t i c a s tl i g h t - t r e e b u tt h e r ea l e m a n yd r a w b a c k ss u c h 笛t h en e t w o r kt h r o u t h p u tc a nn o tm a x i m i z e d ，t h ef e a t u r eo fl o a d b a l a n c i n gi sn o te n o u g hf a v o r a b l ea n dt h eu t i l i z a t i o no fn e t w o r kr e s o u r c e si sn o te n o u g h e f f e c t i v e i n t h es e c o n dc h a p t e r , t h eb a s i ct h e o r ya n da d v a n t a g e so fn e t w o r kc o d i n g t e c h n o l o g yi si n t r o d u c e d , a n dt h i st e c h n o l o g yw i l lb ei n t r o d u c e di n t ot h ew d m n e t w o r k s c o m b i n e dw i n lt h ee x i s t i n gm u l t i c a s tr o u t i n ga l g o r i t h mb a s e do nn e t w o r kc o d i n g 。a tl a s t , a n a l y z et h ea l g o r i t h mo f m u l t i c a s tr o u t 吨a n d1 + np r o t e c t i o nb a s e do nn e t w o r kc o d i n gi n w d mn e t w o r k s i nw d mn e t w o r k s ，t h e r ei sah u g eb a n d w i d t hg a pb e t w e e nt h e c a p a c i t yo fa w a v e l e n g t ha n dt h er e q u i r e db a n d w i d t ho fl o w - r a t et r a f f i cs t r e a m s t oa c c o m m o d a t es u c h k i n do fl o w - r a t et r a f f i cs t r e a mw i t ho n eh g h t - p a t l lw i l ll e a dt oi n e f f i c i e n tr e s o u r c e u t i l i z a t i o n s oi ti sn e c e s s a r yt oi n v e s t i g a t et h et r a f f i cg r o o m i n g ( a l l o wan u m b e ro f s e s s i o n sw i t hs u b w a v e l e n g t hg r a n u l a r t i e st os h a r et h eb a n d w i d t ho faw a v e l e n g t hc h a n n e l ) p r o b l e mi nw d m n e t w o r k s i nt h et h i r dc h a p t e r , t h em u l t i c a s tt r a f f i cg r o o m i n gp r o b l e m i nw d mn e t w o r k si si n v e s t i g a t e d w ea n a l y z ean e wo p t i c a lc r o s s - c o n n e c t i o nn o d e s t r u c t u r e ，w h i c hi n c l u d et h ef e a t u r e so fm u l t i c a s ts p l i t t i n g , t r a f f i cg r o o m i n g ，e n c o d i n ga n d d c c o d i n g 。a n dp r o p o s ea l la l g o r i t h mo fm u l t i c a s tt r a f f i cg r o o m i n gb a s e do nn e t w o r k c o d i n gc o n s i d e r i n gt h ea d v a n t a g e so fn e t w o r kc o d i n gi nl o a db a l a n c i n g n 璩s i m u l a t i o n r e s u l t ss h o wt h a tt h ea l g o r i t h me f f e c t i v e l yr e d u c e st h eb a n d w i d t hb l o c k i n gp r o b a b i l i t y a n di n c r e a s e st h el i n kr e s o u r c eu t i l i z a t i o n n l es t r a t e g yo fs u r v i v a b i l i t ym a i n l yi n c l u d e sp r o t e c t i o na n dr e s t o r a t i o ni no p t i c a l n e t w o r k s 朋1 er e s o u r c er e s e r v a t i o no fp r o t e c t i o nm e c h a n i s m sa n dt h e d y n a m i c 重庆邮电大学硕士论文 p a t h - f i n d i n go fr e s t o r a t i o nm e c h a n i s m sw i l la f f e c tt h en e t w o r kp e r f o r m a n c e i nt h ef o r t h c h a p t e r , t h em u l t i c a s tt r a f f i cg r o o m i n gp r o b l e mw i t hs u r v i v a b i l i t yi nw d mn e t w o r k si s s t u d i e d a n da l la l g o r i t h mf o rm u l t i c a s tt r a f f i cg r o o m i n g 、析t l ls u r v i v a b i l i t yb a s e do n n e t w o r kc o d i n gi sp r o v i d e d t h ea l g o r i t h mm a k e sf u l lu s eo ft h ea d v a n t a g e so fn e t w o r k c o d i n gi n1 0 a db a l a n c i n ga n dn e t w o r ks u r v i v a b i l i t y ：g r o o m i n gt h em u l t i c a s ts e r v i c e s t h r o u g hn e t w o r kc o d i n g ，a n dg u a r a n t e 圮t h es u r v i v a b i l i t yt h r o u g ht h ee o d e w o r d s c o n s t r u c t i o nb ye n c o d i n ga n di n t r o d u c t i o nas m a l la m o u n to fr e d u n d a n ti n f o r m a t i o 豇砀e s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h me f f e c t i v e l yr e d u c e st h eb a n d w i d t hb l o c k i n g p r o b a b i l i t ya n dm a k e st h en e t w o r km o r er e l i a b l e k e y w o r d s ：w d m ，m u l t i c a s tn e t w o r k ，t r a 伍cg r o o m i n g ，n e t w o r kc o d i n g ，s u r v i v a b i l i t y r i 重庆邮电大学硕士论文 第一章绪论 第一章绪论 i n t e r n e t 业务爆炸性的增长和高性能光网络设备( 如光交叉连接器o x c 、分插复 用器o a d m 、分光器l i g h t s p u t t e r 、光缓存o p t i c a l - b u f f e r 等) 的不断成熟，使得波分 复用( w d m ) 技术成为下一代骨干网络的核心技术。w d m 技术允许在一根光纤中同 时传输多路不同波长的光信号，每个波长的传输速率高到g b p s ，为高速大容量宽带 业务的传输提供了有效途径。利用w d m 技术和波长路由选择构架光层( o p t i c a l l a y e r ) ，对高层提供大容量且结构灵活的传输通道，将成为光网络骨干网的核心传输 方式。 1 1w d m 光网络 波分复用( w a v e l e n g t hd i v i s i o nm u l t i p l e x ，w d m ) 是提高一根光纤传输容量的主 要技术，类似于无线电系统中的频分复用技术。它将多个不同波长的光载波信号( 携 带各种不同信息) 在发送端经复用器( m u l t i p l e x e r ) 汇合在一起，并耦合到同一根光纤 中进行传输，在接收端使用解复用器( d e m u l t i p l e x e r ) 将各个波长的光载波分离，然 后由光接收机作进一步的处理以恢复原始信号，其原理图如图1 1 所示。只要相邻 波长信道的间隔距离足够远，不同的波长信道之间就不会产生相互干扰，因此在一 根光纤中可实现多路光信号的复用传输。另外，双向传输可将两个方向的信号分别 安排在不同的波长上实现。w d m 技术大大地提高了光纤的传输容量，由于市场的 驱动和相关技术的研究突破，其发展十分迅猛【h 】。 u 匕入 1 illl 1 至厂 厂 互 、 稚 丑“五赣 t n 厂 2 旺 囝一 妯 聪 盈 坠广 厂 乙 光纤 龆 五厂 厂 1 1 、 图1 1w d m 原理图 为了将w d m 提供的巨大原始带宽转化成实际组网时可灵活使用的带宽，需要 引入灵活的光节点以实现光层互联。因此，w d m 光网络在光域中引入了相当于电 域的交换和路由功能，节点能直接在光域中将经过而非起止于该节点的业务进行交 换处理，旁路掉本地的电处理，从而大大减轻了节点上进行电处理的压力，消除了 中间节点的电处理瓶颈【l 】。其常用的光层设备有光交叉连接器( o p t i c a lc r o s sc o n n e c t 。 重庆邮电大学硕士论文第一章绪论 o x c ) 和光分插复用器( o p t i c a l a d d d r o pm u l t i p l e x ，o a t ) m ) ，如图1 2 所示。o x c 的 功能类似于s d h 网络中的数字交叉连接器( d x c ) ，它能将一个波长信道上的信号直 接交换到出口光纤的相应波长中( 如果没有使用波长转换器，则出入口的波长必须 相同，以满足波长连续性要求；如果使用了波长转换器，则出入口波长可以不同) 。 利用o x c 可以构建复杂的w d m 光网络，如w d m 网状网。o a d m 的功能类似于 s d h 网络中的分插复用器，它能够提供业务的旁路或者上厂f 功能，且直接以光信 号作为操作对象；同时，o a d m 为w d m 光传送网提供了异步接入的功能，使得光 网络设备可以提供与各种业务的直接接口，例如s d h 、a t m 、帧中继以及p 等各 种形式的业务均可以通过占用o a d m 提供的某个波长接口直接进入到w d m 光传 送网进行传输。通过o a d m 或者o x c 构建的w d m 网络的一个共同特点是低速业 务流可以经过多个节点仍在光域中传输，而无须经过电处理；而且它们能够在入纤 和出纤之间进行波长交换的功能也使得光网络的重构成为可能。 入光纤 m i i 复f f l j 光开关 复用嚣 蚓茎：卜一 广胡二坠 严划 上， ( a ) o x c 结构示意图( b ) o a d m 功能框图 图1 2 0 x c 与o a d m 结构框图 w d m 技术具有的主要特点【2 】如下： w d m 技术能够充分利用光纤潜在的巨大带宽资源，使得一根光纤中的传播 容量是以往的几倍到几十倍，从而降低了网络建设成本，使之具有很大的应用价值 和经济价值。 由于w d m 技术中同一根光纤传输的波长信号之间是彼此独立的，因此特 性完全不相同的信号也是可以在同一根光纤中传输，进而完成各种业务的综合与分 离，实现多媒体业务信号的混合传输。 w d m 技术对数据传输的格式是透明的，即w d m 技术与电调制方式以及信 号传输速率是不相关的。一个w d m 系统可以承载多种格式的“业务”信号，以及 a t m 、i p 或其他格式的信号。正是由于这种透明性，使得w d m 系统完成的是透明 传输，对于“业务层信号来说，w d m 的每个波长就类似于一根“虚拟 光纤。 w d m 技术在单模光纤中的原理是将n 个波长复用起来，并把复用后的信 号耦合到一根光纤中进行传输，使得在大容量长途传输时可以有效的节约光纤资源， 2 重庆邮电大学硕士论文 第一章绪论 提高了单模光纤中的传输利用率。 w d m 系统多用于大容量长距离的传输，以便于多信道复用光放大器，这也 可以达到简化系统结构和设计的目的，直接减少了大量的投资和维护费用。 当网络需要扩充时，w d m 技术是理想的扩容手段，同时也是引入宽带业务 的方便手段：增加一个新的波长就可以引入所需要的新业务和新容量。 利用w d m 技术选路可以实现网络的交换和恢复，进而实现未来透明、灵 活、经济且具有高度生存性的光网络。 1 2w d m 光网络多播技术 随着光网络的迅速发展与普及，w d m 光网络组网技术受到了越来越多的关注。 另一方面，随着光学技术的日益成熟，功能越来越完善的各种光通信器件和设备的 大批涌现，使得许多原本需要在业务交换层面完成的工作被更多地移植到了光层。 光网络多播技术 5 1 就是一个典型的例子。 1 2 1 光网络多播概述 光网络多播有多种实现方式，根据网络拓扑的不同结构特点，光网络可以分为 单跳光网络和多跳光网络，如图1 3 所示。其中单跳光网络( s i n g l e - h o po p t i c a l n e t w o r k ) 通常采用基于w d m 的广播与选择机制( b r o a d c a s ta n ds e l e c t ) 实现通信，其 关键技术在于介质访问协议的设计，它主要应用于局域网或者城域网。单跳光网络 中的多播技术研究始于上世纪9 0 年代，文献 6 1 1 鞫述了相关的研究进展和成果。 图1 3 可实现多播的光网络分类 3 出 重庆邮电大学硕士论文 第一章绪论 多跳光网络( m u l t i - h o po p t i c a ln e t w o r k ) 通常具有网状( m e s h ) 结构，完成一次通信 时，除了源、目的节点外，通常还需要多个中间节点的参与。按照网络中节点的设 备类型和信号传输方式的不同，可以将多跳光网络分为透l 斐j ( t r a n s p a r e n t ) 光网络和非 透n 刃( o p a q u e ) 光网络两种类型。在透明光网络中，信息以全光方式进行端到端的传 输，包括由全光光交叉连接设备( o x c ) 组成的波长路由网络( w a v e l e n g t hr o u t i n g n e t w o r k ) ，光突发交换( o b s ，o p t i c a lb u r s ts w i t c h i n g ) 网络和光分组交换( o p s ，o p t i c a l p a c k e ts w i t c h i n g ) l 网络等。与透明光网络不同，在非透明光网络中，信号在每个中间 交换节点都需要光电光( o e o ) 的转换。亦即，非透明光网络中的业务传输是基于 w d m 的全光传输( 光域处理) ，而业务交换则完全由电设备完成( 电域处理) 。混合网 络是指网络中同时具有全光波长路由设备和非透明的电交换设备，在信号端到端传 输的过程中可能需要o - e 0 转换，从这个意义上讲它属于非透明光网络；但由于混 合网络中具有全光o x c ，使得其连接控制和管理具有类似于波长路由网络的某些特 点，如需要满足波长连续性限$ i j ( w a v e l e n g t hc o n t i n u i t yc o n s t r a i n t ) 等非透明光网络所 没有的约束条件。非透明光网络由电交换设备和光纤链路组成，多播交换由电交换 设备完成，多播传输由光纤链路完成，但无论从协议设计还是从硬件支持方面来看， 非透明光网络的多播问题均可归纳为传统电交换网络的多播问题。 文献 7 】首次将光路( 1 i g h t p a t h ，跨越多个全光o x c 设备的透明波长通路) 的概念 扩展为光树( 1 i g h t - t r e e ) 。其基本思想是通过在o x c 中配置分光器( 1 i g h ts p h 钍砷，构造 波长级别的全光透明树状通路，从而实现点到多点的全光传输。光树的引入使得网 络中的每个节点同时具备了多个逻辑邻节点，减少了业务的传输跳数，提高了网络 资源利用率。 在w d m 光网络中传输多播业务需要硬件设备的支持。文献 8 提出了著名的 s a d ( s p l i t t e ra n dd e l i v e r y ) 交换模块，利用此s a d 模块可以构造任意规模、支持多播 的交叉连接结构( m c o x c ，m u l t i c a s tc a p a b l ec r o s sc o n n e c t o r ) 。另一种支持多播业 务传输的硬件设备具有t a c ( t a pa n dc o n t i n u e ) 功能，即指从光传输信号中取出一部 分功率输出到本地电端口( 如果本地是多播业务的目的节点之一) ，而余下的功率沿 光路继续传输。文献 9 】最早提出t a c 模型，由于它不需要分光器件，故多播路径不 是树状结构，而是一条从源点出发，经过所有多播目的节点的光路。文中证明了计 算一条多目的最佳路径( 经过所有给定的一组目的节点，且代价值最小) 问题是不可 解( i n t r a c t a b l e ) 的，并给出了一种近似求解法。 与一般网络中的多播路由计算问题相比，w d m 光网络的多播存在着一些特殊 的约束条件，如波长连续性约束等。在波长连续性约束下，路径的计算与波长的分 配是紧密相关的。约束条件下的光路计算问题称为融聊岖沁妇ga n dw a v e l e n g t h a s s i g n m e n t ) i h l 题，对应的光树计算问题称为m c r w a ( m u l t i c a s tr w a ) 问题。 4 重庆邮电大学硕士论文 第一章绪论 根据业务的到达情况，可以将m c - r w a 问题分为静态和动态两类。静态 m c r w a 问题是指在给定一组多播业务请求的情况下，求解全局最优的光树配置 ( 包括路由和波长分配) 方案。静态问题通常采用整数线性规划( i l p ，i n t e g e rl i n e a r p r o g r a m m i n g ) 的方式描述。文献 1 0 】以最小化波长数目为优化目标，并给出了一组求 解该问题的启发式算法。文献【1 1 】以最大化连接数目为优化目标，文献并没有给出 求解该问题的启发式算法，但是给定了优化指标的上限。在动态m c - r w a 问题中， 多播业务请求随机的到达和离开，要求在不改变现有业务连接的情况下，尽量用最 优的方式满足新到达的业务请求。如果现有的网络资源无法满足该业务请求，则此 请求被阻塞。因此，动态m c r w a 问题通常以业务连接请求阻塞概率为评价指标。 现有的求解方法均是将路由选择与波长分配作为两个独立的子问题来讨论，并且引 入备用路由的方式( 即预先计算一组多播路由，并按照一定的策略从中挑选路由，检 查在波长连续性约束下，该路由是否可以成功分配波长，若不成功，再选下一条路 由，直至备用路由全部被检查) 。文献 1 2 1 4 均是根据这个策略讨论动态m c - r w a 的阻塞概率问题。其中，文献 1 2 1 采用首次命中法( f i r s t - f i t ) 分配波长，而且从备用 路径集合中选取多播树的顺序是固定的：文献 1 3 1 采用随机分配波长方式，但考虑 的网络拓扑是全连接的，而由于实际的网络通常不是全连接的，故此文给出的阻塞 概率可以作为一般网络中的阻塞概率下限。文献【1 4 】证明了在一般意义下m c r w a 问题是n p c 的，而在给定多播树的情况下，波长分配问题可以在线性时间内求解， 文中给出的基于动态规划的波长分配算法可以作为一个性能比较的依据，但其复杂 度过高，难以实用。 1 2 2w d m 光网络多播研究的主要问题 光网络中的多播技术正成为研究的热点。现有的研究大致如下： ( 1 ) 相对于硬件支持设备和相关控制协议，控制算法尤其是路由算法的研究受 到了更多的关注。同时，研究重点集中于波长路由网络中的光树、光林路由问题， 其目的均是寻找有效的光层多播路由方式以提高网络的吞吐量，均衡网络的负载等。 ( 2 ) 多播业务疏导网络的研究。光电混合网络中存在多种类型的交换节点，可 以是全光o x c 、具有高速接口的高端路由器、或者是光交换矩阵与电交换矩阵整合 一体的多粒度交换机等。在这种网络中支持多播业务连接，不再局限于波长粒度的 光树方式。多播业务疏导正是解决细粒度多播业务传输的有效方式。 ( 3 ) 为很好地解决支持可靠多播业务的连接，光层多播的生存性问题也是一个 研究热点。每个光层多播树上可能承载数量巨大的业务连接请求，一旦网络失效将 会导致众多的用户难以正常通信，所以进行光层抗毁是必要的。 5 重庆邮电大学硕士论文 第一章绪论 1 3w d m 光网络业务疏导问题 在w d m 光网络中，每个波长可以提供高达吉比特( 如o c 1 9 2 、0 ( 2 7 6 8 ，对应 带宽为1 0 g b s 、4 0 g b s ) 的传输容量。w d m 网络提供的速率或带宽是以波长为单位 的，是粗粒度的，而实际业务的请求带宽( 如o c 1 、o c 3 、o c 1 2 ，对应带宽为 5 1 。8 4 m b s 、1 5 5 5 2 m b s 、6 2 2 0 8 m b s ) 却远小于一个波长容量。因此，如果为每个这 样的低速业务请求分配一个单独的波长信道，网络资源利用率低且不经济；并且由 于w d m 网络中链路波长数目和节点光收发器数目的限制，不可能为每个低速的业 务连接请求建立专用的端到端波长通道。所以，为提供细粒度带宽需求、降低网络 建设和运营成本，有必要将多个低速业务请求有效的汇集，并通过一个波长通道传 输，即业务疏导( t r a f f i cg r o o m i n g ) 技术。 1 3 1 业务疏导概述 在光网络中，可以使用不同的复用技术实现业务疏导【1 5 】【1 6 1 ，主要包括空分复用 ( s d m ) 、频分复用( f d m ) 、时分复用( t o m ) 和动态统计复用技术等。在w d m 光网 络中，业务疏导技术是指利用t d m 技术有效的将低速业务流汇聚到高速的波长通 道中传输。其具体描述为【l5 】：在给定的网络配置下，包括光纤链路、节点光收发器 数目、每根光纤的波长数目以及波长容量，业务疏导就是为具有各种低速带宽粒度 的业务请求建立光路并合理安排这些业务，优化网络的性能。将低速业务流汇聚到 一个波长上传输时，可以通过一条光路到达网络目的节点，即单跳业务疏导 ( s i n g l e - h o pt r a f f i cg r o o m i n g ) ，或者通过多条光路到达目的节点，即多跳业务疏导 ( m u l t i - h o pt r a f f i cg r o o m i n g ) 。 低速业务连接请求可以是静态的，也可以是动态的。静态业务疏导是已知所有 的低速业务请求，并将这些低速业务请求构成业务需求矩阵，为此业务需求矩阵计 算路由并分配波长，以满足某些约束条件，并达到某些优化指标。这种计算可以是 离线( o f f - l i n e ) 处理的，即不需要实时的计算。静态业务疏导实质是一个特殊虚拓扑 设计问题【1 6 1 ，即为已知低速业务流建立合理的光路，形成最优的逻辑拓扑( 虚拓扑) ， 疏导各个低速业务流。它从全局优化的角度考虑如何为所有业务请求计算路由并分 配波长。其优化目标可以是：( 1 ) 最小化网络成本，即减少电终端设备a d m 或者o x c 光端口数目，或最小化光路数目；( 2 ) 在给定的网络资源下，最大化网络吞吐量。 动态业务疏导【1 7 1 9 】中，低速业务请求随机、顺序的到达网络，要求进行实时疏 导、路由与波长分配( g r w a ，g r o o m i n g ，r o u t i n ga n dw a v e l e n g t ha s s i g n m e n t ) 计算， 并且每个连接在网络中维持一段时间，业务传输完成后将被拆除。其目标是实时有 效的选择疏导路由，并合理分配有限的网络资源，降低业务阻塞概率。通常将该问 6 重庆邮电大学硕士论文 第一章绪论 题分解为三个子问题加以解决：虚拓扑设计子问题，确定物理拓扑上需要建立的一 组光路需求：光路路由与波长分配( r w a ，r o u t i n ga n dw a v e l e n g t ha s s i g n m e n t ) 子问 题，为光路需求寻找合适的路由并分配波长：低速业务流选路子问题，将低速业务 连接在虚拓扑上实现。本论文的重点是研究动态多播业务疏导的相关问题。 1 3 2w d m 多播业务疏导研究现状 由于光层多播技术的应用与发展，w d m 光网络中多播业务的路由和疏导问题 成为了研究热点。文献 2 0 1 概述了w d m 网状网中多播业务疏导的最初研究，文中 给出该问题的整数线性规划( i l v ) 描述，并针对几种典型的拓扑和业务模型进行了相 关的数值仿真。文献 2 1 】在给定物理拓扑和静态业务矩阵的情况下，提出了一种整 数线性规划( i l p ) 模型，优化网络支持业务疏导的s o n e ta d m 数目。 由于i l p 求解难以适应实际的网络规模，因此必须寻找简单高效的启发式算法。 文献【2 2 】提出了w d m 光网络中一种支持多播疏导的节点结构，包括e s a d 单元和 o s a d 单元，并讨论了三种静态多播业务疏导的启发式算法。其中，k - s p t 算法根 据任意低速多播业务请求都可能有不止一棵多播树来支持疏导这一情况，设定参数 k ，基于找到的第一棵多播树，按序号依次删除多播路由上的一条链路，并通过重路 由来获取一棵新的多播树，直至找到k 棵树( 由于资源限制，可能不足k 棵) 。然后 从这k 棵树中选择使用e s a d 单元最少的多播树疏导该低速业务( e - s a d 比o s a d 成 本昂贵的多) 。g r s 算法首先从所有低速业务请求中随机选取一个，并在某一个波 长平面上建立多播树，而对于其他的未疏导业务请求，考察其在该波长平面上已建 多播树是否足以容纳( 疏导) 新的低速业务。若该多播树疏导新业务的瓶颈链路( 波长 链路无足够的剩余带宽资源) 数目不大于2 时，重路由瓶颈链路以实现新低速业务的 疏导，依次类推直到不能容纳新业务时再另建多播树。g c o t 算法则采用了一种贪 婪方式，首先选择使用网络链路波长数最多的多播业务建立连接，并分配适合的波 长：然后反复地在未疏导的低速多播业务矩阵中，选取当中多播疏导路径与现有多 播树共享( 重叠) 物理链路数目最多的那个业务进行疏导，直至多播树剩余带宽不能 疏导新业务。对于未被成功疏导的多播业务请求，再重新建立新多播树，并进行下 一轮的循环。仿真结果表明，k - s p t 算法由于具有更大的疏导灵活性，因而具有较 低的业务疏导总代价；但与i l p 标准解相比，各个算法都还有很大的优化空间。 在w d m 光网络动态多播业务疏导方面，文献 2 3 】提出了一种扩充多播树大小 的策略，它可以减少实际多播业务疏导路由的物理跳数，但是不断扩充多播树的叶 节点，潜在地阻碍了许多中间节点的业务疏导。文献 2 4 1 考虑了w d m 网络中单多 播业务的混合疏导，给出了一种支持多播业务疏导的核心节点结构，并提出用超图 7 重庆邮电大学硕士论文第一章绪论 逻辑拓扑描述网络光树的逻辑连接，把问题分为多播路由计算、光树虚拓扑构造、 波长配置和业务疏导四个子问题。并讨论了动态的单跳、多跳和混合业务疏导方案， 但这些方案都没有考虑网络节点光收发器数目的限制。文献【2 5 】提出一种f r e e l o a d g r a p h 的分层图模型，描述当前网络链路的波长使用情况，并预先计算使用某个波 长链路疏导低速业务产生的网络最小空闲容量链路。所提算法的目的是最大化链路 的最小空闲容量，通过合理分配波长带宽，避免链路瓶颈，寻找最优多播路由树。 但该算法仅以波长资源作为仿真指标，并没有考虑实际网络的多种约束( 如波长连续 性，节点收发器数目) 。文献 2 6 】 2 7 】分析了两种w d m 网络多播业务疏导节点结构， 并提出采用分层图的方法来进行多播业务疏导，这种分层图的方法类似于单播动态 业务疏导使用的分层图，但是在多播业务环境下，由于节点具有分光能力，所以每 个波长平面的节点都需要拆分成多个节点，使得此方法的计算复杂度很高。 1 4w d m 光网络生存性问题 网络生存性【2 9 1 是指当网络设备发生故障时，网络维持某种可容忍服务水平的能 力。在大容量的w d m 光网络中，一旦网络发生故障，将导致大量的业务传输失效， 造成巨大的经济损失，因此，光网络生存性问题成为人们日益关注的研究热点 2 9 1 3 0 l 。 在网络的各种生存性技术中，光层生存性技术具有响应快速、灵活的特点，能有效 提高网络的服务质量，减少业务的丢失，因此光层生存性研究具有十分重要的意义。 光层生存性技术可以分为保护( p 】r o t e c t i o n ) 和恢复限e 咖枷0 n ) 两大类【3 1 】【3 2 】。保护 技术是指事先为业务预留必要的保护资源，当故障发生时，业务可以通过保护资源 承载。恢复技术并不事先为业务预留保护资源，而是当故障发生后，再动态地寻找 网络中的可用资源承载受故障影响的业务。相比而言，保护技术具有较短的业务恢 复时间，但需要耗费较多的冗余资源；而恢复技术具有较好的资源利用率，但故障 恢复时间较长，而且不能提供完全可靠的保护。 在保护策略方面，根据保护资源如何使用可以分为专用保护( d e d i c a t e d p r o t e c t i o n ) 和共享保护( s h a r e dp r o t e c t i o n ) 。专用保护包括1 + 1 和1 ：1 两种方式。1 + 1 保护机制要求发送端始终处于桥接状态，接收端采取择优接收的方式，即“并发优 收机制 。1 + 1 保护机制是单端倒换的保护方式，因此它不需要信令的支持，只需要 接收端检测到信号质量的劣化就可以立即完成保护倒换。l ：l 保护需要在业务的发 送端和接收端之间建立工作路径和保护路径，但信号只通过工作路径传送。当接收 端发现信号质量劣化时，再将信号倒换到保护路径中传输。此时，需要信令过程实 现业务信号从工作路径到保护路径的切换。m ：n i ：m l ，n m ) 保护是一种共享保 护，它的n 条工作路径由m 条保护路径进行保护，且m 条保护路径与n 条工作路 8 重庆邮电大学硕士论文第一章绪论 径必须是同源同目的节点。另外，虽然没有规定共享同一条保护路径的所有工作路 径必须是资源无关的，但是如果希望在网络任意单故障下保证业务的1 0 0 恢复， 则共享同一条路径的所有工作路径必须资源无关。 在恢复策略方面，主要包括共享恢复与重路由恢复。共享恢复是一种通过预留 资源实现受损业务恢复的生存性技术，与保护机制相比，恢复机制不要求路径完成 交叉连接。因此，在共享恢复中，如果两条工作路径是资源无关的，则它们的恢复 路径可共享恢复资源。与共享保护方式相比，由于共享同一段恢复资源的多条工作 路径不必是同源同目的节点，共享恢复可提高资源利用率，从而实现受损业务1 0 0 的恢复，但共享恢复的时间较长。重路由恢复是指，当建立工作路径时，并不为业 务预留保护资源。当故障发生后，根据网络的当前状态，通过某种路由策略为受影 响业务实时计算恢复路由。与共享恢复相比，重路由技术的资源利用率更高，但它 无法保证受损业务的1 0 0 恢复。 w d m 光网络中，保护恢复的粒度可以是链路、通道或区段。基于链路的保护 恢复是指以链路为单位的保护恢复技术。当链路失效时，故障链路的两个端点之 间通过一定的保护恢复机制将故障链路上承载的所有业务切换到保护恢复路径上 进行传输，保护恢复路径可与工作路径上未受故障影响的部分路由共同组成端到端 的新路径，保证业务的正常传输。基于通道的保护_ 恢复是以一条端到端的通道路径 为单位的生存性技术，这种技术需要在发送端和接收端之间建立保护恢复路径，一 旦发生故障，受损业务的源目的节点完成端到端的故障恢复。基于区段的保护恢复 机制是一种介于链路保护恢复和通道保护恢复之间的生存性技术，它根据工作路 径的具体情况将其划分成多个区段，每个区段可以是一条或多条链路，甚至是一条 完整的路径，并以区段为单位进行失效业务恢复处理。 预留资源的保护和恢复策略一般都需要掌握全网的链路状态信息：而对于重路 由策略而言，恢复路由计算可以是基于全网状态信息的，也可以是基于局部网络状 态信息的。在基于全网状态信息的恢复机制中，恢复路由的计算节点可以是网络的 中央控制节点，也可以是受损业务的源目的节点，该计算节点掌握了全网的链路状 态信息。对于基于局部网络状态信息的恢复策略，通常是由业务的源目的节点或是 故障链路的端节点来启动恢复路由的计算，并且网络中的各节点只维护邻接链路的 状态信息。基于全网状态信息的故障恢复成功率较高，且资源利用率也较高。 9 重庆邮电大学硕士论文 第一章绪论 1 5 本文的主要工作及内容安排 本文主要研究了w d m 光网络中的动态多播业务疏导和抗毁问题，给出了基于 网络编码的动态多播业务疏导算法和基于网络编码的抗毁多播业务疏导算法。本文 内容安排如下： 第一章，绪论。介绍w d m 光网络的基本原理和主要特点，并引入w d m 光网 络的三个研究重点：w d m 光网络的多播传输问题、业务疏导问题以及生存性问题， 并简要介绍w d m 光网络在此三方面的研究状况。 第二章，网络编码及其应用。引入网络编码的相关概念，系统介绍了网络编码 的基本原理和优势；分析了光网络中基于网络编码的多播路由算法和l + n 保护算 法，指出了利用网络编码解决w d m 光网络中的多播传输问题时，能够减小网络资 源消耗、改善链路负载均衡、使网络具有抗毁特性。 第三章，基于网络编码的动态多播业务疏导算法研究。针对已有的w d m 光网 络多播业务疏导方案中，多播树的构建方式无法最大化网络吞吐量，也没有考虑负 载均衡的特性，本章结合网络编码均衡网络负载的优势，研究了一种具有多播分光、 业务疏导以及编解码功能的光交叉连接结构，并在此基础上给出了一种基于网络编 码的动态多播业务疏导算法。仿真分析表明，此算法能够很好的降低动态多播业务 请求的阻塞概率，并使链路资源得到充分的利用。 第四章，基于网络编码的抗