（通信与信息系统专业论文）wdm网状网中动态波带交换算法研究.pdf

中文摘要 摘要 波分复用技术( 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 ) f 1 2 够将光纤的巨大带 宽分割成大量的波长信道，是解决带宽资源紧张的主要技术之一。随着w d m 传 输技术的日趋成熟以及光纤资源的大面积铺设，光电交叉连接器的数目和尺寸( 端 口数) 持续增长，不但增加了交换节点的复杂度，而且大幅度地提高了节点的成本 以及相关的控制管理费用，阻碍了w d m 技术的进一步发展。尤其是，密集波分 复用技术的迅猛发展，极大地增加了光交叉连接器( o x c 。o p t i c a lc r o s s c o n n e c t s ) 的端口数目，从而加大了o x c 交换矩阵的复杂度和成本。在此背景下，波带交换 的概念应运而生。波带交换的思想是将许多的波长组成波带进行交换，每个波带 只占用一个端口，因此大大降低了多粒度光交叉连接器的端口数和交换复杂度。 如何有效地选路、分配波长是w d m 光网络的核心问题，即路由和波长分配( r w a ， r o u t i n ga n d w a v e l e n g t h a s s i g n m e n t ) f 口 题。本文研究w b s 网络中的动态r w a 算法。 动态业务下波带交换算法的主要目的是减少多粒度光交叉连接器( m g o x c ， m u l t i g r a n u l a ro p t i c a lc r o s s c o n n e c t s ) 占用的端口数，降低网络阻塞率，因此，合 理有效的波带组成算法和端口分配至关重要。在w b s 网络中，业务失衡容易将网 络中某些节点或光纤的资源耗尽，从而加大网络阻塞率，因此考虑业务平衡问题 的w b s 算法能够有效的提高网络性能。在第2 章中，我们基于m g o x c 节点结 构，提出一种动态平衡业务启发式算法。仿真结果显示，所提出的算法能够有效 地降低网络阻塞率，节省端口数。 在w b s 网络中，一个组件故障将会导致大量的光路失效，从而大量数据传输 中断，造成巨大经济损失。因此，w b s 网络的生存性极为重要。在第3 章中，我 们将平衡业务的思想延伸到w b s 保护模型中，提出一种有效的动态专用保护波带 交换算法，通过网络仿真比较了算法的阻塞率性能。 目前，w d m 波长路由网络面临着相关的技术难题，如光纤或光节点器件( 例 如参铒放大器或o x c ) 所带来的物理损耗，包括光信噪比、色散等等，严重影响了 光信号传输的质量。在第4 章中，我们分析了w b s 网络中的信号质量问题，提出 了一种信号质量限制下的波带交换算法。 关键词：波分复用；波带交换；光交叉连接器；波带保护；信号质量 英文摘要 d y n a m i cw a v e b a n ds w i t c h i n g i nw d mm e s hn e t w o r k s a b s t r a c t o p t i c a ln e t w o r k su s i n gw 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 m ) t e c h n o l o g y , w h i c hd i v i d e st h ee n o r m o u sf i b e rb a n d w i d t hi n t oal a r g en u m b e ro fw a v e l e n g t h s ，i sa k e ys o l u t i o nt ok e 印u pw i t ht h et r e m e n d o u sg r o w t h i nd a t at r a f f i cd e m a n d h o w e v e r , a s t h ew d mt r a n s m i s s i o nt e c h n o l o g ym a t u r e sa n df i b e rd e p l o y m e n tb e c o m e su b i q u i t o u s ， t h es i g n i f i c a n t l yl a r g ec o s ta n dc o m p l e x i t ya s s o c i a t e dw i t hm a n a g e m e n ta n dc o n t r o lo f t h e o p t i c a lc r o s s - c o n n e c t ( o x c ) i sb e c o m i n g an e wp r o b l e m ，a n dh i n d e r st h e d e v e l o p m e n to fw d mt e c h n o l o g ys e r i o u s l y i np a r t i c u l a r , t h er a p i da d v a n c ea n du s eo f d e n s ew d mt e c h n o l o g yh a sb r o u g h ta b o u tat r e m e n d o u si n c r e a s ei nt h es i z eo f p h o t o n i c ( b o t ho p t i c a la n de l e c t r o n i c 、c r o s s - c o n n e c t s 1 1 1 en u m b e ro fp o r t s i na g r o s s c o n n e c ti st h em o s ts i g n i f i c a n tc o n 仃i b u t o rt ot h ec r o s s c o n n e c ts i z e i nt h i s b a c k g r o u n d ，t h ec o n c e p to fw a v e b a n ds w i t c l l i n g ( w b s ) h a sb e e np r o p o s e dt or e d u c e t h ep o r t sr e q u i r e da n dc o m p l e x i t yo fm u l t i g r a n u l a ro p t i c a lc r o s s - c o n n e c t ( m g o x c ) n o d e s 1 1 把m a i ni d e ao fw b si st og r o u ps e v e r a lw a v e l e n g t h st o g e t h e ra sab a n da n d s w i s ht h eb a n du s i n gas i n # ep o r t s i n c er 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 ) i so n eo ft h ec o r ep r o b l e m si nw d mn e t w o r k s w em a i n l yf o c u so nd y n a m i cr w a p r o b l e mi nw b s n e t w o r k s a st h em a i nw o r ko f d y n a m i cw b si st od e a lw i t ht h el a r g et r a f f i ca n dt oa c h i e v ea t o l e r a b l eb l o c k i n gp r o b a b i l i t y , i ti sc r u c i a lt h a th o wt og r o u pw a v e l e n g t h si n t o a w a v e b a n da n dh o wt oa s s i g np o r t se f f i c i e n t l yw h i l ec o n s i d e r i n gt h ep o l i c yo fb a l a n c i n g t r a f f i ci nw b sn e t w o r k s l i t t l el i t e r a t u r eh a sc o n s i d e r e dt h ep r o b l e mo f b a l a n c i n gt r a f f i c i no n l i n ew b s n e t w o r k s ，w h i c hi sp o t e n t i a l l ya tt h eh i g hr i s ko fe x h a u s t i n gr e s o u r c e s o ns o m ef i b e r so rn o d e s ，c o n s e q u e n t l yi n c r e a s et h eb l o c k i n gp r o b a b i l i t y i nt h i sp a p e r , w ep r o p o s ead y n a m i cb a l a n c i n gt r a f f i cw b sa l g o r i t h mb a s e do nt h et h r e e 。l a y e r m g - o x c w ec o m p a r et h ep e r f o r m a n c eo f0 1 1 1 s c h e m ei nv a r i o u st r a f f i cs c e n a r i o sb y e x t e n s i v es i m u l a t i o n s o u rr e s u l t sd e m o n s t r a t eas i g n i f i c a n tr e d u c t i o ni nb l o c k i n g p r o b a b i l i t ya n dp o r ts a v e i naw b sn e t w o r k ，ac o m p o n e n tf a i l u r em a yc a u s et h ef a i l u r e so fs e v e r a l w a v e b a n d - p a t h sa n dl i g h t p a t h s ，a n dr e s u l ti nt h el o s so fl a r g ea m o u n t so fd a t aa n d r e v e n u e t h u s ，f a u l tm a n a g e m e n ti nw b sn e t w o r k si s o fp a r a m o u n ti m p o r t a n c e 英文摘要 h o w e v e r , s u r v i v a b l ew b s ( s w b s ) i sar e l a t i v e l yu n e x p l o r e dt o p i c ，o n l yg a i n i n g a t t e n t i o nr e c e n t l y w ee x t e n dt h ek e yi d e ao fb a l a n c i n gt r a f f i ct oap r o t e c t i o nm o d e la n d d e v e l o p a l le f f i c i e n td y n a m i cd e d i c a t e dw b s p r o t e c t i o na l g o r i t h mi ns e c t i o n3 h o w e v e r , i nt h ec u r r e n tp h a s e ，aw a v e l e n g t h - r o u t e dn e t w o r kh a st of a c et h e t e c h n i c a ld i f f i c u l t i e si no v e r c o m i n gt h ep h y s i c a li m p a i r m e n t si n t r o d u c e db yo p t i c a l f i b e r sa n do p t i c a lc o m p o n e n t ss u c ha se r b i u md o p e df i b e ra m p l i f i e r s ( e d f a ) a n d o p t i c a lc r o s s 。c o n n e c t s ( o x c ) p h y s i c a li m p a i r m e n t s ，e g ，p o w e rl o s s ，n o i s e s ，a n d d i s p e r s i o n s ，i m p o s ef u n d a m e n t a lc o n s t r a i n t so nt h eq u a l i t yo fs i g n a l si nw d mo p t i c a l n e t w o r k s i ns e c t i o n4 ，w ea n a l y z et h es i g n a lq u a l i t ym o d e li nw b sn e t w o r k s ，a n d p r o p o s ea ne f f e c t i v ed y n a m i cw b sa l g o r i t h mu n d e rs i g n a lq u a l i t yc o n s t r a i n t k e y w 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 x i n g ；w a v e b a n ds w i t c h i n g ；o p t i c a l c r o s s - c o n n e c t s ；w a v e b a n dp o t e c t i o n ；s i g n a lq u a l i t y 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博士硕士学位论文：业丛圆丛囝主动盔遮堂銮逸簋这盟峦：。除论文 中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文 中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公 开发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：触表w 口7 年；月”日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密日( 请在以上方框内打“”) 论文作者签名：豫爱导师签名：何朱牟 日期：7 年；月工口e l w d m 网状网中动态波带交换算法研究 第1 章绪论 1 1 w d m 光网络概述 1 1 1 w d m 光网络技术的原理及发展 信息化和网络时代的到来，无时无刻不在改变着我们的学习、生活、和工作， 我们的信息沟通和交流方式日新月异，人们对信息的依赖与需求一直呈增长趋势， 尤其是以因特网( i n t e r n e t ) 为代表的新技术革命正在深刻地改变传统的电信观 念和体系架构，其骨干网络上的业务量约1 2 个月就翻一番，增长速度比著名的摩 尔定律还要快，另外，像网络视频、多媒体、流媒体、网格计算以及网络游戏等 各种新业务的不断涌现，已经使铺设的光纤资源消耗殆尽，这对传统的骨干网络 s o n e t s d h ( s y n c h r o n o u so p t i c a ln e t w o r k s y n c h r o n o u sd i g i t a lh i e r a r c h y ) 技术提 出了巨大的挑战，必须寻找合适的技术解决这个问题【l - 2 】。 在采用s d h 系统挖掘光缆的潜力、采用光时分复用( o t d m ：o p t i c a lt i m e d i v i s i o nm u l t i p l e x i n g ) 技术增加单根光纤中s d h 的传输容量和采用( 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 ) 技术进行波分复用这三种技术中，w d m 技术得 到了充分的肯定和优先的发展。它在长途骨干网上已经取代了s d h 技术，成为大 容量传输系统的首选扩容方案【3 1 。 在光系统的发送端，w d m 系统将调制在不同波长的输入光信号载波通过一个 波分复用器( 合波器) 复用在一起，再经一根光纤传输到远端；在光系统接收端，利 用另一个波分复用器( 分波器) 将这些不同信号的光载波分离开，由不同的检测器将 各自的光信号转换成各自的电信号下载到本地，或者直接获取各自的光波长信号， 连接到其它波分复用器件上继续传输【4 】。 通常，将波长间隔小于等于8 n m 的w d m 系统称为密集波分复用( d w d m ) 系 统，波长间隔小于5 0 n m 的w d m 系统称为粗波分复用( c w d m ) 系统，而波长间隔 大于等于5 0 r i m 的w d m 系统称为宽波分复用( w w d m ) 系统。 由于不同波长的光载波信号可以看作相互独立( 不考虑光线非线性效应) ，因而 双向传输问题很容易解决，只需将两个方向的信号分别安排在不同波长传输即可。 图1 1 0 ) 显示了n 个双向传输的w d m 系统的结构示意图，又称单纤双向w d m 系 第1 章绪论 统。同样也可以将一个方向的传输集中在一根光纤，返回方向集中在另一根光纤， 从而实现双纤单向w d m 系统，如图1 1 ( b ) 所示【4 】o _ _ 丽藤羽生竺厅丽了卜一 ( b ) 双纤单向传输 图1 1w d m 传输系统 f i g 1 1w d m t r a n s m i s s i o ns y s t e m w d m 技术最早可以追溯到2 0 世纪8 0 年代美国a t & t 网中使用的两波长 ( 1 3 1 0 1 5 0 0 n m ) 系统，速率为2 1 7 g b i t s 。此后一直到2 0 世纪9 0 年代中期，w d m 技术发展的并不快，主要原因有：1 当时正值t d m 技术的迅猛发展阶段，t d m 技 术相对简单，可以从1 5 5 m b i t s 比较容易的升级到6 2 2 m b i t s ，系统成本较低。2 w d m 技术中的关键器件没有完全成熟，特别是光放大器的不成熟使得w d m 系统使用 时需要在中继点上进行光电光的转换，不仅复杂而且成本太高。3 当时的业务量增 长比较缓慢，带宽压力不大，通信网络中的主要业务量还是语音业务，原有的t d m 升级方式完全可以满足通信网络的需求。从9 0 年代中期开始，w d m 技术的发展 掀开了新的篇章：1 首先，掺铒放大器( e d f a ) 的出现及其商用化大大促进了w d m 技术的发展。利用e d f a 可以中继点同时放大多个波长的光信号，无需光电光转 换，大幅度降低了系统的成本和复杂度。2 随着t d m 单信道系统的不断扩容，其 速率已经发展到了1 0 g b i t s 。电处理的技术瓶颈日渐明显，增加了系统的难度和成 w d m 网状网中动态波带交换算法研究 本。3 通信网络的业务量飞速增长，使原有的通信网络无法满足带宽的需求，也大 大推动了w d m 技术发展。正是由于以上的各种原因，使得w d m 技术在2 0 世纪 9 0 年代中期开始得到了迅猛的发展，世界各国在其骨干网建设中迅速部署并实施 了w d m 的建设，主要工程集中在3 2 4 0 2 5 g b i g s 和3 2 4 0 1 0 g b i t s 水平层次， 其所建网络也多为一些点到点的初等光网络。这种光网络尽管有效地提高了带宽 利用率，但缺乏组网的灵活性，不能提供灵活的业务沟通能力，光层也缺乏高效 的保护机制，只是其中某些系统具有光复用段保护倒换功能( o m s p ) d s l 。 从9 0 年代后期开始，i n t e r a c t 网上各种形式的数据业务量的爆炸性增长，促使 光通信市场呈现产销两旺的势头。在巨大带宽的需求下，w d m 正迎合了人们挖掘 光纤带宽潜力的需要，各国相继投入和开发力量，在w d m 特别是d w d m ( d e n s e w d m ：密集波分复用) 技术上展开了一场角逐。传输容量和传输距离的世界纪录被 竞相打破。在1 9 9 6 年的o f c 会议上，日本f u j i t s u 报道了5 5 x 2 0 0 b i t s 传输1 5 0 k m 的试验，光纤的容量达到1 t b i t s 的历史纪录。同时日本n t t 也报道t ( 2 2 5 ) x 2 0 g b i t s 在非零色散位移光纤传输5 5 公里的试验。随后不久在e c o c 9 6 日本 n e c 公司报道了1 3 2 2 0 g b i t s 传输1 2 0 公里的新纪录，采用标准单模光纤和色散 补偿光纤，更趋近于实用化。n t t 的又报道了7 0 x 2 0 g b i t s 获得1 4 t b i t s 的6 0 0 公里传输，而后利用o t d m 把每个波长信道速率提高到1 6 x1 0 g b i t s = 1 6 0 0 b i t s ， 再将1 9 个波长信道的1 6 0 g b i f f s 用w d m 复用在一起得到总速率3 t b i t s 的 o t d m w d m 系统。l u c e n t 于1 9 9 7 年实现了6 4 5 g b i t s 的7 2 0 0 k m 传输；和 1 0 0 x1 0 g b i t s 使用真波光纤获得1 t b i t s 的4 0 0 k m 传输；并于1 9 9 9 年实现了单根 光纤上1 0 2 2 路复用的最高纪录。s i e m e n s 公司也于1 9 9 9 年底完成了3 2 t b i t s 传输 4 0 k m 的试验。n o r t e l 公司1 9 9 9 年4 季度实现了1 6 0 x1 0 g b i t s 的o p t e r a 系统。在 o f c 2 0 0 1 和其他的一些会议上，又有多家公司报道了大容量、多信道、超长距离 的d w d m 传输系统。如f u j i t s u 报道的2 1l 1 0 g b i t s 传输7 2 2 1 公里的超长距离 和n e c 的1 0 9 2 t b i t s 超大容量传输系统。在这个时期，国内的w d m 发展也非常 的快。d w d m 系统从1 9 9 8 年开始进入我国电信网络，从l u c e n t 的武汉至西安的 8 x 2 5 g b i t s ，到1 6 波的2 5 g b i t s 和3 2 波的1 0 g b i t s 都已经在我国的通信网络中 得到应用。从d w d m 系统的发展可以看出，在2 0 世纪9 0 年代后期到2 l 世纪伊 始，w d m 技术不断向着更多的波长，更高的单信道速度和更大的容量方向发展【引。 第1 章绪论 尽管d w d m 技术发展十分迅速，但是从网络建设来看，目前还只处于相对较 低的光网络发展初级阶段，点对点的w d m 系统还主要用以扩大传输容量，远期 的以光交换为基础的光分组技术目前也处于试验性探索阶段1 5 1 ，另外，由于服务提 供商们不会轻易放弃现有的基础设施，因此，如何实现网络的平滑过渡是当前亟 待解决的问题，另外由于光器件技术的局限性，目前光网络的覆盖范围还很小， 要扩大网络的覆盖范围，必须要通过光电转换来消除光信号在传输过程中的损伤 ( 色散、衰减、非线性效应等) ，进行网络维护、控制和管理，这必然增加了网络的 成本，目前所说的光网络只是由高性能的光电转换设备连接众多的全光透明子网 的集合，真正实现全光网络的互联，还需经历一个漫长的过程。 随着本世纪初互联网泡沫、光纤泡沫和3 g 泡沫的破灭，世界电信市场陷入了 短期的困境，w d m 技术也从竞相破纪录的鼓噪声中开始归于平静，1 1 u - t 等国际 化组织也决定重新来规划和研究目前的光网络技术及制定相应的标准化建议，并 且放弃对光网络的透明性限定，w d m 光网络的关键技术已经不再是容量的问题， 而是如何与现存网络进行有机的融合，w d m 光网络的研究热点也转向了关键元器 件、网络控制与管理、故障管理、组播技术、i po v e rw d m 、光分组交换和智能光 网络( a s o n ) 等新的方向，从近几年的o f c 会议上看来，以光交叉连接器( o x c ) 、 可重构的光分插复用器( r o a d m ) 为代表的光节点设备日趋成熟，智能的光网络在 向下一代网的演进中扮演着重要角色。智能光网络就是网络的管理和控制具有智 能化的特点，能够动态地、自动地完成端到端光路的建立，拆除和修改，并且当 网络出现故障时，能够根据网络拓扑信息、可用的资源信息、配置信息等动态地 分配最佳的恢复路由。另外，a s o n 具有大容量光交换能力，可实现网络拓扑结 构自动发现、点对点电路配置、带宽动态分配等，是未来光骨干网的发展方向。 尽管光网络的发展放慢了速度，但是电信的内在需求没有根本改变，移动短 信、对等通信( p 2 p ) 等业务迅速的崛起，i p 电视蓄势待发，世界网络带宽的年需求 增长率仍然高达5 0 1 0 0 ，随着新技术的不断涌现和成熟，在市场开放和竞争的 压力下，发展下一代光网络是历史的必然趋势【4 j 。 1 1 2 波长路由光网络 根据承载的业务不同，w d m 光网络可以分为静态业务网络和动态业务网络。 一4 一 w d m 网状网中动态波带交换算法研究 前者两个节点间的路由及分配的波长都是固定的，类似于永久式虚电路，而后者 则更像交换式虚电路，适合于承载突发业务的网络中，两点间的路由和波长需要 动态的选择和分配；从波长变换的角度，w d m 光网络又可以分为无波长变换和有 波长变换网络两种，在无波长变换网络，只有所选择的路由经过的所有节点都有 相同的空闲波长情况下，才能建立连接，这就是所谓的波长一致性条件( 或波长连 续限制) ，而有波长变换网络就没有这个限制；根据数据流在信源到信宿的传输过 程中有无光电转换过程的不同，w d m 光网络又可以分为单跳和多跳网络；按照物 理连接不同w d m 光网络可以分为环网、网状网、星型网和总线网等等：而从选 路方式上划分，可分为两种不同的形式：广播与选择网( b r o a d c a s ta n ds e l e c t n e t w o r k ) 和波长选路网( w r n ：w a v e l e n g t hr o u t e dn e t w o r k ) 。前者由于可扩展 性差，宽带利用率低不适合组建规模较大的网络。而后者与上述相反，波长路由 网络的节点是许多光交叉连接设备o x c ( o p t i c a lc r o s s c o n n e c t s ) 。o x c 与光纤链路 互相连接组成人意的拓扑结构，如图1 2 所示。每个终端用户都通过光链路连接到 o x c 上，终端用户与其相应o x c 的组合就是一个网络节点。每个网络节点都配 有可调谐发射器和接收器【3 】。如果网络节点间所有的物理连接都是由单根双工的光 纤构成的，则称为单纤网络，如果是由多根单工或双工的光纤构成，那么称之为 多纤网络，本文主要针对波长选路的单纤w d m 光网络进行研究，针对多光纤网 络可见文献 1 0 ，1 1 】。 在波长选路w d m 光网络中，信源和信宿节点是通过光路( l i g h t p a t h ) 来实现通 信的。所谓光路，就是网络节点之间的全光通信信道，在没有波长变换的网络中， 源、宿节点问只能建立一条光路，光路可以跨越多个光纤链路，但必需满足波长 连续限制，即在光路的所有链路( l i n k ) 上都要分配相同频率的波长，如图1 2 中由 a 到c 的通道和由b 到f 的通道。带有波长变换的网络中不必遵循这一限制，如 图1 2 中的d 到e 的通路【3 1 。 总之，波长路由网络的基本原理就是同一光链路上的不同光路必须具有不同 的波长，以免通道间的相互干扰。那么，如何有效地分配波长建立光路是波长路 由光网络中一个至关重要的问题，也引起了学者们的广泛关注。 第1 章绪论 1 - - - i 接入节点 o 波长路由节点 图1 2 波长选路的w d m 光传送网示意图 f i g 1 2w a v e l e n g t hr o u t e d n e t w o r k s 1 1 3 w d m 光网络中路由与波长分配( r w a ) f = - 题 w d m 光传送网中选路及波长分配( r w a ，r o u t i n g a n d w a v e l e n g t h a s s i g n m e n t ) 问题就是如何在给定一组节点间寻找合适的路由，并在这些路由上分配波长。一 般情况下，按照所支持的业务类型划分可以把r w a 问题分为两类：( 1 ) 静态光路建 立( s l e ：s t a t i c l i g h t p a t h e s t a b l i s h m e n t ) 问题，即整个网络的连接是事先已知的，在 尽可能少占用波长和光纤等网络资源的情况下，为已知的连接需求建立光路，通 常用基于流量整数线形规划o l p ) 法求解s l e 问题；( 2 ) 动态光路建立( d l e ：d y n a m i c l i g h t p a t he s t a b l i s h m e n t ) 问题，即光路请求随机到达和离开网络，需要即时为到达 的连接请求建立光路，并在通信结束后拆除光路，与s l e 问题相比，d l e 问题求 解比较复杂，通常采用启发式算法，本文主要讨论d l e 问题。 从总体上看，r w a 问题中的选路和波长分配是一个不可分割的问题。但是， 仅仅其中的波长分配问题就是一个n p c f 6 h a 题，要在合理的运算时间内解决大型 网络的r w a 问题常常是不可能的【7 j 。常用的解决方法是将r w a 问题强行拆成两 个独立的子问题，选路子问题和波长分配予问题，分别加以解决【8 一。 作为w d m 光传送网中的核心技术之一，r w a 问题的研究对网络资源的利用、 一6 一 w d m 网状网中动态波带交换算法研究 网络管理和控制都有至关重要的影响。静态路由与波长分配算法主要是为了解决 网络的规划设计问题，当网络中各节点之间的业务需求都已知的情况下，需要对 网络的资源进行优化配置来满足这些业务的需求。通常节点之间的业务需求可以 用业务需求矩阵来明确表示，网络资源优化的目标不尽相同，比如：当网络节点 之间的业务量确定时，每条光纤上需要多少波长才能满足这些业务量，或是光纤 上的波长数目已确定，需要多少条光纤才能满足需求。一般来说，当网络的规模 不是很大时，可以用整数线性规划( i l p ：i n t e g e rl i n e a rp r o g r a m m i n g ) 的方法来进行。 而当网络的规模较大时，整数线性规划的方法就不能使用，需要一定的启发式 ( h e u r i s t i c ) 算法来进行路由的选择和波长分配。通常路由的选择和波长的分配是拆 成两个独立的子问题来解决。关于静态路由与波长分配算法的详细讨论可以见文 献 1 2 1 5 】。本文重点讨论动态r w a 算法。 动态的业务量可以分为两种：业务需求递增型和业务需求动态型。业务需求 递增型是指节点之间的业务需求一直呈增长趋势，已建立的业务一直存在，这种 情况相当于网络的扩容。业务需求动态型是指节点之间的业务需求是呈动态的， 即光路既可以被建立也可以被拆除，这种相当于传统的电路交换网络中呼叫的建 立和拆除。这两种业务量需求的满足都需要动态的路由与波长分配算法。在现在 的网络业务量变化较大的情况下，动态路由与波长分配算法是需要仔细研究的。 图1 3 常见选路方法 f 追1 3r o u t i n gm e l h o d 常见的选路算法有：固定路由( f i x e dr o u t i n g ) 选择，备用路f l j ( f i x e d - a l t e m a t e r o u t i n g ) 选择和自适应( a d a p t i v es h o r t e s t - c o s tr o u t i n g ) 路由选择【3 l 。固定路由是最简 单的选路方法，网络总为一节点对提供固定不变的路由。选路是事先进行的，网 络拓扑结构已知后，按照标准最短路径算法( 比如d i j k s t r a 算法或b e l l m a n - f o r d 算 法) 为每个节点对分配固定的路由。网络运行中，节点对之间的通信总是建立在预 定好的路由上。如图1 3 所示节点0 到节点3 的工作路由总是为( o 1 2 3 ) ，这种方 第1 章绪论 法简单，却需要较多的波长资源。备用路由是指在节点之间选择多条最短路由， 在这些路由上依次进行波长分配算法来建立相应的光路，当节点收到连接请求时， 按路由表中的路由依次建立光路，如图1 3 所示，路由表中包含节点0 到节点3 之 间的两条路由( o 1 2 3 ) 和( 0 - 4 5 3 ) ，当第一条被占用或失效时，可以选择另一条建 立光路，与固定路由相比，备用路由显著降低了网络的阻塞率。自适应路由则是 一种节点之间的路由选择需要依据当时网络的状态来确定的选路方法，例如选择 空闲波长最多的路由作为节点之间的路由。 常见的波长分配算法有以下几种：随机波长分配法( r 锄d o m ) 【、f i m t f i t 法 ( f f ) e 1 7 , 1 8 、l e a s t u s e d 法( l u ) 、m o s t u s e d 法( m u ) 、m o s t - p r o d u c t 法( m p ) 、 l e a s t - l o a d e d 法( l l ) 、最大空闲容量算法( m a x s u m ) 1 9 1 、相对容量损失法( r c l ) 、 波长预留算法( r sv w a v e l e n g t hr e s e r v a t i o n ) t 1 6 】以及保护门限算法( t h r ：p r o t e c t i o n t h r e s h o l d ) 1 16 】等。 r a n d o m 算法：首先搜索所有波长集合，找出可用波长子集，再从中随机选取 波长分配给光路，这种算法相对简单，并且不必知道整个网络状态信息。 f f 算法：将所有波长编号，按照编号从小到大的顺序搜索可用波长，最先找 到的那个可用波长被分配给光路。与r a n d o m 相比，f f 计算量更小，分配速度也 较快。f f 也不必知道整个网络状态信息。 l u 算法：根据波长被占用的情况统计，优先选取被最少链路占用的波长。这 种算法的出发点是使得网络流量均分摊到各个波长上。但是在l u 算法下，较长的 光路往往被拆开，只有较短的光路容易保持波长一致性，算法相对复杂。 m u 算法：这种算法与l u 正好相反，优先选取被最多链路占用的波长。m u 算法的效率明显优于前面三种算法，它有助于将流量集中在少数波长上，这样可 以减少网络的波长需求。 m p 算法：这是一种适用于多光纤网络的算法。先给所有的波长编号，计算 兀岛，其中，q 指链路，上占用波长_ ，的光纤总数，万( p ) 指光路p 所跨越的所 l e z ( p ) 有链路。优先选择能使乘积项最小且编号较低的波长。当针对单纤网络时，m p 算 法就退缩为f f 算法。 l l 算法：首先计算。已警m i l l 归( 力( m 广q ) ，优先选择满足上式，且编号较小 一8 一 w d m 网状网中动态波带交换算法研究 的波长。l l 算法的出发点是将最空闲的波长优先分配给最繁忙的链路段，效果相 对较好。 m a x s u m 算法：先计算链路，上的光纤总数减去链路，上占用波长w 的光纤 总数，认为这个差值是波长w 在链路_ ，上的空闲容量，再计算各个链路上的空闲 容量，优先选择能使空闲总和最大的那个波长。 另外，r c l 算法类似于m a x s u m ，而更致力于将相对空闲容量最大化。r s v 和t h r 算法是为了改善网络中光路的公平性而设计的，r s v 算法是把链路上的部 分波长预留给多跳光路，从而降低了多跳光路的阻塞率，但会导致全网络的阻塞 率性能的下降；r s v 算法是在链路上设置某个门限值，当空闲波长数目大于这个 门限值时才可以分配给单跳光路。t h r 在改善公平性的同时可以使网络的性能不 至于下降太多。 总合考虑路由和波长分配算法问题是目前性能最佳的算法，已有大量文献提 出算法一次性解决r w a 问题，如利用辅助图等等口。捌1 。还有不少文献提出在服务 贡量( q u a l i t y o f s e r v i c e ：q o s ) 限制下的r w a 算法t 2 2 1 ，抗毁网络中的r w a 算法2 3 , 2 4 1 ， 最近几年，基于智能光网络平台的r w a 算法【2 5 】、支持m 业务的r w a 算法【2 6 1 又 引起学者们的广泛关注。总之，r w a 问题是波长路由光网络的核心问题，动态r w a 算法的优化目标就是提高网络资源利用率，减少阻塞率。 1 1 4 w d m 光网络中的其它问题 ( 一) w d m 光网络的生存性问题 网络生存性( n e t w o r ks u r v i v a b i l i t y ) 指网络在经受各种故障( 如链路失效) 后能 够维持可接受业务质量的能力，特别是在战争、失火、地震、光纤断裂、有害的 辐射以及其他人为的或自然的灾难中维持业务质量的能力，而不是通常的电磁干 扰或串音等影响1 3 1 。随着科学和技术的发展，现代社会对通信的依赖性越来越大， 假设一根承载1 6 0 x1 0 0 b i t s w d m 系统的光缆被切断将会引起大约1 6 0 0 万条等效 话路的丢失，其影响可见一斑。美国2 0 0 1 年9 月1 1 日的恐怖袭击事件导致2 0 万 条普通电话线，1 0 万条企事业电话线和3 6 0 万条数据电路受到破坏和中断，需要 花费1 4 亿美元来修复。据估计，通信中断l 小时使航空公司损失2 5 0 万美元，使 投资银行损失6 0 0 万美元。如果通信中断2 天则足以使银行倒闭。可见网络的生 一9 一 第1 章绪论 存性已经成为现代电信网至关紧要的设计考虑问题，也成为网络运营商之间的重 要竞争焦点。 目前在i p 、a t m 、s d h 层都有独自的保护恢复机制，并且可以直接在光纤上 运行，无须依赖其它层即可实施保护恢复功能，但是由于光层最接近光纤，因此 光层保护恢复可以提供整个光纤粒度的快速恢复，而且成本较低，可靠性高，是 解决光网络生存性不可或缺的技术，大量文献都对光层的生存性机制进行了研究 2 7 , 2 9 。在光层引入的生存性机制有两种：保护和恢复。通常保护机制可以分为两 种：共享保护( s h a r e d p r o t e c t i o n , s p ) 和专用保护( d e d i c a t e d - p r o t e c t i o n , d p ) 。而s p 又可以迸一步分为共享通路保护( s h a r e dp a t h - p r o t e c t i o n , s p p ) 和共享链路保护 ( s h a r e dl i n k p r o t e c t i o n , s l p ) 。s p p 是指为工作通路( p r i m a r yp a t h ) 提供一条端到端 的备用通路( b a c k u p p a t h ) ，但是在这条被用通路的各条链路上预留的备用波长可以 在多条其它的备用通路间共享，只要这些备用通路对应的工作通路不同时失效， 如图1 4 0 ) 所示，一条备用通路a g i - i - d 同时为两条工作通路a b c d 和a - e f - d 提供保护，由于这两条工作通路链路完全分离，因此不可能同时失效( 仅考虑但链 路失效网络) 。而s l p 指工作光路在建立时，同时在其经过的链路附近设置备用路 由并同时预留相应的备用波长用以保护相应的光链路，并且允许在多条备用通路 间共享预留的波长资源，只要这些备用通路不会同时启用。如果一条链路失效， 使用它的所有工作光路直接在此链路附近寻找备用路由和备用波长，绕过失效部 分而无需源目的节点参与，工作光路上未失效的部分则保持原状。如图1 4 ( b