（通信与信息系统专业论文）wdm网中面向生存性的动态业务量疏导机制研究.pdf

重庆邮电大学硕士论文摘要 摘要 w d m 光网络中，波长的传输速率越来越高，此时网络提供的速率( 带宽) 是粗 粒度的。而在实际应用中，很多业务的请求速率远远低于一个波长的最高传输速率， 显然，为每个业务提供一个专用波长，资源利用率低且不经济。并且由于光纤中波 长数、网络节点中光收发器数等的限制，不可能为每个业务建立端到端的独立光路 连接。因此，需要研究网状w d m 光网络中如何有效实现业务量疏导的问题。由于 每个波长传输容量可以高达吉比特秒，光网络中承载了大量业务，任何网络故障( 如 链路断裂、节点故障) 会导致巨大损失。因此，需要在w d m 光网络中引入有效的 生存性机制，研究业务疏导网中的生存性问题有着重大意义。 但是目前大多数关于业务量疏导算法的研究没有考虑网络故障。针对w d m 网 络生存性及业务量疏导问题，第三章给出一种基于故障感知的动态业务量疏导算法 0 3 f s a ) ，该算法首先在圈发现算法基础之上建立层次型网络，然后用最高节点度启 发式算法选取簇头，最后基于业务带宽裁剪虚拓扑得到实际光路。仿真表明节点的 数据包丢失率降低，网络性能得到改善。该算法可与基于探测圈覆盖的网络故障监 测机制结合起来，在既考虑到动态业务量疏导的复杂性的同时，又考虑了网络突发 故障。 目前关于业务量疏导阻塞性能分析模型是在链路之间的负载相互独立的假设 基础上建立的，但因为它没有抓住链路负载相关性的本质，所以该模型不够准确。 在第四章，我们通过研究网格型w d m 网络的阻塞特性，给出了一个分析模型来计 算有业务量疏导能力的波分复用网络中业务请求的阻塞性能。该分析模型首先把求 解过程分解为三个阶段，然后对这些阶段分别求解，再对这些阶段进行适当地组合 就可以得到整个网络的解，然后我们利用g a r c h 模型进行链路负载相关性估计。 对于给定的网络拓扑和业务量模式，该分析模型抓住了链路负载和链路阻塞事件的 相关性，仿真结果表明：分析模型给出的计算结果曲线与仿真得到的阻塞性能曲线 较为接近，证明了模型的准确性和有效性。 关键字：波分复用网业务疏导生存性阻塞性能 重庆邮电大学硕士论文 摘要 a b s t r a c t i nw d m o p t i c a ln e t w o r k s ，e a c hw a v e l e n g t hc a l lb eo p e r a t e da tv e r yh i g hs p e e d ， r e s p e e t i v d y , a n dt h eb a n d w i d t hp r o v i d e di sc o a 礴屺g r a n u l a r i t y h o w e v e r , i no p e r a t i o n a l n 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 ec a p a c i t yo faw a v e l e n g t ha n dt h e r e q u i r e db a n d w i d t ho fl o w - r a t et r a t f i es t r e a m s t oa c c o m m o d a t es u c hk i n do fl o w - r a t e t r a f f i cs t r e a mw i t ho n el i g h t p a t hw i l ll e a dt oi n e f f e i e n tr e s o u r c eu t i l i z a t i o n a n di tm a y n o tp o s s i b l et oe s t a b l i s he n d - t o - e n dw a v e l e n g t hc h a n n e l sf o ra l lt h el o w - r a t ee o r m e e t i o n s d u et ot h el i m i t a t i o no f w a v e l e n g t h sp e rf i b e ra n dt r a n s c e i v e r sp e rn o d e s oi ti sn e c e s s a r y t oi n v e s t i g a t et h et r a t t i eg r o o m i n gp r o b l e mi nw d mn e t w o r k s t h es i g n i f i c a n c eo f t r a f f i c g r o m m i n gn e t w o r k si st h ei m p o r t a n c et h a ti th a ss u r v i v a b i l i t y s i n c ee a c hw a v e l e n g t hc h a n n e lh a st h e t r a n s m i s s i o nr a t eo v e rs e v e r a l g i g a b i t s p e r - s e c o n d ，t h ef a i l u r e so ff i b e rl i n k so rn o d e sm a yl e a dal o to fs e r v i c e st ob eb l o c k e d t h e r e f o r e , t h es u r v i v a b i l i t yh a se m e r g e da so n eo fi m p o r t a n ti s s u e si nt h ed e s i g no f w d m o p t i c a ln e t w o r k s b u tm o s to ft h ea l g o r i t h mr e l a t e dt ot r a f f i cg r o o m i n gh a sn o t f o c u s e d0 1 1an e t w o r kf a i l u r e c o n s i d e r i n gb o t ht h es u r v i v a b i l i t ya n dt r a 伍eg r o o m i n gi n w d mm e s hn e t w o r k s ，i nt h et h i r dc h a p t e r , w ep r e s e n tad y n a m i ct r a t t i eg r o o m i n g a l g o r i t h mb a s e d0 1 1f a u l ts e n s i n g ( b f s a ) ，w h i c hi sf o u n do nt h eb a s i so f t h ec y c l e - c o v e r a l g o r i t h ma n dg r o o mi nt h eh i e r a r c h i c a ln e t w o r k t h e nw es e l e c tt h ed u s t e r - h e a dn o d e w i t ht h em a xn o d ed e g r e eh e u r i s t i ca l g o r i t h m f i n a l l y ，w cc u tt h ep a t ho fv i x l x l a lt o p o l o g y a e e o r d i n gt ot h eb a n d w i d t ht do b t a i nt h ep h y s i c a lt i g h t v a t h t h es i m u l a t i o np r o v e dt h a tt h e a l g o r i t h mi s a l le f f e e t i v et r a f f i cg r o o m i n ga l g o r i t h m a tt h es 锄et i m e , w ec a nc o m b i n e t h en e t w o r kf a u l tm o n i t o r i n gm e e h a r t i s mw i t hi t t h u s ，w et a k ei n t oa c c o u n tb o t ht h e c o m p l e x i t yo ft h ed y n a m i ct r a f f i cg r o o m i n ga n d t h en e t w o r ks u d d e nf a i l u r e n o w , t h eb l o c k i n gp , e r f o r m a n e ea n a l y s i sm o d e lo ft r a f f i cg r o o m i n gi sp r e d i c a t e do n t h ea s s u m p t i o nt h a tt h el o a do fe a c hl i n ki si n d e p e n d e n t i nc h a p t e r4 , an o v e la n a l y t i c a l m o d e li sp r o p o s e dt oc a l c u l a t et h ec a l lb l o c k i n gp r o b a b i l i t yo fw d mm e s hn e t w o r k 、) l ，i m 麟c g r o o m i n gc a p a c i t i e s f i r s tt h ea n a l y s i sm o d e ld e c o m p o s e st h es o l v i n gp r o c e s so f t h ep r o b l e mi n t ot h r e ei n d i v i d u a l s u b s y s t e m s t h e nt h e s es u b s y s t e ma r ea n a l y z e d i s o l a t i o n ，a n dt h ei n d i v i d u a lr e s u l t sa l ea p p r o p r i a t e l yc o m b i n e dt oo b t a i n n e x tw eu s e t h eg a r c hm o d e lt oe s t i m a t et h ec o r r e l a t i o no ft h el i n kl o a d s f o rg i v i n gt h en e t w o r k t o p o l o g ya n dt r a 衔em a t r i x ，t h ea n a l y t i c a lm o d e lc a p t u r e st h ec o r r e l a t i o no fb o t hl i n k n 重庆邮电大学硕士论文摘要 l o a d sa n dl i n kb l o c k i n ge v e n t s s i m u l a t i o ns h o w st h a tt h ec l l l v et h a tt h em o d e la l e g i v e ni sd o s et ot h es i m a u l a t i o ng u r v e ，a n dt h er e s u l tp r o v et h ea c c u r a c ya n dv a l i d i t yo f t h em o d e l k e yw o r d s ：w a v e l e n g t hd i v i s i o nm u l t i p l e xn e t w o r k s ，t r a f f i cg r o o m i n g , s u r v i v a b i l i t y , n e t w o r kb l o c k i n gp e r f o r m a n c e m 重庆邮电大学硕士论文第一章绪论 1 1 引言 第一章绪论 i n t e r a c t 业务爆炸性增长和高性能w d m 光网络设备( 如光交叉连接器o x c 、分 插复用器o a d m 、分光器l i g h t - s p u t t e r 等) 不断涌现，使波分复用( w d m ) 被认为是下 一代骨干网络核心技术最有力的竞争者。w d m 技术允许在一根光纤中同时传输若 干路不同波长的光信号，每个波长的传输速率可高到吉比特每秒，以满足大量业务 对高带宽的需求。利用w d m 技术和波长路由选择构架光层( o p t i c a ll a y e r ) ，对高层( 如 p 层) 提供大容量且结构灵活可变的传输通道，将成为i n t e r n e t 骨干网的核心传输方 式。因此，w d m 光网络在未来的未来中提供了一个经济、大容量、高生存性和灵 活性的传输基础设施，具有诱人的前景。 1 2w 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 ) 是提高一根光纤传输容量的主 要技术，它类似于无线电系统中常用的频分复用技术。w d m 技术可以在一根光纤 的多个波长上同时传送数据，只要相邻波长信道的间隔距离足够远，不同波长信道 之间就不会相互干扰。目前。实验室中光纤上可复用的波长信道数已达到上千个， 单信道容量已开始从1 0 g b p s 向6 0 c b p s 发展，系统总传输容量大大增加。 w d m 技术不仅可以充分利用光纤中的带宽，而且其多波长特性还具有将光通 道进行直接联网的优势，促使波分复用系统由传统的点到点传输系统向波长路由光 网的方向发展，形成了多波长的波分复用光网络( w d mo p t i c 面n e t w o r k s ) ，通常 把传统的点到点的传输系统当作是第一代光网络，而把波长路由光网作为第二代光 网络，而现在正往智能光网络发尉。 第二代光网络在光域中引入了相当于电域的交换和路由功能，节点能把经过而 不是起止于该节点的业务在光域中进行交换，旁路掉本地的电处理，从而大大减轻 了节点上进行电处理的压力，消除了中间节点的电处理瓶颈 2 1 。在第二代光网络中 常用的光层设备有光分插复用器( o p t i c a la d d d r o pm u l t i p l e x , o a d m ) 和光交叉连 接器( o p t i c a lc r o s sc o n n e c t , o x c ) 。o a d m 能够提供上下或者旁路业务，o x c 能把 从一根光纤某一波长进来的业务交换到另一根光纤的同一波长，如果该波长空闲的 话中去。o x c 能够用来构建复杂的w d m 网络，如网状网。通过o a d m 或者o x c 重庆邮电大学硕士论文第一章绪论 构建的w d m 网络的一个共同特点是低速业务流可以经过多个节点仍在光域中传 输，无须经过电处理。o a d m 和o x c 能够在入纤和出纤之间进行波长交换的功能 也使得光网络的重构成为可能。 根据网络分层的概念我们可以把第二代光网络看成一个光层它为高层网络如 i po v e rw d m 网络中的口层提供服务一般来说光层能为高层提供三种类型的服务 即光通道( 1 i g h t p a t h ) 、虚电路c c m u a lc i r c u i t ) 和数据报( d a t a g r a m ) 服务。光通道是网 络中两个节点之间的一个连接，它由一系列的波长信道组成，如果节点上没有配置 波长转换器，光通道经过的每一光纤链接上都必须分配相同的波长由于一个波长信 道的传输速率非常高，其数量级一般为g b p s ，因此光层能够以光通道的形式一次 性为高层网络提供巨大的带宽。需要注意的是，低速业务流通过光通道进行传输时， 它始终保持在光域内，没有经过任何的电处理。高层网络可以向光网络申请建立或 拆除光通道，类似于电话网络中的电路交换。高层网络需要的带宽也可能小于一个 波长信道的容量，此时需要在时域上将多个虚电路复用到一个光通道上，根据复用 方式的不同，可以分为固定和统计复用两种。前者为每个虚电路指定固定大小的带 宽，后者把每个虚电路上的数据拆分成多个短分组，并把不同虚电路上目的地为同 一虚电路的分组进行复用和交换。s d h 、s o n e t 和电话网络都是固定复用的例子， i n t e m e t 和a t m 则是采用统计复用方式的例子光层能提供的另一种业务是数据报， 它在网络中传送分组或一段长度不定的数据包时，不需要建立和拆除连接的开销字 节，如光突发交换( o p f i c a lb u r s ts w i t c h , o b s ) 和光分组交换( o p t 跏p a c k e ts w i t c h , o p s ) 。 因此基于w d m 技术的波长路由光网不仅提供了大的传输容量，还具有以往通 信网和现行通信系统所不具有的优点【3 】( 1 ) 对传输码率数据格式及调制方式具有透 明性，可支持多种协议业务( 例如a t m ，i p 等) ；( 2 ) 具有好的可扩展性，允许网 络节点数目和业务量不断地增长；( 3 ) 网络具有可重构性，可根据通信业务量的需 求，动态地改变网络逻辑结构，网络资源利用率高；( 4 ) 由于光网是对整个波长信 道进行路由交换，大大节省了电子交换设备的费用，而且简化了网络的运行和管理； ( 5 ) 网络具有高的生存性，可以减少网络故障所带来的损失：( 6 ) 光网结构简单， 网络中许多光器件都是无源的，可靠性高，易维护。 1 3w d m 业务量疏导问题 1 3 1 疏导技术 文献 4 】有个很好例子说明了什么疏导：如果你想从你家乡a 到一个遥远的小 2 重庆邮电大学硕士论文第一章绪论 地方b 市，你可能没有从a 到b 的直飞航班。原因有两个：一是在所有地点建立直 飞航班将需要大量的飞机，二是这些航班中相当多几乎是没有乘客。因此将导致初 始投资和运营费用极其昂贵。当然，如果有直飞航班到达b ，但由于该航班机票已 售完，你也不可能直接到达目的地b 。然而你可以通过一次或者多次的转机到达b 。 这样有利于提高航班的利用率，同时降低费用。网络中的疏导技术也跟这类似，即 有效地将低速业务流“疏导 ( g r o o m ) 高容量的波长上去传输。“疏导 源于复用 ( m u l t i p l e x i n g ) 和捆绑( b u n d l i n g ) ，即将多个低速业务汇集到高容量的传输单元上传 输，是用来描述传输系统中有效利用容量的优化设计问题【5 1 。 光网络中不同的域可以使用不同复用技术实现疏导【6 刀，包括空分复用( s d m ) 、 频分复用( f d m ) 、时分复用( t d m ) 和动态统计复用技术。w d m 光网络中的业务量 疏导( t r a f f i cg r o o m i n g ) 技术【8 9 】是指利用t d m 技术有效地将低速业务流汇聚到高速 的波长通道中传输。给定网络配置，包括光纤链路、节点光收发器数目、每根光纤 的波长数目以及波长容量，业务量疏导就是为具有各种低速带宽粒度的业务请求， 建立光路并合理安排这些业务，优化网络的性能。将低速业务流汇聚到一个波长上 传输，低速业务流通过一条光路到达目的网络节点，即单跳业务量疏导( s i n g l e - h o p t 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 c g r o o m i n g ) 。 低速业务连接请求可以是静态的，也可以是动态的。静态业务量疏导是预先给 出所有低速业务连接需求，计算路由和分配波长。这种计算可以是离线( o f f - l i n e ) 的， 即不需实时计算。静态业务量疏导是一个特殊的虚拓扑设计问题【9 ，姗，即为已知的 低速业务量建立合理的光路，形成最优的逻辑拓扑( 虚拓扑) ，疏导各个业务连接。 它所考虑的是如何从全局优化的角度来为所有连接需求计算路由。 在动态业务量疏导中，低速业务连接请求随机、顺序到达网络，要求进行实时 疏导、路由与波长分配( g i d 0 m i n gr o u t i n ga n dw a v e l e n g t h a s s i g n m e n t ，c r w a ) 计算， 但是一个连接维持一段有限时间后又被拆除。动态业务量疏导目标一般都是有效地 选择疏导路由和合理分配网络资源，以使业务连接建立的阻塞率最低。 1 3 2 业务量疏导研究现状 近年来，由于网状结构能够提供快速和有效的容量配置，并且可以提供较好的 抗毁能力，现已成为长距离骨干网的主要组网方式。w d m 网状网中的业务量疏导 成为研究的热点。 文献 1 2 ，1 3 】研究了逻辑拓扑上的业务量疏导问题。文献 1 2 1 先提出了一个线 性规划模型解决网状网中的静态业务量疏导问题，接着提出一个启发式算法最小化 3 重庆邮电大学硕士论文第一章绪论 光收发器数目。文献 1 3 给出了几个不规则拓扑上的业务量疏导下界( 1 0 w e rb o u n d s ) ， 同时提出了基于贪婪式的迭代启发式算法( g r e e d y - b a s e di t e r a t e dh e u r i s t i c ) 。文献 1 4 】 提出了在w d m 网状网中支持业务量疏导的两种节点结构模型，并使用线性规划解 决静态业务量疏导问题，并提出两个以最大化网络吞吐量的启发式算法，通过与线 性规划方案所得结果进行比较，评估了启发式算法的性能。在文献 1 5 】中，作者提 出了一种通用图模型来解决异构w d m 网状网中的静态业务疏导问题；作者使用该 模型构造辅助图模型，采用最短路径算法，提出了i g a b a g 算法；针对静态业务量 疏导，还提出了几种业务选择方案，通过仿真研究了其性能。 上面简单介绍了w d m 网状网中在静态业务量疏导方面的研究，在动态业务量 疏导方面，也存在一些研究。文献 1 6 提出一种研究业务量疏导网络中为子波长 ( s u b - w a v e l e n g t h ) ) l k 务选路的方法学，同时在波长级疏导的网络中通过仿真比较三种 动态选路算法。在w d m 业务量疏导网络中，高带宽需求的连接比低带宽需求的连 接更容易被阻塞，文献 1 7 】研究业务量疏导网络中的容量公平性( c a p a c i t yf a i r n e s s ) 问题，提出了一种接纳控制( c 0 衄e c t i o na d m i s s i o nc o n t r o l ，c a c ) 以达各种带宽粒度连 接在连接上的公平性。文献 1 8 1 给出了可达图( r e a c h a b l eg r a p h ) 模型，提出了两种动 态路由计算算法，为了取得很好的性能( 很低的连接阻塞率) ，仿真表明在不同的网 络状态时应该使用不同的疏导策略和算法。在预先已知一定的业务量需求，文献 1 9 】 研究了使用整数规划和遗传算法( g e n e t i ca l g o r i t h m ) 在满足所有连接的基础上最小化 网络费用的规划设计问题。文献 2 0 】研究了如何设计多层网状网络，在满足各种业 务的带宽要求和保护要求的同时，最小化整个网络费用，提出了一个数学模型和启 发式算法。文献 2 1 1 研究了在异构w d m 网状网中动态地为具有各种带宽粒度的业 务建立连接的问题，通过扩展了文献 3 3 】中的通用图模型，进行有效的业务量疏导， 以达到不同的业务量工程( t r a f f i ce n g i n e e r i n g , t s ) 目标。为了减小网络中o x c 端口 费用，文献 2 2 】研究了具有不同交换粒度的o x c 的w d m 网络设计问题，提出了 将多个具有不同交换粒度的o x c 放于一个网络节点设备的思想，同时扩展t 1 5 】 中的模型，提出了一种业务量疏导算法，该算法可以自动决定采用网络节点中的某 种类型的o x c 。文献【2 3 】研究了业务疏导网络中的生存性问题，将路由和波长分配 分开考虑，基于固定备份路由( f t x e da l t e r n a t em u t i n g ) 提出了两种路由策略为低速业 务流建立共享通路保护。文献 2 4 】基于通用图模型【b j ，侧重于研究动态业务量疏导 中的路由计算和资源共享，提出了三种共享保护策略。 4 重庆邮电大学硕士论文 第一章绪论 1 4w d m 网络生存性问题 1 4 1 生存性技术 网络生存性是指网络经受各种故障，甚至灾难性大故障后仍然能够维持可接受 的业务质量的能力【2 5 】，它是网络完整性的一部分。 广义的生存性【2 6 】包括一下几个方面：故障监测( f a u l td e t e c t i o n ) 、故障定位( f a u l t l o c a t i o n ) 、故障通知( f a u l tn o t i f i c a t i o n ) 、故障恢复( f a u l tr e c o v e r y ) 。狭义的生存性分 为保护机$ ! j ( p r o t c c t i o ns c h e m e s ) 和恢复机$ ! | ( r c s t o r a t i o ns c h e m e s ) 。保护机制是指利用 节点之间预先分配的带宽资源对网络故障进行修复的机制，一般在工作路径建立的 同时建立保护路径。恢复机制是指不进行预先的带宽资源预留，当发生故障后，再 利用节点之间的可用资源动态地进行重路由来代替故障路由的机制。 1 4 2 光网络生存性研究现状 目前国内外有大量文献针对w d m 光网络中生存性问题的研究，它们大多是针 对静态或动态的单播业务连接的保护或恢复方法。 涉及最多的是w d m 光网络中单链路失效下的单播业务保护问题。单链路失效 是目前光网络中最常见的故障，它指在同一时间段内网络中只存在一条失效的光纤 链路，在修复这条失效链路前没有其他链路失效。文献 2 7 】使用整数线形规划o l p ) 对小型网状光网络进行单链路失效的保护设计，采用了共享通路和共享链路两种策 略。i l p 优化目标是使全网使用的光纤总数最小。仿真发现，当网络引入保护机制 后，使用波长转换器有助于减少全网所需的光纤链路，特别是使用共享链路保护策 略时效果更为明显。文献【2 8 】研究了两种优先级的波长分配保护算法，波长编号发 和分配限额发。文献【2 9 】对光网络单链路失效的多种保护措施进行了比较，分析资 源预留和保护切换时间的差别，描述了专用通路保护、共享通路保护和共享链路保 护三种保护方案，通过数据说明共享通路保护具有最少的资源预留量，专用通路保 护次之，共享链路保护最多。而保护切换时间方面，共享通路保护切换时间长于共 享链路保护切换时间，并且保护切换时间随着o x c 配置时间的不同而不同；专用通 路保护切换时间与o x c 配置时间无关。 在实际网络中，由于光纤链路共享了物理资源而存在一定的故障相关性，这种 故障相关性由共享风险链路组( s z l c ，s h a r e dr i s kl i n kg r o u p ) 来描述( 删。s r l g 指 具有共同失效风险的一组链路，它们共享相同的物理资源( 如光缆、路由器、管道 等) 。s r l g 可以通过物理链路的路由信息自动生成，也可以通过网络管理者人工 5 重庆邮电大学硕士论文第一章绪论 指定。每个s r l g 对应唯一的标识，路由选择时为光纤链路分配不同的s r l g 标识， 可以满足业务工作路由和保护路由在一定程度风险分离。文献 3 1 ，3 2 提出s r l g 分 离的低费用双路径选路算法，基本思想是在s u u r b a u e 算法p 副的“变换相继最短路 基础上，引入部分k 路由思想【蚓，并且放宽了“两条路径综合费用最佳这一要求， 启发式地逼近最佳解。文献 3 5 】针对单s r l g 失效问题和静态业务矩阵提出接近最 优解的重路由( r e r o u t i n g ) 方法和禁忌搜索( t a b us e a r c h ) 方法，两种方法克服了i l p 求解巨大时间消耗的缺点，启发式地求解。通过仿真发现，r e r o u t i n g 算法的时间消 耗比t a b us e a r c h 少，但t a b us e a r c h 更接近最优解。文献【3 6 】也研究了单播业务s r l g 保护问题，针对计算两条s r l g 分离路径中可能遇到的陷阱( t r a p ) l 商- j 题，提出了一种 共享子通路( 段) 保护算法。该算法根据相应的策略，将工作通路划分若干段，并为 每个段建立保护通路，从而避免陷阱。 随着网络规模扩大，网络结构更加复杂，各类失效风险可能性增大。一些文献 针对双链路失效情况展开研究。双链路失效是指在同一时间段内网络中存在两条失 效的光纤链路，这两条链路可能是同时失效的，也可能先后失效。文献 3 7 ，3 8 描述 了两种双链路失效下基于共享链路保护的方案，一种是为每条链路计算两条链路分 离的保护通路：另一种是为每条链路先计算一条链路分离的保护通路，再为该保护通 路上的各链路计算一条链路分离的保护通路。前者需要特殊信令来广播链路失效消 息到网络其它各节点，后者则不需要。文中采用了一种新颖的“压缩扩展图 算 法。文献 3 9 】研究共享保护方案，为每条业务在源宿节点之间计算一条工作通路和 两条链路分离的保护通路，并且满足链路分离的工作通路在其保护通路可以共享预 留的波长资源。文献 4 0 】提出一种基于通路的共享保护算法和一种基于链路的共享 保护算法。算法考虑了不同工作通路和保护通路之间的交叠关系，并通过i l p 模拟 、发现通路保护相比链路保护节省了大量资源。 由于光层多播技术和应用的发展，一些文献对w d m 光网络多播业务的保护恢 复进行了研究。多播业务保护最直观方式是冗余树( r e d u n d a n tt r e e ) ，即为每棵多播 业务请求构建两棵多播树，一棵为工作树，另一棵为保护树，它们都覆盖多播业务 的所有成员节点( 源点和所有目的节点) ，且不相互交叠。如果工作树上链路或节点 发生故障，业务可以切换到保护树上进行传输。文献 4 l 】提出构造链路分离和弧 ( a r c - d i s j o i n t e d ，单向链路) 分离树进行业务保护，给出i l p 描述，对一组给定多播 业务请求，寻求工作与保护路由的联合最优。该i l p 基于o e o 和全光两种节点结 构，可以扩展到分光稀疏配置网络。通过删除工作树上所有链路( 弧) 来确保保护树 与工作树分离，但是删除过程大大减小了保护树的可行域，因而业务阻塞概率很高。 文章用标准数学规划软件c p l e x 进行数值仿真，没有给出保护资源的配置方法。 文献【4 2 】讨论了w d m 网中寻求全局最优静态多播保护设计问题，i l p 描述的目标 6 重庆邮电大学硕士论文第一章绪论 是减少节点波长转换器的使用和路由总代价。 由于求解i l p 问题难以满足实际网络需求、扩展性差，因此，文献 4 3 】提出多 播业务专用保护的启发式算法。对于多播业务保护，只要在分配或预留资源时确保 多播业务的任意源和目的节点对间存在两条链路分离的路由，就可以保证播路由在 网络任意单链路失效下的业务可靠保护。 链路分离树保护的一个不足之处是，如果网络中与源节点或任一目的节点相连 的所有链路都被工作树占用，那么构建该多播业务的保护路由失败。文献 4 4 提出 一种改进算法m c a p e ，在构建工作树时先随机删去与源和各目地节点相连的一条 链路，以避免寻找保护路由时出现孤立节点。但该算法的随机删除具有盲目性，导 致算法性能的不确定性。文献1 4 5 研究了在所有叶节点间构造对偶保护树。当发生 网络节点或链路故障，不能从源节点接收业务的目的节点由对偶保护树上的相关链 路实施恢复。算法要求网络是b i c o n n c c t i o ng r a p h 结构，即任意两节点间均存在节点 分离的两条链路，并需要相应的机制判断由哪个目的节点启动业务保护切换过程。 如果多播成员节点都分布在一个环路上，则多播业务连接通过环形路由自愈功 能可以防止单链路失效。文献 4 4 提出环形路由的多播保护，但是没有对目的节点 的排列顺序进行阐述，并且连成一条环形通路相比自然的树状路由并不节省资源。 文献 4 6 】考察单多播业务共存的保护方法，给出一种按优先级计算源到所有目的的 环路。文献 4 7 】考虑多播业务不同目的端具有不同可靠性要求的保护设计问题，给 出i l p 描述，并与无保护和专用保护算法进行了比较，说明其降低代价和阻塞概率 的优势。 上述方案都是基于专用保护的，不同多播业务连接在w d m 网络中预留的保 护，资源是不能共享的。文献 4 8 】提出交又共享的多播保护方案，提出整型线性规 划模型，没有给出启发式算法。i l p 仿真表明交叉共享保护比弧分离或自共享保护 方法都要节约备用波长资源。 在w d m 光网络多播业务的恢复设计方面，文献 4 9 】阐述了优化备用资源的数 学描述，分析多播保护中链路波长数和节点分光能力的影响。提出光树重构、中断 光树重构、备用光树枝保护和固定光树枝保护四种网络链路失效下的业务恢复设计 思想，但是文章没有给出具体算法。文献【5 0 】将恢复方案分成两类。一类基于路护， 在网络链路失效时工作树被分成两棵子树，通过在网络中寻找一条通路将两棵子树 重新连通，并删除不必要的原工作树枝；另一类基于环的保护，包括单业务单环保 护和多个业务单环保护两种，要求该共享保护环覆盖所有多播业务的目的节点。仿 真表明基于路的恢复耗资源比环保护少。 7 重庆邮电大学硕士论文第一章绪论 1 5 本文的主要工作及内容安排 1 5 1 主要工作 本文的主要工作是围绕着以下几个问题展开的： 1 ) 层次型逻辑拓扑构建问题 层次型网络结构具有较强的可扩展性，本文第三章给出的业务量算法用h s t 圈覆盖算法将网络初步划分为不同的簇并用最高节点度启发式算法选取簇头，进 而完成对给定拓扑的网络分割。 2 ) 链路负载相关性问题 链路负载相关性预测是第四章需要解决的关键问题。网络中所承载的数据流数 量较多，且每个端到端数据流需要经过多个中间节点转发，相邻链路之间的负载 具有非常强的相关性，因此，准确地对链路之间的负载相关性进行估计是所建立 的分析模型是否准确的关键因素。 3 ) 业务疏导中的生存性问题 首先第三章给出一种基于故障感知的动态业务量疏导算法( b f s a ) ，在用圈算 法进行网络分割时，可以与故障检测机制结合起来。然后在第四章给出一个更准确 的通用业务量阻塞性能分析模型。可以根据计算得出的网络阻塞概率，推导网络所 能够承载的业务量的最大值，以根据需要选择合适的业务量疏导算法和网络生存性 方案，更好的提高疏导能力和生存性。 1 5 2 主要内容安排 本文内容安排如下： 第一章，介绍w d m 波分复用原理和w d m 传输网的发展，简单介绍业务量疏 导和网络生存性的概念，详细介绍了目前关于w d m 网络中关于业务量疏导和生存 性的的研究现状。 第二章，介绍并举例说明了疏导技术以及业务量疏导的基本概念，指出了业务 量疏导的两种分类方法，即按业务静态与否分为静态和动态，按疏导策略分为单跳 和多跳。并介绍了网络生存性的概念和分类，阐述了保护机制和恢复机制，指出了 业务量疏导需要注意的问题。 第三章，针对w d m 网络生存性及业务量疏导的要求，本章给出一种基于故障 感知的动态业务量疏导算法( b f s a ) ，该算法在圈发现算法基础之上建立层次型网 络以对业务量进行疏导，经仿真证明该算法是一种行之有效的业务疏导算法，同时 可与基于探测圈覆盖的网络故障监测机制结合起来，在既考虑到动态业务量疏导的 8 重庆邮电大学硕士论文 第一章绪论 复杂性的同时，又考虑了网络突发故障。 第四章，针对目前关于业务量疏导阻塞性能分析模型是基于链路之间的负载相 互独立的假设基础上的，本章给出了一个新的分析模型来准确有效地计算业务请求 的阻塞概率，该模型考虑了网络中链路负载的相关性。 第五章，总结全文，并指出下一步的工作计划，对未来进行了展望。 9 重庆邮电大学硕士论文 第二章w d m 光网络中的业务量疏导问题 第二章w d m 光网络中的业务量疏导问题 在w d m 光网络中，为了充分利用带宽，一个波长上传输的通信速率常较高， 例如o c - 4 8 ，o c 1 9 2 ，o c 7 6 8 ( 对应的速度为2 5 g b s 、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 ) 。显然，为每个低速业务提供一个专用 波长，资源利用率低且不经济。并且由于光纤中波长数目的限制、网络节点中光收 发器数目的限制( 一个光路的建立需要在其两个终点各使用一个光收发器) 等，不可 能为每个业务连接建立端到端的独立光路连接。因此为了提供细粒度的速率或带宽 需求，同时降低网络建设成本和运营成本，提高网络性能，需要为这些低速业务有 效地建立端到端的连接。疏导( g r o o m i n g ) 技术可以解决这个问题。 2 1 业务疏导问题 在w d m 光网络中，目前长途骨干网络一根光纤上可以传输的波长数目已经可 以达到几百个甚至更多，单个波长通道的容量和整个网络链路容量非常巨大。目前 大规模应用d w d m 骨干网络的单波长的传送容量基本上为1 0 g b p s ，而一些实验系 统的单波长信道的容量达到了4 0 g b p s ，s y c a m o r e 的1 6 t b p s 系统是4 0 g x4 0 路波 长复用，而a l c a t e l 报道的1 0 2 t b p s 系统是4 0 ( 3 x2 5 6 路波长复用，而n e c 报 道的1 0 9 t b p s 系统是4 0 g 2 7 3 路波长复用。如此巨大的带宽适应了信息传输和 i n t e m e t 业务飞速增长的需要。但是另一方面，巨大的带宽资源给整个网络中的电 层交换处理设备，如s d h s o n e t 分插复用设备a d m 、a t m 交换机、路由器 等等，带来了巨大的处理负担，形成了“电子瓶颈 ，对网络的性能带来不利的影 响，也是网络成本居高不下的一个重要原因。 而在城域网和接入网方面，尽管诸如i n t e m e t 服务供应商( i s p ) 之类的w d m 光 传送网客户对于带宽有着很大的要求，例如，可能要求一条甚至多条o c 1 2 o c - 4 8 的线路。但是，还有大量的用户( 例如有着大量通信量需求的企业或者居民小区) 每 一个网络连结请求只需要一个波长通道提供的带宽的一小部分，例如o c - 1 。但是这 样的连结请求的数量却很大。随着技术的进步和需求的扩大，城域网和接入网逐渐 成为发展的重点，这一类用户的业务需求也逐渐成为主流，光传送网必须能够灵活 1 0 重庆邮电大学硕士论文第二章w d m 光网络中的业务量疏导问题 的满足各种业务需求，因而也必须能够有效的满足这种业务需求。然而给每个这样 的用户提供一条专用的光通道既不经济，也不现实。尽管在目前的w d m 传输系统 中，可以提供的波长通道已经很多了，但是和用户的数目相比，仍然要小几个数量 级。两者之间的矛盾的关键在于数目小而容量大的波长信道中合理分配数目大而容 量小的业务请求的问题，本文研究的业务疏导问题就是考虑通过有效的优化方法使 用户低速数据流共享高速的波长通道，从而有效的利用网络资源，提高网络性能。 业务疏导是指有效的将低速数据流复用到高速波长通道。高速波长通道数据流 解复用成为低速数据流，以及低速数据流在不同高速波长通道上的交换【5 l 】。 在光网络中不同的域可以使用不同复用技术实现疏导 6 , 7 1 ： ( 1 ) 空分复用( s p a c e - d i v i s i o nm u l t i p l e x i n g ，s d m ) 技术：将物理空间分区以达到提 高传输系统的容量。例如，将多根光纤捆绑到一根光缆上，或者多个光缆作为一个 链路连接网络中相邻两节点。 ( 2 ) 频分复用( f r e q u e n c y - d i v i s i o nm u l t i p l e x i n g ，f d m ) 技术：将频谱分成不重叠的 一系列独立的通道。光网络中的波分复用w d m 或者密集波分复用d w d m 技术即 是采用了f d m 技术。 ( 3 ) 时分复用( t i m e - d i v i s i o nm u l t i p l e x i n g ，t o m ) 技术：在时域内将带宽分成固定 长度的时隙( s l o t ) 。使用t d m 技术，多路信号只要在时间上不重叠可以共享一个波 长。 ( 4 ) 动态统计复用技术：在i p m p l so v b rw d m 的