（计算机应用技术专业论文）网络中可靠路由算法的研究.pdf

山东师范大学硕士学位论文 网络中可靠路由算法的研究 摘要 2 l 世纪是数字化、信息化飞速发展的一个世纪，各种多媒体业务的纷纷呈现，最终导 致了网络通信量的爆炸式增长，这就必然要求扩大广域骨干通信网的容量。随着各行各业 对网络信息系统依赖程度的不断提高，网络生存性问题成为人们日益关注的焦点。传统的 基于防御思想的网络保护措施不可避免地带有滞后性和被动性。随着日趋严重的网络信息 系统安全问题的出现，业内已经纷纷开始意识到进行网络生存性( s u r 、，i v a b m t y ) 研究势在必 行。 本文讨论的网络生存性研究是致力于开放式网络环境下，保证系统能够在无法完全抵 制或消除攻击时，尽可能维持关键业务的运行。第一章提出研究背景，简要阐述了网络生 存性的研究现状及许多学者的研究成果，并概述本文所做的工作及内容安排；第二章重点。 介绍了网络生存性技术及生存性技术的实现机制一保护恢复策略，并详细讲解了保护技 术。 科技的发展不仅大大增加了网络中的业务流量，同时使得用户对业务服务质量的要求 也日益提高。由于不同网络的作用不同，我们在进行路由选择时的服务要求也是不尽相同 的，为此我们引进了服务质量( q o s ) 的概念。目前网络服务质量已经成为越来越热门话 题，其根本原因归结如下： 网络中实时性的业务越来越多，比如实时多媒体交互系统、视频会议、远程教育 系统、金融信息系统等等，这类业务对q o s 有严格要求，他们的大量出现推动了 q o s 的发展。 用户对网络服务质量要求日益多样化。网络运营商为满足不同用户的不同要求， 必须通过q o s 机制来提供更多有区分的、适应性更强的业务服务。 此外，为适应网络需求，达到提高网络利用效率、降低网络成本的目的，也要加 强对q o s 研究。 因此，第三章本文就q o s 路由展开讨论，文中首先对网络中的路由算法做了简介， 又阐述了q o s 技术的现状及相关技术，最终将两者结合介绍了基于q o s 技术的路由算法， 提出了服务质量路由算法及研究中存在的问题。 在第四章中，综合全文，给出一种满足多个q o s 约束的基于链路保护机制的不相交 路由算法，该算法通过图论的有关性质得到满足带宽、时延2 个q o s 约束条件的源与目 i i i 山东师范大学硕士学位论文 标节点对间的所有路径及其最短链路不相交相似路径，从而使高实时性网络得到更好的优 化。 第五章主要进行算法实验。文中给出了网络模拟模型，对本文提出的新算法在该模型 中进行实验、讨论其可行性，从拒绝率、资源利用率、网络负载、平均路径长度等多个指 标进行相关分析并与传统的基于剪枝的算法进行比较，得出相应的结论。 第六章综合全文做出总结：可生存性研究已经成为当前的研究热点，其成果不可忽视， 但是其中还存在不少的脆弱点和系统组建缺陷，因此有待于一步研究。最后总结作者在学 习过程中的不足，提出研究中还存在的一些问题，对未来进行展望。 关键词：可生存性；保护技术；服务质量路由；不相交路径 分类号：t p 3 11 山东师范大学硕士学位论文 r e s e a r c ho nr e l i a b l er 0 u t i n ga l g o r i t h m0 fn e t w o r k a b s t r a c t t h e2ls tc e n t u 巧i sar 印i dd e v e l o p m e n tc e l l t u r ya b o u td i g i t i z e d 觚di n f | 0 m a t i o n i z a t i o n i t t a k e so ns om a n ym u l t i m e d i as e n ，i c e st h a tt h et r a 伍ci nt h en e t w o r kg r o w sa tr a i l w a ys p e e d t h e r e b yi ti so b l i g a t o 巧t oe n l a r g et r a m co 九h eb a c k b o n en e t w o r k w i t ha l lt h es e r v i c e sm u c h d e p e n d e n c yo nt h en e t w o r ks y s t e m ，t h en e t w o r ks u i v a b i l i t yb e c o m e st h ef o c u sw h i c ht h e p e o p l ep a ya t t e n t i o n t h ei d e ab a s e do np r o t e c t e dm e c h a n i s mh a st h eh y s t e r e s i sq u a l i t ya n dt h e p a s s i v i t yi n e v i t a b l y a l o n gw i t hs e c u r i t yo ft h en e t w o r kb e c o m i n gw o r s e ，t h es t u d yo ft h e n e t w o r ks u r v i v a b i l i t yi si n e v i t a b l y t h er e s e a r c ho ft h en e t w o r ks u r v i v a b i l i t yw h i c hw eh a v ei sb a s e du p o nt h eo p e nn e t w o r k 1 ls h o u l de n s u r et h ep i v o t a ls e r v i c e sm a i n t a i na sf a ra sp o s s i b l e ，w h e nt h ea t t a c ki sn o ta v o i d e d h lt h ef i r s tc h 印t e rw ep r o p o s e dt h er e s e a r c hb a c k g r o u n d ，e l a b o r a t e dt h en e 铆o r ks u n r i v a b i l i t y r e s e a r c hs t a t u sp r e s e n t l ya n ds o m er e s e a r c hr e s u l t so fm a n ys c h o l a r s a t1 a s tw es u m m a r i z e d t h ec o n t r i b u t i o nw h i c ht h i sa n i c l ed o e s i i lt h es e c o n dc h a p t e rw ei n t r o d u c e dt h en e t w o r k s u r y i v 2 l b i l i t yt e c h n 0 1 0 9 ya n dp r e s e n t e dak i n do fr e a l i z a t i o nm e c h a n i s m2 i b o u ts u r v i v a b i l i t y t e c h n i c a l t h ep r o t e c t i o l l r e s t o r e ss t r a t e g y ，a n dp r o t e c t i o nt e c h n i q u ew a se x p l a i n e dd e t a i l e d l y t h et e c h n i c a ld e v e l o p m e n tn o t o n l y i n c r e a s e dt h en e t w o r kb u s i n e s s g r e a t l y ， b u t e n h a n c e dt h eq u a l i t yo fs e r v i c ew h i c ht h eu s e rr e q u e s t e d b e c a u s eo ft h ed i f f e r e n tf u n c t i o no f t h ed i f f e r e n tn e t w o r k ，t h er c q u e s ti sd i f 传r e n tw h e nt h er o u t i n gw a ss e l e c t e d s ot h ec o n c e p to f q o sw b ei n t r o d u c e di n t o t h ee s s e n t i a lr e a s o nw h i c hq o si sb e c o m i n gm o r ea n dm o r ep o p c o u l db es u n l m a r i z e da sf 0 l l o w s ： t h e r ea r em o r ea n dm o r er e a l t i m es e r v i c e s ，f o re x a m p l et h er e a l t i m em u l t i m e d i a i n t e r a c t i v es y s t e m 、t h ev i s i b l ec o n f e r e n c | e 、 t h el o n g d i s t a n c ee d u c a t i o ns y s t e m 、 矗n a n c i a li n f o n n a t i o ns y s t e ma n ds oo n t h i sk i n do fs e r v i c e sh a v et h es t r c lr e q u e s tt o q o s ，a n dt h e i ra p p e a r a n c ei m p u l s et h eq o sd e v e l o p m e n t t h eu s e r s r e q u e s tf o rq o si sd i v e r s i f i c a t i o n i n t e m e ts e n r i c ep r o v i d e “i s p ) m u s t p r o v i d eak i n do fd i v i s i o n a la n da d a p t a b l es e rv i c et h r o u g hq o st os a t i s f i yt h e d i f f e r e n tr e q u e s t so fd i f f e r e n tu s e r s v 山东师范大学硕士学位论文 i na d d i t i o n ，t h eq o sr e s e a r c hm u s tb er e i n f o r c et oa d a p tn e t w o r kd e m a n d 、t oe n h a n c e t h en e t w o r ke f f i c i e n c ya n dt or e d u c et h en e t w o r kc o s t a c c o r d i n g l yt h eq o sr o u t i n gw a sd i s c u s s e di nt h et h i r dc h a p t e r a tf i r s tw es u m m a r i z e dt h e r o u t i n ga l g o r i t h mi nt h en e t w o r l 【，a n dt h e ne l a b o r a t e dt h eq o st e c h n o l o g ys i t u a t i o na tp r e s e n t a n dt h ei n t e r r e l a t e dt e c h n o l o g y ，a l s of i n a l l yi n t r o d u c e dt h eq o sr o u t i n ga l g o r i t h mb a s e do n b o t ho ft h e m ，a n dp r o p o s e ds o m eq u e s t i o n sw h i c he ) i s t e di nt h er e s e a r c ho ft h eq u a l i t yo f s e r v i c er o u t i n ga l g o r i t h m i nt h ef 0 u r t hc h a p t e r ，c o n t a c t i n gt h ec o n t e x t ，ar o u t i n ga l g o r i t h mi sp r e s e n t e db a s e do n p r o t e c t i n gm e c h a n i s mw h i c hc o u l ds a t i s f ym a n yq o sc o n s t r a i n t s t h i sa l g o n t h mf i r s to b t a i n s a l lp a t h sw h i c hs a t i s f yt h eb a n dw i d t ha i l dt h el a t e n c yb e t w e e ns o u r c ea n dd e s t i n a t i o nn o d e s t h r o u g ht h er e l a t e dn a t u r eo fg r a p ht h e o r y t w oo ft h es h o r t e s tl i r 墩一d i s j o i n ts i m i l a rp a t h sc o u l d b ea c h i e v e db yt h i sw a ys ot h a tt h er e a l t i m en e t w o r kc o u l dg e tt h eb e t t e ro p t i m i z a t i o n t h ee x p e r i m e n to f m ya l g o r i t h mw a sc a r r i e do ni nt h ef i f t hc h a p t e i nt h ea n i c l ew eg a v e an e t w o r km o d e l t h en e wa l g o r i t h mo ft h i sa n i c l ew a sc a r r i e do ni nt h em o d e l t h e nw e d i s c u s s e ds o m ef a c t o r sf o ri n s t a n c ei t sf e a s i b i l i t y 、t h er e je c t i n gr a t e 、n e t w o r kl o a d i n g 、t h e a v e r a g er o u t i n g1 e n 醇ha n ds oo n w ea n a l y s e dt h e s et a r g e t sa n dd r e wac o n c l u s i o nt h a ti tw a s p r e f e r a b l e i nt h es i x t hc h a p t e r ，w em a d et h es u m m a r y ：t h es u r v i v a b i l i t yr e s e a r c ha l r e a d yb e c 锄es o m e a c h i e v e m e n tw h i c hw a sn o t i c ea _ b l e h o w e v e ri tw a sv u l n e ra _ b l ea 1 1 dh a ds o m es y s t e mn a w s s o t h er e s e a r c hm u s tb ef u n h e r f i n a l l yi tw a ss u m m a r i z e dt h ei n s u 伍c i e n c yo ft h er e s e a r c h ，a n d p r o p o s e ds o m eq u e s t i o n si nt h er e s e a r c h i nc o n c l u s i o nt h ef u t u r ew a s v i e w e d k e y w o r d s ：s u r v i v a b i l i t y ；p r o t e c t i o nt e c h n i q u e ； q o sr o u t i n g ；1 i n k - d i s jo i n tp a t h s c l a s s i f i c a t i o n ：t p 311 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得( 注：如没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：王鹰晃 新替硝 学位论文版权使用授权书 本学位论文作者完全了解生堕有关保留、使用学位论文的规定，有权保留并向国家有关 部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权兰越可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：王秀器 导师签字号锄彳 签字同期：2 0 0 8 年弓月弓。同签字日期：2 0 0 艿年 占月多9 同 山东师范大学硕士学位论文 1 1 研究背景 第一章绪论 随着计算机技术和通信技术的飞速发展，计算机网络也越来越趋于成熟，并以全速进 驻到工业、农业、科学等各个领域，深刻的影响和改变着人们的工作及生活方式。越来越 多的网络应用必然要求网络能够在故障发生时保证业务的连通性和服务质量。另一方面， 随着光网络技术的进步，链路传输速率已达数1 0 g b s ，甚至更高。显然，一条链路的失效 可能影响到大量的网络业务，而当前常用的基于i p 路由协议的恢复机制至少需要几秒到几 分钟的时间n3 来恢复正常状态，这将不可避免的提高丢包率，造成严重服务质量问题以及 网络性能的下降。因此，网络生存性及可靠性研究得到人们越来越多的关注，已经成为互 联网研究中的一个关键问题。 1 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 ) 网络得到了越来越广泛 的应用，它采用波分复用技术，能够在一根光纤上复用数以百计的波长信道，其中每个波 长信道都具有很大的传输容量( 例如o c 一4 8 电路容量为2 4g b p s 、o c 一1 9 2 电路容量为l o g b p s ) ，因此，一旦发生光纤断裂或其他物理故障，就会造成非常巨大损失，一些重要数 据的丢失甚至可能给社会带来灾难性后果。因此，在网络设计过程中，保证网络的生存性、 健壮性自然成为网络设计的首要考虑因素。 随着人们对生存性技术的关注，国内外的许多研究机构也都对其投了大量的人力、物 力，其研究重点可概括为生存性的基本概念心1 、生存性体系结构、系统模型口1 、系统分析 与设计、系统工程方法和工具、生存性风险评估h 1 等。 就国内目前的研究来看，网络生存性设计主要基于两种模式啼1 ，即基于入侵使用情景 的重新设计和基于入侵容忍技术的生存系统设计方法。简单来说，第一种模式是在故障产 生后对系统模型的重新开发，目前还处于研究阶段；而第二种模式采用了容忍入侵的策略， 山东师范大学硕士学位论文 它具有高效的监测系统，一旦发现故障，便调用冗余资源进行系统异常修补。第二种模式 的代价较第一种模式要高一些，并且现阶段的研究还不是很成熟，目前比较经典的是基于 入侵检测技术的设计模式，它通过对网络故障的快速检测、定位和恢复使其可靠性提高。 现阶段，网络生存性研究哺7 1 已经得到了很大重视，很多知名学者就该问题的不同方 面作了深入研究，问题涉及故障分类、生存性建模分析、故障恢复技术、生存性网络规划 等许多子领域，并取得了一些成果。 在网络拓扑规划方面，m i n k y uk i m 啊1 等人主要在具有随机性的大型网络拓扑的保护问 题上深入考虑，利用该网络的随机图模型及概率论保证网络可靠性；w e i e h e n b e r gge 旧1 等人进行了低可靠性网络元素基础之上的高可靠性物理网络拓扑的研究。其出发点是，假 设网络模型中的故障元素是链路而非节点。最终，对故障链路详细考察结论如下：平均链 路故障概率较高的网络，其可靠性对网络拓扑结构的依赖程度较大，此时，只有保证较高 的节点度数，才能获得更好的网络可靠性n 0 。 在光网保护策略上，o g e r s t e l 、r r a m a s w a m i 和g h s a s a k i 1 分别研究了链路、节 点、信道三种故障状态下，w d m 点到点链路和有限波长转换的环形网络。s r a m a m u r t h y 和 b i s w a n a t hm u k h e r j e e n 2 1 考虑了w d m 网状网中单链路故障的多种保护策略，设置优化目 标为全网中波长总数最少( 包括正在使用的波长和预留波长) ，同时给出了在静态业务条 件下通道保护及链路保护的整型线性规划描述。b d o s h i 1 3 1 等人从网络初始条件受限角度 出发，着重研究了在初始光通道及网络资源特定条件下能够保护的最大通道数，以及在限 定的生存性要求下正常工作的最小网络资源。c b a w o r n t u m m a r a t 和l w u t t i s i t t i k u l k i j 【l 、 将三种保护方式：最小开销( m i n i m a lc o s t ) 、单链路保护( s i n 9 1 el i n kb a s i s ) 和链路 不相交( d i s j o i n tp a t h ) ，从“冗余资源需求 、“运行简单”、“操作可行性”三个方面进 行了比较，并得出了各自的冗余资源需求下限。 m u r a r is r i d h a r a n 、m u r t iv s a l a p a k a 和a r u nk s o m a n i 1 5 1 研究了动态业务条件下的 网络优化问题，提出了一个适于快速的、基于l p 松弛( r e l a x e d ) 技术的启发式算法。 陆绮荣、庄松林n6 1 等人对环形网和网状网结构的光层保护进行了研究，并结合工作 保护光通道功率测试、故障定位、开光倒换协调等技术，设计了一个符合我国光通信发展 现状的l ：1 光层保护方案。江雪敏、李彤岩n 订等人讨论了w d m 光层生存性机制基础之上 的多层网络联合生存性机制，提出了一种多层协调的实现办法，并讨论了多层空闲资源 2 山东师范大学硕士学位论文 设计中的共享问题。 可见，对生存性的研究已经涉及到很多方面并逐步走向成熟，目前其研究成果也是显 而易见的。 1 2 本文的内容及主要工作 1 2 1 主要研究内容： 本文主要着力于网络生存性技术的研究，首先对生存性技术的基本含义作了综述性阐 述，其实现机制主要体现在路由算法上。通过分析，整理本文主要思想如下： 不同的业务对网络的服务质量有不同的要求，因此，保障q o s 基础之上的网络生存 性变得更加关键。我们进行生存性设计的目标是，要尽量保障网络的连通性，使网络应用 不会因为个别故障因素而出现业务中断现象，同时保证满足业务的服务质量要求，并最小 化网络代价。 本文对此问题的解决方式如下：即提出更加新颖的链路不相交的路由算法，达到在不 提高算法复杂性的基础上，优化网络资源的目的；并通过网络模拟实验验证其可行性。 1 2 2 研究内容的主要创新点 更加深入细致的进行链路不相交问题算法的研究n8 1 9 卫0 1 。以往的算法主要是通过剪枝 法来查找路由，这样找到的两条链路不相交路由，可能相差的链路数太大，从而造成 数据在从工作路由转到保护路由后的传输时延增加，而此时的网络中却可能存在两条 传输性能相似的链路不相交的次优路由，如果选择这两条路由，则能够保障业务在工 作路由和保护路由传输时，对时延要求的一致性。此外，上述算法可能从拓扑图中根 本找不到两条链路不相交路由( 比如最短的两条路由有交叉链路时) 。本文提出找到源、 目的节点对间的k 条路由，通过交集为空的理论进行路由选择，从而避免上述两方面 的问题，提高网络性能。 将q o s 路由与网络生存性问题有机结合。本文提出的生存性设计表现如下：在网络正 常运行的情况下，保证网络提供业务要求的q o s 能力；一旦出现故障( 如地震) ，网 3 山东师范大学硕士学位论文 络将无法正常运行，此时便要进行网络生存性设计堙l 2 刳。 1 2 3 本文内容安排 由于无论人们设计多么高级的通信网络，采用多么周密的故障处理方法，像地震等自 然灾害或网络的物理故障总会不可避免地存在着。那么一旦故障出现，其生存性的关键点 就自然落在了网络的自愈能力上，即发生故障时，网络能够迅速从失效链路中自动恢复所 携带的业务流数据，使网络不会因为故障而导致通信中断乜3 1 。在通信日益发展的今天，网 络的生存性问题被提到了前所未有的高度，可见，对网络的生存性进行深入研究不仅具有 重要的实用价值，而且具有深远的理论意义。 本文主要以w d m 网为模拟网络环境，对光网络中保护路由算法进行了一些列研究。 主要针对波分复用技术中的网络路由问题，提出了一种基于链路保护机制的q o s 路由算 法。该算法利用图论的有关性质得到任意两点间的所有路径，并过滤链路条件使其满足 q o s 约束，在此基础上运用集合的性质求出结点对间的两条链路不相交的最短相似路径， 对大数据流复用及高实时性网络都能起到更好的优化作用。 本文第一章主要对当前网络生存性现状及研究背景进行概述；第二章重点对生存性 技术做了综述，阐述了生存性技术的实现机制：第三章详细描述了基于服务质量的路由 算法；第四章针对光网络中的故障中断问题提出一种不相交链路保护算法；第五章对提 出的新算法进行实验研究，证明其可行性；第六章是对本文的总结及对光网络未来的展 颦。 4 山东师范大学硕士学位论文 第二章光网络生存性的基本原理 为了增强网络性能、保证网络健壮性心制，需要对网络中( 本文以w d m 光网络为研究背 景) 的许多问题进行优化设计，这些问题主要包括：网络生存性设计问题；业务疏导问题 等。随着网络业务爆炸性增长及在各个领域的广泛应用，网络生存性问题已成为人们关注 的焦点。目前业内提出了很多关键词，比如可靠性、抗毁性等，它们本质上都是以网络生 存能力的研究为出发点。本章中，我们主要就网络生存性问题展开讨论。 2 1 网络的生存性概述 前面本文已经讲过，在实际操作中，w d m 网络中每个信道都具有很大的传输容量，一 旦发生故障，就会造成非常巨大损失。因此，在网络设计过程中，生存性及可靠性设计日 渐成为人们关注的焦点。 关于网络生存性( s u r v i v a b i l i t y ) 2 5 1 说法不同，早在1 9 9 3 年n e u m a n n 2 6 1 等人正式提出 了网络系统可生存性定义：在任意的不利条件下，基于计算机通信系统的应用所具有的持 续满足用户需求的能力。其中，用户需求包括安全性、可靠性、实时响应和j 下确性等需求； 到1 9 9 7 年e 1 1 i s o n 口 等人进一步完善了网络系统生存性的定义：网络系统在遭受攻击、 故障和意外事故的情况下及时完成任务的能力，属于网络完整性的一部分。潘世英乜1 等将 网络生存性理解为网络安全研究的第三个阶段，即容侵容错，具体指在系统受到攻击和破 坏后系统自我恢复的能力，主要考虑如何使网路在受到攻击和破坏后仍能恢复，并确保基 本服务的实现。 现实生活中，网络故障不可避免，因此，必须加强网络生存性研究，可以通过采取对 网络故障进行快速检测、定位和恢复的方式，保障网络健壮性。 2 1 1 网络生存性指标 本文在进行网络生存性设计时，要达到的最理想的状态是：对于给定的网络拓扑结构， 能够在最短的时间内使故障元素获得最大程度的恢复，并同时保证最大的资源利用率。然 5 山东师范大学硕士学位论文 而由于事件的互斥性，很难同时实现所有这些要求，所以需要根据不同的业务或用户需求 以及网络本身的特点，采取相应地措施，从而满足网络的生存性指标要求。 常用的网络生存性指标主要有： ( 1 ) 故障恢复时间乜引：是指从网络故障发生时，到业务恢复正常传输所需的时间。该 项指标最直接，也最能体现网络的生存性能力。众所周知，对于网络用户来说，传输过程 是透明的，他们所能感受到的就是网络提供的业务服务质量，而其中最敏感的因素便是故 障恢复时间。 ( 2 ) 业务请求拒绝率：是指被拒绝的网络业务数量与总体业务请求数量的比率。生存 性网络研究的目标是最小化请求拒绝率。 ( 3 ) 平均网络负载：网络负载是指网络链路中的流量负荷，一旦链路负荷过重，将直 接影响整体网络的连通性。因此，最小化网络负载乜引将有利于网络生存性的研究。 ( 4 ) 业务平均步长：某些网络有时以步长来衡量代价耗费，因此最小化路径长度是网 络优化指标之一。 ( 5 ) 网络资源利用率：这是衡量任何一个网络优劣的可靠指标，提高网络利用率是网 络运营商追求利益的根本。 ( 6 ) 鲁棒性：即健壮性，是指经历过一次网络故障后，网络再次承受故障的能力。它 主要用来衡量网络业务的可持续性。 其中，网络资源利用率、业务请求拒绝率和平均网络负载是几个最常用的评价指标。 2 2 网络故障分类 由于遭受破坏的因素及网络元素不同，网络故障也是多种多样，按照光网络中故障的 表现方式不同可分为软故障和硬故障们；按照故障产生的元素不同可分为信道故障、节点 故障和链路故障乜创。概念解释如下： 所谓硬故障是指某些意想不到的突发事件致使传输信道中断的事件，如地震、光纤断 裂、收发元器件失效等；软故障是指传输过程中由于信号逐步衰减，而造成信息丢失的事 件，如光纤损耗增大等。 不难看出，硬故障对网络业务影响较大，但处理方便；软故障对网络业务的影响比较 6 山东师范大学硕士学位论文 小，但出现机率较高，不容易被发现，并且难以对故障精确定位。 因而，从科研角度出发，光网中的故障按位置区分更利于研究： 信道故障是由于该信道对应的特定激光器或接收器出故障引起； 链路故障主要是由于光纤断裂引起； 节点故障主要是由于断电或是地震等灾难性情况引起。 2 3 网络故障恢复 网络的生存性实现机制根据是否预留备用资源和是否进行重路由计算，通常把故障处 理策略分为保护( p r o t e c t i o n ) 和恢复( r e s t o r a t i o n ) 口门两种。保护措施和恢复措施均是在 网络故障情况下，使受损的业务得以重新运行。原理上，两者均利用重路由方式( 重新选 择新的路由来代替故障路由) ，继续故障业务数据传输。就具体实施方案而言，保护和恢 复方法又有所不同。两种方案各有利弊，恢复机制能够提高网络资源的利用效率；保护机 制可提供更快的恢复时间，有利于网络q o s 的保障。下面我们将做详细区分。 所谓保护方案口2 1 是指，事先为业务分配好预留的保护资源即备份资源，主要利用节点 之间预留的备用资源来实现网络保护。当故障发生时，业务可以由事先预留的保护资源承 载，即将工作通路上的通信信号倒换到备用通路上，使工作信号通过预留的保护通路维持 业务正常传输；而恢复方案指，并不事先为业务分配预留的保护资源，在检测到故障时， 动态地从网络中寻找替代的路由，来承载受故障影响的业务。如果此时找不到合适的路 由，那么，该工作路径上携带的业务就会丢失。 两种方案对比如下： 由于保护机制是事先对特定的故障做了假设，进而预留了备份资源。它能够确保 对于预料之中的故障( 如单链路失效) 业务的恢复，而对于一些未知故障( 如多链路同时 失效) ，则不能确保其恢复能力； 恢复机制是在发生故障后实时、动态地寻找可用资源，这种方式灵活性较强，可以针 对多种失效情况进行恢复，特别是对于多链路同时失效下的恢复。但由于事先没有预留备 份资源，因此在很多情况下，网络的资源状况不能确定，也就无法确保及时恢复。 保护机制是在牺牲资源利用率的前提下实施的，因而可以较快的实现业务恢复；恢 7 山东师范大学硕士学位论文 复机制是动态地根据当前网络状态重路由，从而可以实现较高的资源利用率，但业务恢复 时间较长； 由上面的阐述可见，保护和恢复方案两者不存在互斥现象，因此，我们在进行网络的 生存性设计时，往往会考虑将保护和恢复方案折中的办法，取两种方案中的优点合并，从 而为客户提供多种服务级别，尽可能做到在恢复时间、运行保障与效率及成本之间取得平 衡。同时保证故障情况下，时效性和网络资源的合理化利用，即保证在一定的约束下为工 作通路预先选择好保护通路。这就相当于以网络生存性为约束条件的资源优化的问题。 一般而言，运营商根据不同的服务标准，对不同业务选择不同的方案，选择依据如下： 对于重要的业务，如金融业，一般采取保护的方案； 对于一些特殊的拓扑，如链形、环形或环网相交等可以采用保护方案； 对于网络拓扑连通性强，且对网络的资源利用率要求较高的一些网络，则可以选 用合适的恢复方案。 由于现实中网络资源的不足，在实际的网络操作中，通常以保护机制2 1 为基础，来保 障一些可预料的故障，( 如光缆断裂等公共失效故障) ，然后，再使用恢复机制进行加强，保 障整网范围内的故障或失效。根据不同要求的业务可以选择不同类型的方法以保证其生存 性，例如对于实时业务，可以使用链路节点保护，即预先建立保护通道和预留资源的保护 方式；而对于“尽力而为 的业务，就可以按需建立保护通道，或者依靠高层的恢复机制。 与恢复机制相比，保护机制具有更高的可靠性和更快速的恢复能力，这更适用于具有巨大 传输容量的光网络，因此本文主要研究的是保护机制。 2 4 网络保护策略 随着技术的发展，网络所承载的信息流量显著增加，特别是在主干网中，网络中设备 接口的速率达到2 5 g b s 以上，即使仅持续几移的短暂性故障也会造成大量的数据丢失。 因此，为故障的业务寻找新的传输路由，并使其在尽可能短的时问内自愈变得越来越重要。 目前，许多文献砼3 3 1 对于光层故障保护方案进行了大量的研究，根据不同的功能或方 式总结如下： 8 山东师范大学硕士学位论文 从重路由的角度分为：基于通道的保护、基于链路的保护及区段保护； 一，一、 s 。 s i d 卜争 123 43 ( a ) 通路保护 s ，、，、，- 、，、d 1 卜- lzj 4 ) 图2 1 通路保护和链路保护 ( b ) 链路保护 根据备用资源的预留方式可分为：专用保护和共享保护； s 1 s 1 d _ p 。( w p ：) ：业务l ( 2 ) 的： 5 b p ( b p ：) ：业务l ( 2 ) 的 图2 2 共享保护 图2 3 专用保护 按照路由的计算方式可分为：预计算和实时计算； 2 4 1 通道保护 w p ：业务的工作通路 b p ：业务的保护通路 所谓通道( 路径) 保护口们是指业务故障恢复由通道两端的终端节点来完成。具体说来， 基于通道的保护机制是指对工作路由事先预留一条备用保护路由，在故障发生后，用预留 9 山东师范大学硕士学位论文 的保护通道来传输故障通道中的业务流，从而取代故障通道，实现业务重路由。在通道保 护方案中，每条光路在建立时就已经预设了一条端到端的备用通道并预留了备用资源。一 旦网络中发生故障，受到影响的通道的源一目的节点对问的业务流将自动由工作通道切换 到这两个节点间的另一条与故障通道链路不相交的备用通道上来，从而保证业务恢复。即 当发生故障时，其切换过程只涉及源、目的节点，与中间节点无关，由于是源节点和目的 节点启动保护倒换，因而对故障的具体定位要求不高，但信令协议必须快速准确的将故障 消息传送至源、目的节点。工作状态如图2 4 所示： 4 工作通道 一一一卜保护遵道 1 0 。一3 图2 4 基于通道的故障保护 通道保护又可分为专用通道保护( 备用资源为某条工作通道专用) 和共享通道保护( 备 用资源能同时为多条工作通道提供保护) 。专用保护通常是指1 + 1 通路保护和1 ：1 通路 保护。共享保护是指l ：n 保护方式。 ( 1 ) l + 1 保护 l + l 保护要求发送端始终处于连接状态，由分光器( 这里说的分光器s p l i t t e r 是一种 无源器件，它由入射和出射狭缝、反射镜和色散元件组成，其作用是将所需要的共振吸收 线分离出来) 将业务流信号一分为二，同时在两条并行的通道中传输，从而实现信号保护。 工作通路正常运行时，目的端接收器会收到两条相同的业务流，并随机择优处理。然而， 网络中一旦出现链路故障，处于接收端的光开关就会把接收通道切换到另一条保护通道 上。 如上所述，该保护方案中目的端接收器完全可以独立处理单点故障，源端点并不需要 作其他任何额外的操作，只要将待传输的业务流同时复制到工作保护两条通道中即可。 l o 山东师范大学硕士学位论文 这就使1 + 1 保护执行起来非常简单，能够实现瞬间恢复。同时，该方案也存在缺点，它几 乎浪费了一倍的带宽资源，因而只适合用于带宽完全充裕的网络。 nw k j 一一一 分 一 光 光 班pb 开 器 关 图2 5l + l 保护方式 ( 2 ) 1 ：1 保护 1 ：l 保护方案与l + 1 保护方案原理相似，都是利用两条不相交路径同时路由，以避免 故障对业务的影响。区别是，在l ：1 保护中，正常状态下保护通道并不承载业务流量，只 有当工作通道发生故障时，源一目的端会将业务流同时切换到备用保护通道上。 进行l ：1 保护时，未承载业务流的备用保护通道可以暂时用来传输低优先级的业务， 一旦被通知与其相关的工作通道发生故障时，高优先级的业务将被切换到该备用保护通道 上，而原来在该保护通道中传送的低优先级的业务会被自动丢弃。该方案可以更有效的利 用资源，从而提高资源利用率。但是由于正常工作状态下，备用路径被用来进行其他业务 流的路由，这使得工作路由在发生故障后必须先将故障信息传送到源一目的端，然后才能 把业务切换到备用通道上，因而较1 + 1 保护增加了故障恢复时间。 z nw 光 的多条备用路径 图2 7l ：n 保护方式的简单示意图 基于链路的故障保护方案，是指业务请求经过的每一条链路，都有一条保护路径对其 进行保护，一旦链路出现故障，业务将越过故障点，直接转到保护路径上。它是通过处理 与故障点相邻的节点来实现对业务的恢复的，是将受故障影响的业务流绕过故障链路来进 行重路由。即：在与故障点邻接的两点间，为该故障链路寻找一条可绕过该故障点的备用 路由。显然，该保护方案中，参与保护切换的节点数较少，因而具有较强的本地性，恢复 速度较快。同时由于它的本地性，也使得资源浪费过多，从而，无法有效的利用资源。 在该方案中，对于不同链路中的业务，只要不同时发生故障，就可以共享相同的保护 路径，因此也可以分为专用链路保护和共享链路保护两种。前者是指对于某一链路，提 供专门的保护路径，其他链路则不得使用该专用路径；而后者允许不同的链路保护路径在 其重叠的部分实现共享。比较而言，后者比前者资源利用率要高，而前者较后者的保护力 度大。 1 2 山东师范大学硕士学位论文 4 2 4 3 区段保护 l o 图2 7 基于链路的故障保护 - - o 一一一 工作通道 保护通道 区段保护是折中了通路保护和链路保护各自的特点而得到的一种中庸的保护方式。区 段保护是指在一对节点之间出现光纤断裂故障时，则该段链路中的业务被倒换到这两个节 点之间的另一根光纤中。如果两个相邻节点之间的一根光纤发生断裂，则类似于链路保护。 s 一r 1 、 d - - 厶_ - 一飞一 1 i 乙j i i + 1 j 一1 j 、唑，r 7 n 2 4 4 其他保护方案 图2 8 区段保护 本节开篇提出三种分类方式，在第二种分类方式中，专用的通道保护方案，常常为受 保护的通道预留一条与该工作通道无公共边的保护通道和相应的网络资源，处于保护通道 各链路资源归