（信号与信息处理专业论文）基于负载平衡的wdm网络rwa算法研究.pdf

重庆邮电大学硕士论文 摘要 摘要 近年来，宽带视频、多媒体等业务日益兴起，特别是i n t c m e t 业务的快速增长， 对骨干网的带宽提出了越来越高的要求。波分复用技术( w d m ) 以其传输容量大， 对高层协议和技术适应性强，以及易于扩展等优点成为光网络领域研究的焦点。 因此w d m 网络的关键技术以及波长分配和路由选择( r w a ) 技术的光传送网是下 一代高速骨干网最具有竞争力的候选者。随着网络技术的发展，各种新的业务相 继出现，这些业务在可靠性上有着不同的要求，如何区分业务可靠性是当前网络 研究的一个热点。又由于每一条链路都承载了大量的业务，任何链路或节点的失 效都将导致巨大的损失，因此在光网络中引入有效的生存性策略是必然的趋势。 保护和恢复机制是生存性策略的两种方法，而恢复机制在资源利用率上高于保护 方案。本文对如何有效解决r w a 问题并实现其优化目标及网络生存性问题进行了 研究。 在现有的r w a 算法中，启发式算法需要将r w a 问题拆分为选路与波长分配 两个子问题，复杂度比较大。为了能有效降低算法的复杂度，本文采用了整数线 性规划算法来解决r w a 问题。本文首先针对业务频率树( b f p - t h ) 方法路由机 制网络阻塞率较低问题，结合了负载平衡思想，改进了一种基于b f p - t r e 圮方法的 路由机制，按照网络中各链路使用波长数的统计方差最小作为优化目标，对业务 请求进行路由选择，建立整数线性规划模型。通过仿真验证这种路由方案在阻塞 概率方面要优于b f p - t r 圮路由机制，其负载更均衡，提高网络的资源利用率。 其次，本文在研究负载平衡的背景下，将使链路波长使用数均衡的负载平衡 思想引入到光网络恢复机制中，同时区分业务的可靠性，改进了已有的恢复算法。 在负载平衡的条件下保证优先级越高的业务对应的阻塞率较低作为优化目标，建 立整数线性规划模型，通过仿真实验验证了该算法的性能良好。该算法不仅降低 了全网阻塞率，而且保证了较高优先级的光路建立请求具有较低的阻塞率，更适 合现代光网络中不同业务请求对应不同服务等级的要求。 关键词：r w a ，负载平衡，路由机制，恢复 重庆邮电大学硕士论文 a b s t r a c t i nr e c e n ty e a r s ，b r o a d b a n dv i d e o ，m u l t i m e d i aa n dp a r t i c u l a r l yt h ei n t e r a c tb u s i n e s s h a v eb e e ni n c r e a s i n gr a p i d l y , w h i c hp r o p o s e sh i g h e rb a n d w i d t hr e q u i r e m e n t sa b o u tt h e b a c k b o n en e t w o r k 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 i n g ( w d ot e c h n o l o g yh a sm a n y a d v a n t a g e s ，s u c ha sl a r g et r a n s m i s s i o nc a p a c i t y , s t r o n ga d a p t a b i l i t yo fh i g h - l e v e l p r o t o c o l sa n dt e c h n o l o g y , e a s ye x p a n d i n ga n ds oo n , s ot h a ti tb e c o m e st h ef o c u so f r e s e a r c hi nt h eo p t i c a ln e t w o r k sf i e l d t h e r e f o r e ，t h eo p t i c a lt r a n s p o r tn e t w o r kc o n t a i n s w d m t e c h n o l o g ya n dw a v e l e n g t ha s s i g n m e n ta n dr o u t i n gf r w a ) t e c h n o l o g yt h a tw i l l b et h em o s tc o m p e t i t i v ec a n d i d a t eo ft h en e x t - g e n e r a t i o nh i g h - s p e e db a c k b o n en e t w o r k w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g y , v a r i o u sn e ws e r v i c e sa r eo n ea f t e ra n o t h e r , w h i c hh a v ed i f f e r e n tr e q u i r e m e n t sf o rr e l i a b i l i t y h o wt od i s t i n g u i s hb u s i n e s sr e l i a b i l i t y i sah o ts p o to f t h ec u r r e n tn e t w o r kr e s e a r c h b e c a u s ee a c hl i n kc a r r i e sal o to f b u s i n e s s , t h ef a i l u r eo fa n yl i n ko rn o d ew i l ll e a dt oh u g el o s s e s ，s ot h ee f f e c t i v es u r v i v a ls t r a t e g y i si n e v i t a b l ei n t h eo p t i c a ln e t w o r k t h e r ea r et w om e t h o d s o fs u r v i v a ls t r a t e g y ： p r o t e c t i o na n dr e s t o r a t i o nm e c h a n i s m s c o m p a r e dw i t l lp r o t e c t i o ns c h e m e , r e c o v e r y m e c h a n i s mh a sah i g h e rr e s o u r c eu t i l i z a t i o nr a t e t h i sp a p e rf o c u s e so nh o wt o e f f e c t i v e l ys o l v et h er w ap r o b l e mt oa c h i e v ei t so p t i m i z a t i o ng o a la n dn e t w o r k s u r v i v a b i l i t y i nt h ee x i s t i n gr w aa l g o r i t h m s ，h e u r i s t i ca l g o r i t h mn e e d st os p h tr w a p r o b l e m i n t ot w os u b - p r o b l e m sa sm 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 , w h o s ec o m p l e x i t yi s r e l a t i v e l yl a r g e i no r d e rt oe f f e c t i v e l yr e d u c ea l g o r i t h mc o m p l e x i t y , t h ei n t e g e rl i n e a r p r o g r a m m i n ga l g o r i t h mi su s e dt os o l v et h er w ap r o b l e m t h i sp a p e rf i r s tc o n s i d e r s t h eb f p 1 r o u t i n gm e c h a n i s mw i t hl o w e rn e t w o r kb l o c k i n gp r o b a b i l i t y , w h i c h c o m b i n e sw i t hl o a db a l a n c i n gi d e a st oi m p r o v er o u t i n gm e c h a n i s m sb a s e d0 1 1b u s i n e s s f r e q u e n c yt r e e ( b f p - t r e e ) m e t h o d , a c c o r d i n gt om a k e t h es t a t i s t i c a lv a r i a n c eo f t h el i n k w a v e l e n g t h si n t h en e t w o r kl e a s ti st ot h eo p t i m i z a t i o no b j e c t i v e s ，a n dc o n d u c tt h e r o u t i n gf o rb u s i n e s sr e q u e s ta n de s t a b l i s ht h ei n t e g e rl i n e a rp r o g r a m m i n gm o d e l s i m u l a t i o nr e s u l t ss h o wt h a tt h er o u t i n gs c h e m ei ss u p e r i o rt ot h eb f p - t r e er o u t i n g m e c h a n i s mi nt h eb l o c k i n gp r o b a b i l i t y , w h o s el o a di sm o r eb a l a n c e da n di m p r o v e s n e t w o r kr e s o u r c eu t i l i z a t i o nr a t e s e c o n d l y , i nt h ec o n t e x to fl o a db a l a n c i n g , t h i sp a p e ri n t r o d u c e st h ei d e o l o g yt h a t 重庆邮电大学硕士论文a b s u a c t l i n kw a v e l e n g t h sb a l a n c ei n t ot h er e c o v e r ym e c h a n i s mi n o p t i c a ln e t w o r k s ，a n d d i s t i n g u i s h e s b u s i n e s sr e l i a b i l i t y , w h i c hi m p r o v e st h ee x i s t i n g a l g o r i t h m o nt h e c o n d i t i o no fl o a db a l a n c e ，t h i sp a p e rt a k e sh i g h e rb u s i n e s sp r i o r i t ya n dl o w e rb l o c k i n g p r o b a b i l i t y a st h e o p t i m i z a t i o no b j e c t i v e s ，a n de s t a b l i s h e sa n i n t e g e r l i n e a r p r o g r a m m i n gm o d a l s i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tt h ea l g o r i t h mp e r f o r m a n c ei s g o o d n o to n l yd o e s t h ea l g o r i t h mr e d u c et h eb l o c k i n gp r o b a b i l i t yo ft h ew h o l e n e t w o r k , b u ta l s ob 1 1 s u r e sah i g h - p r i o r i t yr e q u e s tf o rt h ee s t a b l i s h m e n to ft h eo p t i c a lp a t hw i t l la l o wb l o c k i n gr a t e , w h i c hi sm o r es u i t a b l ef o rr e q u i r e m e n t so fd i f f e r e n ts e r v i c er e q u e s t c o r r e s p o n d i n gt od i f f e r e n ts e r v i c el e v e li nm o d e mo p t i c a ln e t w o r k s k e y w o r d s ： r w a ，l o a d - b a l a n c i n g , r o u t i n ga l g o r i t h m , n e t w o r ks u r v i v a b i l i t y 重庆邮电大学硕士论文 第一章绪论 第一章绪论 随着网络技术的不断更新以及网络技术的推陈出新，光网络的迅速发展以及 宽带视频、多媒体等业务的日益兴起，对w d m 网络提出了更高标准的要求。由 于光学技术的逐渐成熟，涌现出大量的功能完善的各种光通信器件和设备，未来 i n t e r n e t 骨干支撑的w d m 光网络技术受到越来越多的关注。w d m 技术解决了光 网络传输的各种难题，w 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 i n gw d m ) 技术最初 应用于点到点的传输系统，随着光器件技术工艺以及网络技术的不断进步发展为 w d m 网络【1 1 。w d m 即波分复用方式，是光纤通信中的一种传输技术，实现了超 高速率的光通信，一根光纤可以同时传输多个不同波长的光载波的特点，把波长 范围划分成若干个波长，而每个波段当作一个独立的通道用来传输一种预定波长 的光信号。综上所述，光波分复用的实质是将光频分复用应用在光纤上，因为光 波采用的不是频率，而是波长来监测与控制。w d m 技术以其传输容量大，对高层 协议和技术适应性强，并且具有易于扩展等优点而备受青睐。w d m 网络可以提供 一个大容量、高生存性和灵活性的传输基础设施，具有诱人的前景郾】。自2 0 世纪 9 0 年代以来，w d m 网络技术一直是网络领域的研究热点，同时，随着下一代网 络的越来越高的要求，也促进了对w d m 网络技术的日益精进的需要，因此全球 范围内的各大运营商和通信设备商将w d m 网络技术的改进提高到一个战略高度， 国内外著名大学和科研机构也对w d m 网络的相关技术展开深入研究。因此，采 用波长分配和路由选择的w d m 光传送网被认为是下一代高速广域骨干网的最具 竞争力的候选者 4 1 。 1 1w d m 网络 1 1 1w d m 网络理论 光波分复用( w a v e l e n g t hd i v i s i o nm u l 邱l e x i n g ，w d m ) 的原理是：在一根光 纤上可以同时传输多个不同波长的光载波的功能，其技术手段是在光纤传输的时 候将波长在可能应用的波长范围内( 低损耗区) 划分若干个波段，以每个波段为 一个独立的通道，在各个独立的通道上传输一种预定波长的光信号。波分复用技 术的基本原理是在传输系统的发送端使用复用器将不同波长的光信号组合起来使 用复用器进行复用，并把复用后的信号耦合到光缆线路的一根光纤中进行传输， 在接收终端采用解复用器分离出不同波长的光信号，并在不同的终端送入恢复出 重庆邮电大学硕士论文第一章绪论 的信号，如图1 1 。光波分复用( w 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 i n g ) 是目 前提高光纤传送带宽的最有效的方法，它利用了一根光纤可以同时传输多个不同 波长的光载波的特点，把光纤可用的波长范围划分成若干个波段，每个波段用作 一个独立的信道，并在各个独立的信道上来传输一种特定波长的光信号。 、， ! 厂 厂 堑 丸l 。地，姬 黧竺厂 厂 兰 蹿 渣 旺 穗卜一 趣 蛾 耜 撕厂 厂 n 光纤 塑几厂 堕一 图1 1w d m 原理图 w d m 技术具有的主要特点【5 j ： 可以充分利用光纤的巨大带宽资源。w d m 技术可以充分利用单模光纤的 巨大带宽，达到了一劳永逸的目的。 w d m 系统多用于大容量长距离传输，以便多信道复用光放大器，这也可 以达到简化系统结构和设计的目的，直接减少大量的投资和维护费用。 w d m 技术在单模光纤中的原理是使n 个波长复用起来，并把复用后的信 号耦合到光缆中的一根光纤中进行传输，这样在大容量长途传输时可以节约大量 光纤，提高了光纤的利用率在单模光纤中传输。另外，对于早期光缆安装的芯数 不多，因此这些光缆用其他的技术改进需要做较大的改动，其改造的成本是很大 的花费，而w d m 技术的出现解决了这一难题，利用w d m 技术可以不必对原有 系统做较大的改动，可以很方便的进行扩容。 由于同一光纤中传输的信号波长彼此独立，因而特性完全不同的信号也可 以在同一光纤中传输，完成各种电信业务的综合和分离，包括数字信号和模拟信 号，以及p d h 信号和s d h 信号的综合与分离都可以靠这个特性来完成。 w d m 技术对数据格式是透明的，即w d m 技术与信号速率及电调制方式 无关。一个w d m 系统可以承载多种格式的“业务”信号，以及a t m 、i p 或者将来 有可能出现的信号。正是这种透明性，因此w d m 系统完成的是透明传输，对于“业 务”层信号来说，w d m 的每个波长就像“虚拟”的光纤一样。 在网络扩充和发展中，w d m 技术占据了重要的地位，w d m 是理想的扩 容手段，而宽带业务对容量的需求，也让w d m 技术成为引入宽带业务的方便手 段，增加一个附加波长即可引入任意想要的新业务和新容量【3 】。 网络的交换和恢复也可以利用w d m 技术进行选路来实现，从而可以实现 2 重庆邮电大学硕士论文第一章绪论 未来透明的，具有高度生存性的光网络。 w d m 系统的另外一个优点是通过w d m 技术可方便地增加波长信道，既 有利于实现网络的光交换和恢复，又有利于网络扩容升级，从而可进一步实现适 用未来需求的、透明的、有高度生存性的光网络。 综上所述，w d m 是光纤通信中的一种传输技术，它的原理就是利用了一根光 纤可以同时传输多个不同波长的光载波的特点，把光纤可能应用的波长范围划分 成若干个波段，每个波段用作一个独立的通道传输一种预定波长的光信号。 w d m 技术的一个重要特性是在各个波长信道上可以独立地进行路由、交换， 彼此之间互不影响。为了建造一个高效的w d m 网络，终端用户必须具备向多个 w d m 信道注入信号或从多个w d m 信道中抽出期望信号的能力。因此，工作范围 大、调节速度快的可调光收发器的设计和实现显得尤为重要。w d m 的优势在于 复用多个业务流到一根光纤上，允许灵活地扩展带宽，从而可以利用光纤的巨大 带宽资源达到了降低复用成本的目的，使一根光纤的传输容量比单波长传输增加 几倍至几十倍。由于在同一光纤中传输的各种不同的信号波长都彼此独立，因而 可以传输特性完全不同的信号，完成各种业务的综合与分离。因此，w d m 网络采 用波长分配和路由选择技术，使得w d m 光传送网被认为是下一代高速广域骨干 网的最具竞争力的候选者【4 】。 随着w d m 光网络的不断发展，各种各样的问题也有待迸一步解决，如设备 价格昂贵、标准化、不同用户间的波长分配、对用户鉴权、保密性、串扰一体化 网络管理机制和互操作等问题。研究或开发可用于w d m 时新技术和新器件具有 极其重要的意义，新技术或新器件可使整个系统的性能大大改善，有时甚至会产 生出不同于旧系统的全新的系统。所以国内外大量的科研单位和公司都投入了相 当大的力量来开发w d m 新技术，以掌握行业的制高点。 1 波长转换器 随着w d m 全光网技术的不断发展，波长变换器已逐渐成为一个极为重要的 器件而受到了广泛的关注，波长变换已成为w d m 网络中一项重要的基本技术。 众所周知，在传统w d m 网络中，由于受波长连续性的限制，在波长路由中，构 成某一光通道的各段链路必须使用同一波长，从而导致网络中出现由于波长竞争 而引起的阻塞。波长变换器的引入能很好地解决这一问题，只要各段链路具有空 闲波长，在波长变换器的作用下就能建立通信路由，从而提高了波长重复率，减 少了网络中所需的波长数，消除了由于波长竞争而造成的阻塞。另一方面，在采 3 重庆邮电大学硕士论文 第一章绪论 用波长转换技术的网络中，可以将网络的管理和控制更加方便，此时波长路由算 法可以分布进行，各段链路可以独立地进行波长分配，无须考虑整个网络，从而 使r w a 大大简化。这对目前正在不断发展中的自动交换光网络技术具有很重要的 意义【6 】。 在波长变换器的研究领域中，目前主要有以下3 个大的研究方向。 完全波长变换。在节点处，所有输入端的任意波长的光可以在输出端转换 成任意波长的光，此时网络在功能上等同于传统的电路交换网，完全不存在波长 连续性限制问题。在这方面，目前主要研究在网络具有完全波长变换能力时，各 种因素对波长变换增益产生的影响。 有限波长变换。由于波长变换技术的限制，波长变换器的波长变换范围不 能覆盖整个复用波长集。这个方向主要是针对波长变换原理的研究，即是设计基 于不同原理的波长变换器，如光电光波长变换、基于s o a 的交叉相位调制、基 于四波混频的波长变换等。 稀疏波长变换。单个波长变换器能实现完全波长变换，但由于费用的原因， 波长变换器总数有限，每个节点只能放置数量有限的波长变换器，即节点不一定 能实现完全的波长转换。这种情况的一个特例是，部分节点是完全波长变换节点， 而其余节点则是无波长变换能力的节点。 2 光开关 光开关在光网络中起到十分重要的作用，它不仅构成波分复用光网络中关键 设备的交换核心，本身也是光网络中的关键器件。随着光传送网技术的发展，新 型的光开关技术不断出现。同时，原有的光开关技术性能不断地改进。随着业务 需求的急剧增长，骨干网业务交换容量也急剧增长。因此，光开关的交换矩阵的 大小也要不断提高。同时由于m 业务的急剧增长，要求未来的光传送网能支持光 分组业务，未来的核心路由器能在光层交换。这样对光开关的交换速度提出更高 的要求。大容量、高速交换、透明、低损耗的光开关将在光网络发展中起到更为 重要的作用。其应用范围主要有下列几种： 保护倒换功能：光开关通常用于网络的故障恢复，当光纤断裂或其他传输 故障发生时，利用光开关实现信号迂回路由，从主路由切换到备用路由上，这种 保护通常只需要最简单的l x 2 光开关。 网络监视功能：使用简单的l x n 光开关可以将多纤连接起来，当需要监视 网络时，只需在远端监视点将多纤光开关连接到网络监视仪器上，通过光开关的 动作，可以实现网络在线监测。 光器件的测试：可以将多个待测光器件通过光纤连接，通过l x n 光开关， 通过监测光开关的每个通道信号来测试器件。 4 重庆邮电大学硕士论文第一章绪论 1 i 3w d m 传送网 w d m 光传送网主要有两种形式【7 ，8 9 】：一种是广播与选择网 ( b r o a d c a s t - a n d s e l e c t o p t i c a ln e t w o r k s ，b s o n s ) ，另一种是波长一路由网 ( w a v e l e n g t hr o u t e do p t i c a ln e t w o r k s ，w r o n s ) 。这两种形式的区别是b s o n s 只 适用于节点数较少并且对网络生存性的要求不是特别高的局域网或城域网。基于 光路交换的w r o n s 采用波长选路机制，主要用于广域骨干网中。在w r o n s 中， 网络节点为o x c o a d m ，这些网络节点是通过点到点的光纤链路可以连接构成任 意的拓扑结构。利用o x c 就能在接入节点对间建立端到端的光路( l i g h t p a t h ) 。 在w r o n s 中，它的优势在于光路上的中间节点可以不进行任何电域的存储转发 或者交换处理，从而可以大大提高网络的数据吞吐能力、简化网络管理和减少电 域的网络设备。另外，w r o n s 还有个特有的波长重用能力，它可以使它具有良好 的可扩展性。本文主要针对这种具有波长选路能力的w r o n s 进行研究。w d m 网 络【l o ，l l 】是光纤通信技术发展的下一个目标，w d m 技术的建立将在干线网的交叉节 点上引入光交叉连接设备( o x c ) ，光分叉复用设备( 创m ) 和光波长变换，从 而引入端到端之间的“虚波长”通路，实现用户端到端的全光信号连接。 图1 2 表示一个波长选路的w d m 光传送网的示意图。图中a 到h 为接入节 点，1 到l o 为波长路由节点( w a v e l e n g t h - r o u t e d n o d e s ，w r n s ) ，它可以是光交叉 连接器( o x c ) 或光分插复用设备( o a d m ) ，完成波长选路功能。接入节点及其 相应的波长路由节点统称为网络节点。图中表示接入节点对a - c 之间在波长九1 上 建立光路，而接入节点对b f ，h g 之间建立的光路分别使用波长尥和九1 。 口接入节点 。波长路由节点 图1 2 波长选路的w d m 光传送网示意图 在w d m 光网络中，网络节点被称为波长路由节点( w a v e l e n g t h r o u t e dn o d e s ， w e n s ) 或光交叉连接( o p t i c a lc r o s s c o n n t , o x c ) 。波长转换( w a v e l e n g t h c o n v e r s i o no rw a v e l e n g t ht r a n s l a t i o n ) 是将输入波长信号转换到不同的输出波长上， 要实现波长转换需要引入额外的代价，并且它的技术实现也比较复杂。无波长转 5 重庆邮电大学硕士论文第一章绪论 换能力的路由节点称为波长选择交叉连接器( w a v e l e n g t h - s e l e c t i v ec r o s s c o n n e c t , w s x c ) ，有波长转换能力的路由节点叫波长转换交叉连接器( w a v e l e n g t h i n t e r c h a n g i n gc r o s s - c o n n e c t , w r x o 。 图1 4 所示为一种w s x c 的原理图。由图可以看出任一输入光纤上的任一波 长信号可以经过解复用器( d c r a u l t i p l e x c r ) 解复用、相应波长的光空分交换器交换， 最后复用( m u l t i p l e x i n g ) 输出到任一输出光纤的同一波长上。利用w s x c 就能在不 同的端用户之间建立端到端的光路就是利用了w s x c 这一原理。而没有波长转换 能力的路由节点，光路必须在其路由经过的光纤链路上使用同一波长，如图1 2 中 b 到h 的光路采用尥，h 到g 和a 到c 采用九1 ，这一限制称为波长连续性限制 ( 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 ) 。波长连续性限制也是波长路由网络区别于传统 的电路交换( c i r c u i ts w i t c h c d ) 网络的特性之一。 波长连续性带来的限制使得波长资源的利用率下降，尤其是在动态业务下会 增加光路的阻塞率( b l o c k i n gp r o b a b i l i t y ) 。如图1 3 ( a ) 所示，当节点a 到b 在九1 上、 b 到c 在尥上已建有光路时，尽管a 到b 和b 到c 的链路上分别有空闲波长尥 和九l ，仍无法建立从a 到c 的光路。如果在节点b 中引入波长变换，将输入的尥 波长信号变换到输出光纤的波长九l 上，就能够克服波长连续性限制，建立a 到c 的光路。这种含有不同波长的光路被称为虚光路o r m u a lw a v e l e n g t hp a t h , v w p ) ， 而相应的遵守波长连续性限制的光路则被称为w p ( w a v e l e n g t hp a t h ) 1 2 , 1 3 , 1 4 。在 w s x c 的光空分交换器的输入或输出端口配置波长变换器，就可以得到具有波长 变换能力的w l x c 。如果路由节点都是w i x c ，并且都能实现任意输入波长到任意 输出波长的全范围波长变换( f u l l - r a n g ew a v e l e n g t hc o n v e r s i o n ) ，本文的研究内容 就专注于这种具有波长变换能力的光网络。 ( b ) 有波长变换 图1 3 波长连续性限制造成的波长冲突 6 重庆邮电大学硕士论文 第一章绪论 输入光纤 l 2 n 图1 4 波长选择光交叉连接器结构示意图 除o x c 外，目前已广泛使用的一种具有波长选路功能的w d m 设备是光分插 复用器( o p t i c a la d d d r o pm u l t i p l e x e r , o a d m ) 。o a d m 的作用是从光纤的众多波长 中解出任意一路，或者向光纤中加入新的波长，其结构如图1 5 所示。o a d m 为 w d m 光传送网提供了异步接入的功能，使得光网络设备可以提供与各种业务的直 接接口。例如，s d h ，a t m 、帧中继和口等各种业务可通过占用o a d m 提供的某 个波长接口直接进入w d m 光传送网进行传输。 图1 5o a d m 功能框图 光传送网是在光领域对客户信号提供传送、复用、选路、监控和生存性功能 的综合实体。h u tg 8 7 2 建议( 草案) 5 】已明确在光传送网加入光层( 叫i c a ll a y e r ) ， 按照建议，光层由光信道层、光复用段层和光传输段层组成，如表1 1 所示。在光 传送网的主要功能是为用户传送高比特数据信息。从功能角度，它可以分为电子 层、光层和物理媒介层。电子层包含了电路交换层和电子通道层。光层则包含了 光信道子层、光段层。其中，光段层要进一步细分为光复用段层和光传输段层。 光信道层( o c h ) 网络为透明地传递各种不同格式的客户层信号的光通路提供 7 重庆邮电大学硕士论文第一章绪论 端到端的联网功能。光通路层的主要传送实体有网络连接、链路连接、子网连接 和路径。因此具有如下功能：光通路连接的重组，以便实现灵活的网络选路； 光通路开销处理，以便确保光通路适配信息的完整性；光通路监控，以便实 现网络等级上的操作和管理功能，诸如连接指配、业务参数交换的质量以及网络 的生存性。光复用段层( o m s ) 网络为多波长光信号提供联网功能，主要传送实 体有网络连接、链路连接和路径。因此具有如下功能：光复用段开销处理，以 便确保多波长光复用段适配信息的完整性；光复用段监控功能，以便实现复用 段层上的操作和管理功能，如复用段生存性等。光传输段层( o t s ) 网络为光信号 在各种不同类型光传输媒质上提供传输功能，主要传送实体有网络连接、链路连 接、子网连接和路径。因此具有如下功能：光传输段开销处理，以便确保光传 输段适配信息的完整性；光传输段监控功能，以便实现传输段层上的操作和管 理功能，如传输段的生存性等。整个光传送网由最下面的物理媒体介质层所支持， 物理媒体介质层是光传输段的服务者，即为各种规定类型的光纠1 6 】。 表1 1 光传送网的分层结构示意图 电路层电路层虚通道 p d h 通道层s d h 通道层虚通道 电复用段层电复用段层( 没有) 光信道层o c h 光复用段层o m s 光传输段层o t s 物理层( 各种光纤，如g 6 5 2 ，g 6 5 3 ，g 6 5 5 ) 1 2w d m 网络中r w a 问题国内外研究现状 w d m 网中选路及波长分配( 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 ，r w a ) 问题 所研究的内容是给定一组节点间的全光连接请求：寻找从源节点到目的节点的 路由；在这些路由上分配波长。按照所支持的业务类型划分，r w a 问题可分为 静态r w a 和动态r w a 问题，本文重点研究静态r w a 问题。 从总体上看，r a w 问题中的路由和波长分配是一个不可分割的问题。但是， 仅仅其中的波长分配问题就是m c 【l 刀( n o n d e t e r m i n i s t i cp o l y n o m i a l c o m p l e t e ， n p c ，非确定型多项式完全) 的问题，要在合理的运算时间内解决大型网络的 r a w 问题常常是不可能的。常用的解决方法是将r w a 问题强行拆成两个独立的 子问题，路由子问题和波长分配子问题，分别加以解决。为了避免该问题的拆分， 8 重庆邮电大学硕士论文第一章绪论 本文重点论述分层图模型在静态r w a 问题中的应用。 在研究r w a 问题上，一般分为建立试验网和理论建模仿真两种。 1 试验网方法，一般用于比较成熟的网络。近年来，支持光网络的光通信高 技术的发展已成为国际和国内的研究重点。以美国、欧洲为代表的许多发达国家 和地区已经投入大量的资金，实行了一系列针对光网络的研究计划。国内外一般 通过搭建光网络试验网来研究光网络的特性，然后通过大量的实验数据来比较所 采用算法的优劣。特别是近年来，波长路由光网已成为研究的热点。欧洲已经在 其r a c e 计划中将多波长传送网列为研究目标。在后续的a c t s 计划中，又在欧 洲各地建立一系列实验性的w d m 波长路由光网络。美国在国防部高级研究计划 局的资助下，组建了多个研究团队，建立一系列光传送网，用于实验和验证各种 新技术。日本则是以大公司的投资建设为主，i t u - t 也在积极制定有关光传送网的 建议。我国在光网络的基础研究方面也加大了力度。国家“十五”规划中，“8 6 3 计 划在通信技术主题下设立了光纤通信分项目计划，1 9 9 9 年6 月，国家高技术研究 发展计划( 8 6 3 计划) 发布了信息技术领域主题重大研究项目中国高速信息示范网 研究开发项目。此外作为国家8 6 3 计划“十五”期间一个专项的高性能宽带信息网， 它采用核心网加边缘网的网络架构。在核心网使用电路交换的自动交换光网络， 支持比特传输，边缘网采用电路和分组混合的交换体制。该项目能实现端到端带 宽达到4 0 m b p s 的实用化、可管理、可运营的广域高性能宽带信息网的方法和途径 i s ，1 9 ，2 0 o 2 理论建模仿真方法，一般用于实验室仿真阶段。对于一个新型算法需要验 算其可行性，建模仿真具有速度快，代价小，可重复演算等优势。仿真内容可以 是一个大型网络，也可以是单个节点性能。即使要建立试验网进行研究，也必须 经过充分的仿真，以降低可能的投资。 1 3 本文的主要工作与内容安排 本文主要研究了w d m 光网络中的r w a 问题。通过对现有r w a 算法和整数 线性规划( i l p ) 的研究，提出了一种基于b f p - t r e e 方法的负载平衡路由机制，并将 业务优先级、恢复受损业务等问题考虑到基于负载平衡的r w a 算法中。本文内容 安排如下： 第一章通过对w d m 网络的介绍，认为w d m 技术必将是下一代高速广域骨 干网的最具竞争力的候选者。介绍了路由与波长分配问题及研究现状。 第二章总结r w a 的基本理论，包括静态r w a 算法和动态r w a 算法；之后 又对考虑约束的r w a 问题加以介绍，对每个约束的重点问题一一详细介绍，它们 9 重庆邮电大学硕士论文第一章绪论 是分别针对考虑负载平衡问题、网络生存性问题和优先级问题的相关r w a 算法作 出了一系列的综述。并且指明影响网络性能的因素主要是路由选择问题和分配波 长问题。为了突出下文的重点问题，本章给出常用的路由算法以及波长分配算法， 与基于考虑上述几个问题综合一起的算法性能通过m a t l a b 仿真予以比较。 第三章研究了一种基于b f p - t r e e 方法的负载平衡的r w a 算法，文章采用整 数线性规划法来描述这个问题。主要是对一种基于b f p t r e e 方法的的路由机制做 了一点改进，加入负载平衡这个思想。通过数学建模和仿真分析，对算法的性能 与原来的算法做了比较，讨论了算法的共同点与区别，并分析了原因。 第四章研究考虑基于恢复受损业务的w d m 网络中负载平衡的路由方法。对 是否考虑负载平衡、区分业务优先级等四种情况分别进行详细讨论，并建模分析。 最后对各种情况下的性能进行仿真分析，分析各自的原因。 1 0 重庆邮电大学硕士论文第二章w d m 网络中的础融理论 第二章w d m 网络中的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 ) 问题，简称r w a 问题。目前光网络的可用 资源( 波长、光纤等) 有限。因此，如何在有限资源网络中为业务选择合适的路 由和分配优化的波长将直接影响到网络的传输效率。路由和波长分配算法成为重 要的研究课题。 路由和波长分e f a w a ) 是w d m 光传送网中的重要问题，其主要任务是为业务 选择路由，即源节点到目的节点的可达路径，然后再为该路径分配波长，以建立 光路，传送该业务。根据网络支持的业务类型，r w a 算法可以划分为静态r w a 和 动态r w a 。对于静态r w a 文中简要介绍了常见的几种处理方法并分析了各自的优 缺点；对于动态r w a 主要介绍了一些在固定路由和备用路由策略下常用的波长分 配算法，同时简要评价了算法的优缺点。接着，文章还提出了几个在r w a 算法中 需要考虑的附加问题。 2 1w d m 网络中路由与波长分配问题 r w a 问题是波长路由光网络中需要求解的一类重要问题。该问题可以描述如 下：在特定的网络拓扑下，如何为到达的连接请求分配路由及如何为路由所经的 各链路分配波长，从而使得指定的性能指标达到最优。r w a 问题是网络设计中的 一个关键技术，其结果是优化网络的某些特性。路由和波长分配( r w a ) 是w d m 光 传送网中的重要问题，其主要任务是为业务选择路由，即源节点到目的节点的可 达路径，然后再为该路径分配波长，以建立光路，传送该业务。根据网络支持的 业务类型，r w a 算法可以划分为静态r w a 和动态r w a 。在研究r w a 问题的文 献中，通常将网络支持的业务分为两类t1 、静态业务r w a 问题：给定网络拓扑 和一组连接建立请求，需要为这些请求在拓扑上寻找路由并在其路由上分配波长， 以建立永久光路来传送业务。静态r w a 问题的优化目标为：建立光路所消耗的资 源最少( 所需波长数或光纤数最少等) ，或同等资源下使全网吞吐量最大；2 、动态 r w a 问题：光路请求随机达到和离开网络，相应的性能指标通常是全网阻塞率。 动态r w a 问题与静态r w a 问题的不同在于：动态r w a 问题中的业务是随机到 达的，服从泊松分布，并且业务传送完毕后建立的光路需要拆除，光路的保持时 间服从负指数分布；而静态r w a 问题中的业务是已知的，并且所建立的光路不需 要拆除。 重庆邮电大学硕士论文第二章w d m 网络中的r w a 理论 2 2 静态r w a 问题 静态r w a 是在尽可能少的使用网络的资源( 如波长或者光纤) 等情况下，为 已知的业务选择路由，并在路由上分配波长。它的优化目标是在为业务建立光路 时尽可能地节省波长和光纤资源，从而提高网络的吞吐量。对于r w a 问题，可以 将其分解成路由子问题和波长分配子问题来考虑，同时也可以用线性规划将路由 子问题和波长分配作为一个整体来解决。在静态情况下，网络的连接请求是已知 的。静态r w a 问题就是在给定的光纤和波长等网络资源上建立尽可能多的光通路， 所以静态r w a 问题又叫做静态光通路建立问题。对于静态r w a 问题，可以将其 分解成路由子问题和波长分配子问题来考虑，同时也可以用线性规划( l i n e a r p r o g r a m m i n