（无线电物理专业论文）wdm光网故障恢复算法的研究.pdf

兰 州 大 学 研 究 生 学 位 论 文 wd m光网故障恢复算法的研究 论文摘要 本文在分析波分复用光网生存性问 题的基础之上， 针对网络最大 的故障来源一 链路故障， 提出了 两种适用于波分复用光网 单链路故障 条件下的恢复算法， 将路由与波长分配问 题中常见的固 定备用路由- 首次命中策略进行了 修改并应用到了 故障恢复中， 称为固定备用链路 无关路由一 首次命中算法;此外还提出了一种较新颖的故障恢复算 法， 该算法采用动态路由一 波长再分配的策略， 可以保证失效连接的 恢复; 根据两种恢复算法的基本思路以及所采用的路由与波长分配策 略， 本文给出了 在恢复过程中算法的具体执行步骤以及恢复指令信号 在路由上的传输流程， 并通过实例做了更进一步的说明; 最后以恢复 效率和平均恢复时间为主要研究对象， 通过计算机模拟仿真， 详细分 析了网 络波长总数、 网络负载以 及网 络连通率对算法性能的影响。 研 究结果表明， 无论在何种网 络条件下， 采用动态路由一 波长再分配策 略的故障恢复算法始终具有高于采用固定备用路由一 首次命中策略 的故障恢复算法的恢复效率， 而平均恢复时间却正好相反; 一味地增 加网 络波长总数与网 络密集程度或者减轻网络负 载并不能提升算法 的性能， 而是应该根据具体情况选择与之相适应的故障恢复算法， 找 到网络资源与算法性能的平衡点， 以少的网络波长和重的网络负载在 稀疏的网络中 取得尽量高的恢复效率和尽量短的恢复时间。 关键词:波分复用光网，生存性， 链路故障，恢复算法，恢复效率， 恢复时间 兰 州 大 学 研 究 生 学 位 论 文 s t u d y a l g o r it h ms on i n f a i l u r e re s t o r a t i o n wd m o p t ic a l n e t w o r k s ab s t r a c t i n t h i s th e s i s , w a v e l e n g t h d i v i s i o n m u l t i p l e x i n g ( wd m) o p t i c a l n e t w o r k s s u r v i v a b i l i t y h a s b e e n s t u d i e d in d e t a i l s . t w o f a i l u r e r e s t o r a t i o n a l g o r i t h m s a g a i n s t s i n g l e l i n k f a i l u r e i n wd m o p t i c a l n e t w o r k s a r e d e v e l o p e d d u e t o t h e b i g g e s t f a i l u r e s o u r c e , l i n k f a i l u r e s . t h e c o m m o n f i x e d - a lt e rna t e - r o u t i n g - f i r s t - f i t s t r a t e g y i n r o u t in g a n d w a v e l e n g t h a s s i g n m e n t i s a p p l i e d t o f a il u r e r e s t o r a t i o n , n a m e d f i x e d - a lt e r n a t e - l , i n k - d i s j o i n t - r o u t i n g - f i r s t - f i t ( f a l d r f f ) a l g o r i t h m . a n d a n o v e l a l g o r i t h m t h a t u s e s d y n a m i c - r o u t i n g - w a v e l e n g t h - r e a s s i g n m e n t ( d r wr ) s tr a t e g y a n d c a n e n s u r e t h e r e s t o r a t i o n o f f a i l e d c o m m u n i c a t i o n s i s a l s o p r e s e n t e d . b a s e d o n t h e i d e as o f r e s t o r a t i o n a n d t h e r o u t i n g a n d w a v e l e n g t h as s i g n m e n t s t r a t e g y , t h e e x e c u t i v e r o u t i n e s a n d t h e t r a n s m i s s i o n fl o w o f t h e r e s t o r a t i o n in s t ru c t i o n s i g n a l p a c k e t s i n o p e r a t i n g t h e t w o a l g o r i t h m s a r e f u l l y d i s c u s s e d a n d i l l u s t r a t e d i n d e t a i l s b y a n e x a m p l e . d e t a i l e d a n a l y s i s b as e d o n s i m u l a t i o n s t o u n d e r s t a n d t h e r e l a t i o n s h i p s b e t w e e n t h e s m n o f w a v e l e n g t h s i n n e t w o r k , n e t w o r k l o a d , n e t w o r k c o n n e c t i v i t y a n d t h e p e r f o r m a n c e o f t h e p r o p o s e d a l g o r i t h m s , i n t e r m s o f r e s t o r a t i o n e f f i c i e n c y a n d a v e r a g e r e s t o r a t i o n t i m e , a r e p r e s e n t e d . t h e r e s u l t s i n d i c a t e t h a t t h e d r w r a l g o r it h m h a s a b e t t e r r e s t o r a t i o n e ff i c i e n c y t h a n t h e f a l d r f f a l g o r i t h m , w h i l e t h e l a tt e r p e r f o r m s b e tt e r i n a v e r a g e r e s t o r a t i o n t i m e t h a n t h e f o r m e r n o m a tt e r w h a t t h e c o n d i t i o n i s . t h e p e r f o r m a n c e o f t h e a l g o r i t h m s c a n n o t b e i m p r o v e d e it h e r b y i n c r e a s i n g t h e s u m o f w a v e l e n g t h s a n d t h e n e t w o r k d e n s i t y o r b y l i g h t e n i n g t h e n e t w o r k l o a d , b u t s h o u l d b e d e p e n d i n g o n t h e r i g h t c h o i c e o f i t s m a t c h i n g f a i l u r e r e s t o r a t i o n a l g o r i t h m i n s t e a d , w h ic h m e a n s w e m u s t t r a d e o ff p r o p e r l y b e t w e e n t h e n e t w o r k r e s o u r c e s a n d t h e a l g o r i t h m p e r f o r m a n c e s o t h a t w e c a n g e t m u c h b e tt e r r e s t o r a t i o n e f f i c i e n c y a n d m u c h s h o r t e r r e s t o r a t i o n t i m e 场 u t i l i z i n g f e w e r n e t w o r k w a v e l e n g t h s a n d h e a v i e r n e t w o r k l o a d i n s p a r s e n e t w o r k s . k e y w o r d s : w a v e l e n g t h d i v i s i o n m u l t i p l e x i n g o p t i c a l n e t w o r k s , s u r v i v a b i l it y , l i n k f a i lu r e , r e s t o r a t i o n a l g o r it h m , r e s t o r a t i o n e ff i c i e n c y , r e s t o r a t i o n t i m e 丫 7 3 1 7 6 2 原 创 性 声 明 本人郑重声明:本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人己经发表或未发表 的成果、数据、观点等，均己明确注明出处。除文中已 经注明引用 的内 容外， 不包含任何其他个人或集体己经发表或撰写过的科研成果。 对本文的研究成果做出重要贡献的个人和集体，均己在文中以明确方 式标明口 木声明的法律责任由本人承担。 论文作者签名:三 屯触 日 期: 0 0 1r . 14 , l o 关于学位论文使用授权的声明 本人在导师指导下所完成的论 文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门 或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅;本人授权竺州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论 文 作 者 签 名 : ; ,导 师 签 名 : - el 期: 朴 r . 伞2 0 兰 州 大 学 研 究 生 学 位 论 文 ，引言 网络时代的到来以及人们对信息与日俱增的需求使得建设高速大容量的宽 带综合业务通信网成为现代通信技术发展的必然趋势。光纤因其所具有的宽带 宽、信号失真与损耗小等优点 ， ， 正 迅速成为广域骨千通信网的标准传输媒质。 随 着光交换技术的发展以 及光交叉连接器 ( o x c )与光分插复用器 ( o a d m )的实 用化，光纤通信正从单纯的点到点传输逐步走向网络化，采用波分复用 ( w a v e l e n g t h d i v i s i o n m u l t i p l e x i n g , w d m ) 与波长路由( w a v e l e n g t h r o u t i n g ) 技术的光传送网 ( o p t i c a l t r a n s m i s s i o n n e t w o r k s )被认为是未来广域高速宽 带骨干通信网的首选对象l乙 。波分复用技术将每根光纤的巨大带宽分 割成多个 互不重叠的波长信道， 所有信道都可以 异步并行地传输各种不同 格式的数据l 3 ， , 这使得侮个信道都能够工作在当前电子处理数据的极限速率上，从而减弱光一 电、电一光转换 “ 电子瓶颈 ( e l e c t r o n i c b o t t l e n e c k ) ”效应的影响，并且 也使 得波分 复用光网具有了 传统电网 络所不具备的“ 透明 性 ( t r a 门 s p a r e n c y ) o 近年来， 波分复用光网中单信道传输速率已逐渐由比较常见的2 . 5 g b i t % s 或 i o g b i t / s 提高到4 0 g b i t / s ，而复用信道数日 也己由 几个增加到几百个， 2 0 0 1 年的o f c 会议上报道了 总容量为1 0 . 2 t b i t / s ， 传输距离为l o o k m 的 系统!x ) ， 其单 路传输速率达到 4 2 . 7 g b i t / s ，共复用 2 5 6路。并且随着大量宽带新业务和新应 用的产生， 以及用带宽换取服务质量的实施， 都要求 一代网络具有更高的传输 容量， 超大容量将成为未来光网络的基本特征。 监测结果表明， 光网络并不能做 到完全可靠，不会出 现故障(s , in 。 对于大容量网 络而言，一旦发生故障， 将导致 网 络性能快速下降 u 并造成巨大的经济损失和影响，据美国联邦通信委员会 ( f e d e r a l c o m m u n i c a t i o n s c o m m i s s i o n , f c c ) 报告， 平均 每 两天 就 有 一次 影响 3 0 0 0 0 客户的网络故障发生， 而故障恢复的平均时间是5 -1 0 小时，当传输容量 达t b i t / s 的单根光纤失效， 将有1 2 0 0 万对以上的电 话受到影响 ，2 d21 。 因 此对网 络 生存性 ( n e t w o r k s u r v i v a b i l i t y ) 进行深入研究不仅具有重要的实用价值，更 具有深远的理论意义， 对波分复用光网而言 ， 就是要求其应有完备的抗故障措施， 当故障出现时， 网络具有对通信进行重选路由和网络重建的能力， 即故障的恢复 能力 a 兰 州 大 学 研 究 生 学 位 论 文 日前， 研究波分复用光网生存性问题的文献一 般分为两类， 一类主要研究失 效保护 ” 而另一类则主要研究失效恢复 1a 7前者以 优化网 络资 源配置为目 标， 解决静态业务下工作通道与保护通道的路由与波长分配 ( r o u t i n g a n d w a v e 土 e n g t h a s s i g n m e n t , r w a ) 问 题，由 于保护通道的路由 和所用波长在网 络设 计时就已经计算好，因此也被称为主动 ( p r o a c t i v e )或保护方式;后者与前者 不同之处在于恢复通道的路由 和所用波长不是预先计算好的， 而是根据网络出现 故障时的资源使用情况，使用某种恢复算法实时寻找可用资源来建立恢复通道， 因此也被称为被动 ( r e a c t i v e )或恢复方式。 在有关光网络保护的 研究中， 文献 1 2 , 1 5 , 1 6 采用了 整数线性规划( i n t e g e r l i n e a r p r o g r a m m i n g , i l p ) 算法为业务通道实施预留保护，其中， 文献 1 2 研 究了波分复用格状光网单链路故障保护的各种方案， 以全网使用的波长总数( 包 括工 作通道使用的波长和为保护通道预留的波长) 最少为优化目 标， 给出了在静 态业务条件下，采用专用通道保护、共享通道保护和共享链路保护的工 l p 描述; 文献仁 1 5 将业务通道与保护通道相互结合，以获取最优的路由; 文献 1 6 则提出 了三种不同的儿p 算法模型， 它们分别以提高恢复效率、 减小预留保护容量以及 效率与容量的联合优化为目 标。 而在有关光网络恢复的研究中， 文献t 1 4 采用了 ) 一 播发送的恢复机制 17 来确定恢复路由; 文献 1 8 在选取路由的时候采取避开故 障链路的方式;文献 1 9 则研究了基于端到端的恢复策略。 尽管现在可找到的有关研究波分复用光网故障保护与 恢复的文献比较多， 但 大多数的研究工作却主要集中在解释保护的基本原则、 各种保护方案的分类与比 较、网络优化设计等方面，具体的保护恢复方案较少， 而且大都是从网络设计与 规划的角度研究网络生存性， 很少从运行维护角度考虑; 同时， 网络传输容量的 增加以及“ 透明性”的要求， 也使得在光层或者波长级别上对网络实施保护或恢 复操作受到越来越多的关注。 因此有必要研究故障条件下， 对网络实施恢复可采 用的有效的路由选择与波长分配算法。 本文在分析波分复用光网生存性问题的基础之上， 针对网络最大的故障来源 链路故障， 提出了两种适用于波分复用光网单链路故障条件下的恢复算法， 将路 由与波长分配问题中常见的固定备用路由一首次命中策略应用到了故障恢复中， 此外还提出了一种较新颖的故障恢复算法， 该算法采用动态路由一波长再分配的 兰 州 大 学 研 究 生 学 位 论 文 策略， 可以 保证失效连接的恢复; 根据两种恢复算法的基本思路以及所采用的路 由与波长 分配策略， 本文给出了在恢复过程中算法的具体执行步骤以及恢复指令 信号在路山上 的传输流程， 并通过实例做了更进一步的说明; 最后以 恢复效率和 平均恢复时间为主要研究对象， 通过计算机模拟仿真， 详细分析了网络波长总数、 网络负载以及网络连通率对算法性能的影响。 研究结果表明， 无论在何种网络条 件下， 采用动态路由一 波长再分配策略的故障恢复算法始终具有高于采用固定备 用路由一首次命中策略的故障恢复算法的恢复效率，而平均恢复时间却正好相 反; 一味地增加网络波长总数与网络密集程度或者减轻网络负载并不能提升算法 的性能， 而是应该根据具体情况选择与之相适应的故障恢复算法， 找到网络资源 与算法性能的平衡点， 以少的网络波长和重的网络负载在稀疏的网络中取得尽量 高的恢复效率和尽量短的恢复时间。 本文的研究结果对波分复用光网故障恢复算法的实际设计与故障网络的运 行维护具有 一 定的参考价值。 2 w d m 光网的保护与恢复技术 日前，波分复用 ( w d m ) 技术已经成为大容量高速传输的主 要手段，由于其 传输容量大， 任何故障都有可能造成严重的损失， 因而要求w d m 光网具有良 好的 网络生存性 ( n e t w o r k s u r v i v a b i l i t y ) 。网络被划分为不同的层面，各层通常提 供相对独立的生存技术， 一般有i p , s d h 和w d m 三种。 在各种生存性技术中， 源 于w d m 层的光层生存性技术因其具有响应快速、 灵活、 高效、 可靠和透明等特点， 能有效提高网络服务质量， 减少业务损失， 因此对光层生存性的研究具有重要意 义。 2 . 1 wd m光网简介 波分复用 ( w d m )技术将光纤的巨大带宽分割成许多具有不同波长的w d m信 道， 侮一个信道均独立地按其对应的波长进行路由选择， 所有信道可以同时以不 同的速率进行传输，而互不影响。图2 . i 就为一个波长路由w d m 光网的结构图， 网络一般由包含光交义连接器 ( o x c ) 和光分插复用器 ( o a d m )的波长 路由节点 以 及连接节点的光纤组成， 不同的波长信道复用在同一根光纤中传输， 而网络中 的每一光纤链路大多均由一 对单向的光纤构成。 网络中的每个连接请求均通过在 兰 州 大 学 研 究 生 学 位 论 文 源节点与目的节点之间建立一条光路 ( l i g h t p a t h )来实现，光路是指任意节点 对之间的 一 条全光通道， 可以经过一条或多条光纤链路。 在图2 . 1 所示的波长路 由w d m 光网中， a与b 为波长路由节点，1 -5 为接入节点， 一 共建立有三条光路 反 之 夕 图2 . 1 波长路由w d m 光网结构图 连接， 其中 接入节 点对1 - 5 与3 - 4 在波 长a , 上 建立光 路， 接 入节点 对2 - 4 则 在 波长 兄 2 上建立 光路。 2 . 2 网络生存性问题概述 网络的生存性 ( n e t w o r k s u r v i v a b i l i t y )是网络的一个重要指标，指网络 在经受各种故障后能够维持可接受业务质量的能力， 是网络完整性的一部分， 在 设计网 络尤其是骨干网络时需要认真考虑2 a 7网络生存性研究的主要目 的是使网 络具有自愈( s e l f - h e a l i n g ) 能力。 自 愈是指当网络发生故障时， 无需人为干预， 网络即 si 在较短的时间内从故障状态中自 动恢复所携带的业务， 使用户感觉不到 出现故障， 其基木思想就是使网络具备发现故障并找到替代路由的能力， 在较短 时间内重新建立通信。 实现网 络生存性的方法有保护和恢复两种 1z . 14 3 。 两者的主要区别在于适用的 网络拓扑、 业务的恢复速度以及保护容量的 确定性等因素。 保护是利用节点之间 预先分配的容量提供快速恢复， 适用于特定拓扑的技术， 如线形或环形拓扑。 保 护往往处于本地网元或远端网元的控制之下， 无需外部网管系统介入， 保护倒换 时i d 很短， 但备用资源无法在网络范围共享， 资源利用率低。 恢复是利用网络提 兰 州 大 学 研 究 生 学 位 论 文 供的剩余资源， 为故障造成的失效业务快速而准确地重新安排路由以 确保通信的 畅通， 其实质是在网络中寻找失效业务的替代路山， 恢复算法与网络选路算法相 同。 恢复通常可以利用节点之间可用的任何容量， 包括预留的专用空闲备用容量、 网络的专用容量乃至低优先级的额外容量， 因而可大大节省备用资源。 但恢复机 制通常采用集中控制方式， 需要外部网管介入，时间较慢， 恢复响应不确定， 业 务恢复时间可能长达数秒至分钟量级。 2 . 3 wd m光网光层的生存性问题 w d m 光网是一个支持多种业务和协议的综合传送平台， 1 p 和 s d h 往往只是作 为网络所承载的业务， 它们自身已经具有一定的生存性能力并且这种能力与光网 本身的特点没有关系，而对于其它信号，如模拟视频信号 等则不具有这种能力。 在网 络中引入光层将能为各种信号提供一个公共的生存平台， 因此在这里不讨论 i p 和s d h 的生存性问 题。 2 .3 . 1 w d m 光网的分层结构 电层 电路层 电通道层 电复用段层 光层 光信道层 光复用段层 光传输段层 物理层 图2 . 2光网分层结构 如图2 . 2 所示为 i t ll - t g . 8 7 2 所定义的 光网分层结构，与传统意义上 的电网络所不 同的是网络层次结构中新增添了光层。光层 紧邻物理层， 即传输媒质光纤， 将工 p 和s d h 等作为客户层信号，为其提供一个透明的公 共传送平台。层与层之间为客户/ 服务者 ( c l i e n t / s e r v e r )的关系， 每一层网络在为 相邻上一层网络提供传送服务的同时，又使 用下一层网络所提供的传送服务仁， ， 。光层又 被细分为 3 个层次: ( 1 )光信道层 ( o c h : o p t i c a l c h a n n e l l a y e r ) 该层为电复用段层的客户信息，如工 p , s d h 等选择路由和分配波长，为灵活 的网络选路安排光信道连接， 处理光信道开销， 提供光信道层的检测、 管理功能 以及光信道层的保护恢复功能。 ( 2 ) 光 复 用 段 层( o m s : o p t i c a l m u l t i p l e x i n g s e c t i o n l a y e r ) 兰 州 大 学 研 究 生 学 位 论 文 该层保证相邻两个波长复用传输设备间多波长复用光信号的完整传输， 为多 波长信号重新安排光复用段， 处理光复用段开销， 提供光复用段检测和管理等功 m r o ( 3 ) 光 传 输段 层( o t s : o p t i c a l t r a n s m i s s i o n s e c t i o n l a y e r ) 该 层为光复用段的信号在不同 类型的光传输媒质 ( 如g . 6 5 2 , g . 6 5 3 , g . 6 5 5 光纤等) 几 提供传输功能， 处理传输段开销， 提供对光放大器或中继器的检测和 控制功能。 2 .3 .2光层的保护与恢复技术 保护与恢复技术是最重要的两种网络生存性技术。 对光网而言， 保护就是为 光网所承载的业务提供预留的保护资源， 当网络中发生故障时， 受影响的业务将 转由预留的保护资源进行传送; 而恢复则与此相反， 它并不为业务预留保护资源， 而是通过一定的算法和优化准则， 依据网络在发生故障时刻的空闲资源为失效业 务重新选择一条合适的路由。 可见相对于保护技术而言， 恢复技术能够更合理地 利用网络的资源， 因为它是按照一定的算法利用故障条件下的网络状态计算出来 的。 与业务层或高层信号，如 1 p 和s d h 等的保护与恢复相比，光层保护与 恢复 技术有下列特点: . 采用波长保护， 保护与恢复速度快: 光层保护与恢复是对波长进行操作， 而不是时隙，从而使网络保护的总带宽得以 增大，提高了保护与恢复速度。 2 透明性:山于光网采用波长路由，因此对光层进行保护与恢复可以为各 : 通 道 无 关 专 用 保 护 共 享 保 护 : 链路无关专用保护共享保护 图2 . 3光层保护与恢复技术的分类方式 兰 州 大 学 研 究 生 学 位 论 文 种速率和传输格式的信号提供一个公共的生存平台， 而不管该信号是否具有内在 的恢复能力。 3 .简单，恢复成本低:光层恢复比高层恢复需要更少的协调性，不需要业 务层恢复所必须的数日 众多的电子器件，简化了 相应的通信、管理和控制系统， 降低了成本。 图2 . 3 以框图的形式表示了光层保护与恢复技术的具体分类方式，按其作用 对象的不同可分为:光信道 ( o c h )层和光复用段 ( o m s )层保护/ 恢复技术，或 者通道和链路保护/ 恢复技术，为说明这两种技术的实现思路，以图2 . 4 为例来 进行解释，图中( a ) 所示为未发生故障时的网络，节点a与d 建立有一连接，所 经过的路由为a -g -h -d o 通道保护/ 恢复技术是针对每个光通道的，当故障发 生时，光网为受影响的故障通道分配一条完整的，通常是通道无关的保护/ 恢复 ( a )故障前 ( b ) 通道保护/ a复 ( c )链路保护/ 恢复 图2 . 4通道与链路保护/ 恢复示意图 通道来恢复失效业务，如图 2 . 4 ( b ) 所 示，当链路g 一i i 发生故障， 通道保护 / 恢复将依据网络当前的状态， 选择节 点a与d 之间的一条最优的备用通道a - h - c -d 来替代原来的路由， 很明显 两者之间并没用公共链路: 链路保护/ 恢复技术是针对光复用段层的，当故 障发生时，光网为故障链路寻找一条 替代链路或路由来同时恢复故障链路 上的所有业务，如图 2 . 4 ( c 所示，仍 旧是链路 g -h发生故障，链路保护/ 恢复将使原本经过链路 g 一11 的 a 一g -i i -d 路由不再经过g -h ， 而是经过 链路g -h的备用路由g 一f -卜 h ， 路 由上的其它几段链路却并不需要重新 路由，从而形成新的路由a -g -f -e 一h一d. 兰 州 大 学 研 究 生 学 位 论 文 通道保护为钉条工作光路预先设置好了链路分离的保护路由， 并在保护路由 经过的链路上预留相应波长， 不会同时失效的工作光路的保护光路可以共享链路 上的预留波长。 链路保护则在工作光路经过的链路周围设置备用路由并同时预留 相应的备用波长， 当某条物理链路出现故障时使用它的所有工作光路只在故障链 路周围寻找备用路由和备用波长， 原先工作光路上的其他链路段都保持不变， 链 路上预留的备用波长可以被多条备用路由共享，只要这些备用路由不会同时启 动。可见通道和链路保护还可分为专用保护和共享保护两类。 由于不管采用哪种保护技术都需要预留资源， 因此如果在一 个网络中全部采 用保护将造成网络资源利用率过低， 即使采用共享保护也会如此， 因为保护上限 不能无限大， 而月 _ 总得预留一定的保护通道， 所以 一 个网络中除了采取适当的保 护措施外， 一般采用恢复技术来实施对业务的保护， 针对不同的故障原因选择不 同的恢复算法。 节点和链路 ( 多根单工或双工的光纤) 是光网的基本构成， 它们也是光网故障的两个主要来源， 而本文主要是针对链路故障进行讨论的 因此 ，因 为链路故障较节点故障更为常见， 况巳 节点故障往往会导致链路失效， 最终也司 以用处理链路故障的方法来对故障进行恢复。 2 . 4 wd 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中的 路由与 波长分配是一个不可分割的问题，但是仅仅其中的波长分配就是一个 n p 完全问 题22 1 ， 计算时间复杂度高， 而恢复算法针对的 业务恢复要求恢复时间尽量 短，以减少业务的丢失，所以恢复算法通常将r w a问题拆分为两个子问题: .路由子问题:为失效业务选择优化的路由; 2 ，波长分配子问题:为失效业务分配优化的波长。 在恢复算法中，这两个子问题也 被称为恢复路由 选择算法和恢复波长分配算法， 下面就对这两个算法做进一步的介绍。 兰 州 大 学 研 究 生 学 位 论 文 2 .4 . 1恢复路由 选择算法 恢复路由选择算法的日 的是为待恢复的业务寻找一 条替代路由， 对于恢复路 由的选取通常是基于最短路由进行的， 针对不同的故障原因可以选择不同的恢复 算法。 对于木文卞要讨论的链路故障而台， 恢复路由算法可基于两种备用路由策 略 + 7 : 1 .通道无关 ( p a t h - d i s j o i n t ) 策略 选择的恢复路由同原故障业务路由 没有公共链路。 基于通道无关的恢复策略 属于o c h 层， 恢复针对的是通过故障链路的每条通道， 其路由选择策略选取了同 原业务通道没有相关链路的路由， 因此， 它无需等待故障定位，当检测到故障时 可以立即启动恢复算法程序， 在避开原通道的物理拓扑 匕 寻找 一 条备用的光通 道， 并将故障业务切换到恢复通道上。 由于基于通道无关的恢复是针对 一每条受故 障影响的业务， 故障链路上的所有光通道均需要切换， 恢复动作涉及到多节点动 作。 基于通道无关的路由选取策略能选择当前网络的最优路由， 同时能较好地处 理该故障路由上的多故障情u l 2 . 链路无关 ( l i n k - d i s j o i n t ) 策略 选择的恢复路由同故障链路无关， 即在当前光网剩余资源中寻找故障链路两 个端节点间的一 条最短路由来替代故障链路。基于链路无关的策略属于o h t s 层， 是链路层的恢复，它只需要为故障链路寻找替代链路，而路由的其它部分不变， 计算时间的复杂度低。 但链路无关路由需要准确的故障定位信息、 富余的网络剩 余资源， 而巨 无法选取当前网络中的最优资源， 易导致网络中的资源分配效率不 高，处理业务路由上多故障时的效果也不好口 2 . 4 . 1恢复波长分配算法 j恢复业务的波长 选择可以 采用r w a问题中的波长 分配算法， 在选取恢复路由 之后， 再在恢复路由上选取最优的分配波长。 考虑多光纤情况， 假设每个光纤支 持w个 波长， 每个链路f 根光纤， l 代表网 络中 的 链路总 数， l ( p ) 代表 通道p 上 的 所有 链路集合， l ,. ( 1 , 幻代 表链路l 在 波长a 上的 剩余信道 数， 任意通道p 在波 长a 上 的 可 用 信 道 数p ( p , a ) = m i n l. u p ) l , ( 1 , a ) , 如 果l , ( 1 , a ) 一 p ( p , a ) ， 称 链 路 1 为 通道p 的 瓶颈链路; 厂为新到 达的 业务 请求对应的 路由， a ( p * ) 代表通 道厂 兰 州 大 学 研 究 生 学 位 论 文 上的可用波长集，g ( 厂) 代表与n * 有共享链路，且仍具 有可 用信道的通道的 集 合: d ( a , b ) 为指示函数，当a = b 时取值为1 , 否则取值为。 ;( i ( a ) 为单位阶跃 函数，当a 0 时取值为1 ，否则取值为0 .波长分配算法具体包括: 1 . 随 机 分配( r a n d o m w a v e l e n g t h a s s i g n m e n t : r ) + a 该算法的思路为，首先遍历所有波长，确定在选定路由上 的可用波长集合， 接着从可用波长集合中随机等概率地选取一波长。 随机分配算法不考虑当前的网 络资源占用情况， 所以时间复杂度低， 但其对网络性能的改善不明显。由于需要 遍历所有波长以 确定可 用波长集合， 其时间复杂度可简单地以。 ( w ) 表示，其中 w为光纤中的复用波长数。 2 首次 命中 ( f i r s t - f i t : f f ) r2 . 2 0 在命中算法中，所有的波长都被统一编号，既可以按波长的大小顺序编号， 也可以随机编号， 一般按波长的大小顺序编号， 接着选用可用波长集中编号最小 的波长来建立光路。 但同随机分配算法一样， 首次命中算法也不考虑当前的网络 状态。由于是按顺序检查波长集合， 将发现的第一个空闲波长分配给呼叫， 其时 间复杂度为o ( w ) 。 3 .最小使用 ( l e a s t - u s e d : l u ) 5 该算法根据网络的状态统计出各波长的使用情况， 并将波长按其使用率的高 低升序排列， 在选定路由上按序检查波长， 直到找到一 可用波长。由j 二 每次都是 选择使用率最低的可用波长，因此最小使用算法使得各波长的使用率趋于平均。 最小使用算法需要利用目前的网络资源的占用情况， 其时间复杂度要高于首次命 中与随机分配算法，为o ( w l f ) o 4 .最大使用 ( m o s t - u s e d : m u ) s 该算法与最小使用算法 一 样，也要根据网络的状态统计出波长的使用情况， 不过在选用波长 时是选择使用率最高的波长。 最大使用算法也需要利用全网的状 态信息，因此时间复杂度与最小使用算法一样，为o ( w l f ) e 5 .最小负载 ( l e a s t - l o a d : l l ) z9 ) 该算法是针对多光纤网设计的。 在最小负载算法中， 首先选定路由上负载最 重的链路，设为1 ，接着对所有空闲波长计算其在1 上的空闲信道数，从中选择 具有最大剩余信道数的波长。其优化目 标可以表示为: 兰 州 大 学 研 究 生 学 位 论 文 m a x m in ( m ,z . a (p ) t. l (p ) 一 d ) ( 2 . 1 ) 其中a ( p ) 代表通道p 上的可用波长 集合，l ( p ) 代表通道p上 所有链路的集合， 从 ; 为 波长a 在链路1 上已 被使用的 信道数，m， 代表链路1 上的光 纤数目 。 在时 间仁 ，需要确定路由上负载最重链路和遍历最重链路上所有波长。设1 1 为网络 中的节点数，则一条通道的链路数的上界为h,所以其总的时间复杂度为 o ( h w ) , w为光纤中的复用波长数。 6 ，全局最大总和 m a x s u m ) w 该算法的基本思路是对每一 光连接请求在给定路由 卜 对所有的可用波长， 依 次计算将波长几 分配给该连接请求后， 网络中其他所有通道在几 上降低的可用信 道数的总和， 选定降低总 和最小的波长。 该算法在选择空闲波长时， 由于利用了 全网的波长占 用信息， 因此可以保证分配该 波长后全网所有通道的可用信道数最 大。其优化目标可用如下公式表示: 、 m illa e a ( p 艺 u (艺d ( l , ( 1 , a ) , p ( p , a ) ) ) ( 2 . 2 ) p . g ( p) i c l ( p ) n l ( p ) 时问复杂度分析如 f :设网络中有h个节点，则所有可能的通道最大链路数为 ho 厂的 相邻 通路p 的p ( p , a ) 可 在 时间o ( h ) 内 得到， 设m是 相 邻通 道的 数h ， w为p * 上的 可 用波长 数， 则 确定 所有 波长， 所 有相 邻通路的p ( p , a ) 的 时间 为 o ( m h w ) ， 其中a 1 h z ， 考虑最坏情况， 则算法的时间复杂度为。 ( w h ) o 7 、 相对 容量 损失( r e l a t i v e c a p a c i t y l o s s : r c l ) 该算法是在全局最大总和算法的基础上形成的， 其思路为对所有波长， 依次 计算为通道分配该波长后， 其它侮条通道在此波长土降低的可用信道数与其相应 的可 用信道数的比值， 累加此比值， 从中选定比值最小的波长。 相对容量损失算 法也是考虑全网状态的一种算法， 它的特点在于将分配了某个波长后对其他通路 的影响定义为相对容量损失， 即某相关业务在某波长下减少的信道数与它在各波 长 下总的剩余信道的比值，如果所选择的波长使得各相关业务的该比值之和最 小， 则认为所选择的空闲波长对全网所有通道总和的影响最小。 其时间复杂度与 全 局 最 大 总 和 算 法 相 同 ， 为 0 ( w 1 1 ) 。 该 算 法 的 优 化目 标 可 用 如 下 公 式 表 示 : 兰 州 大 学 研 究 生 学 位 论 文 u ( 艺d ( l , ( 1 , a ) , p ( p , a ) ) ) l e l ( n ) n l ( p ) y_ p ( p , 兄 ) ( 2 . 3 ) 艺卿 a e a ( p ) p e 8 .最小影响 ( l e a s t - i n f l u e n c e : l t ) 28 j 该算法也是考虑全网状态的一种算法，思路与全局最大总和算法较为类似， 算法所计算出的都是分配某波长后对其他工作业务的影响的绝对值。 但不同之处 在于该算法对具休情况的考虑更为细致， 比如这样一种在实际网络中很常见的情 况: 两个相关业务之间的公共链路并不止 一 条， 同时在这些公共链路中作为瓶颈 链路的也不止一条， 此时如果将影响值按照全局最大总和算法所得出的仅视为一 条信道， 显然考虑得太粗略了。 因此为了 尽量避免这种情况， 引入了 最小影响算 法， 并且从另外一个角度来描述波长分配对网络的影响， 它首先计算网络中与新 业务相关的业务在新业务选定路由上各波长遭遇的瓶颈链路数， 接着选择具有最 小瓶颈链路总数的波长， 这样造成瓶颈链路多的波长 影响值就大， 反之就小， 从 而更加细致地反映了网络的实际状态。 其时间复杂度为。 ( w h 3 ) 。 该算法的 优化 目 标可用如下公式表示: m ma . a ( n l . yd ( l , ( 1 , a ) , p .( p , 兄 ) ) ( 2 . 4 ) p e c ( p ) r e l ( 川, l ( n 9 . 相 对 最小 影响 ( r e l a t i v e l e a s t i n f l u e n c e : r l i ) i20 从上面的分析中不难看出， 相对容量损失与最小影响算法实际上是从两个不 同的角度对全局最大总和算法的改进。 前者考虑了受波长分配影响的通道的可用 信道数，从而引入了相对容量损失的概念，可用信道数越小，则该比值就越大， 那么分配时就应尽量避免: 后者则考虑了实际网络中相关业务的公共链路包含多 条瓶颈链路的情况， 这样的链路越多， 则影响值就越大， 那么在分配时也应加以 避免; 而这里的相对最小影响算法则结合了_ 七 述两种算法的优点， 它将各相关业 务在各波长上的瓶颈链路总数除以 此业务的可用信道数， 再将此比值累加， 选择 具有最小累加值的 波长，即先采用最小影响算法的思路得到一 个绝对的影响值， 再将该值去除以 受波长分配影响的通路的可用信道数， 从而得到一个最终作为判 据的相对影响值。由于相对最小影响算法更精确地描述了新建光路对网络的影 响， 据此进行的波长分配将有助于提高网 络的性能。其时间复杂度为o ( w h3 ) 。 兰 州 大 学 研 究 生 学 位 论 文 该算法的优化日标可用如 下 公式表示: 艺u ( l , ( 1 , a ) , p ( p , a ) ) n飞 ( n s s a ( p * ) 工 i e l ( 川n l ( p ) yp ( p , a ) ( 2 . 5 ) p e 舀( p 免 恢复算法要求恢复时间尽量短， 因此在路由 选择和波长 分配