（通信与信息系统专业论文）抗毁光网络设计中保护算法的研究.pdf

上海交通大学博上学位论文 抗毁光网络设计中保护算法的研究 摘要 随着w d m 技术的发展，一条光路承载巨大的数据量，光纤故障 可以造成巨大损失。所以迫切需要进行抗毁光网络的设计，保护技术 是一种很有效保证网络抗毁的方法。抗毁光网络不断的发展不仅给保 护设计提出了很高的要求，服务方面也得到了重视，特别是保证 q o s ( q u a l i t yo fs e r v i c e ) ，提供区分服务等方面越来越成为抗毁光网络 设计的重要目标。而可用性就是量度服务的一个重要参数。所以本文 不仅要考虑单播或组播下的保护设计还要考虑基于可用性的冗余资源 利用问题。本文分别研究了基于可用性的保护算法，“工作保护 共 享的保护算法，组播保护算法，基于可用性的波长分配。 对于基于可用性的保护算法。过去，曾以可靠性为基础提供区分服 务，可靠性是在一段时间之内的故障率，但是，这个指标只揭示了故 障出现的频率，没有反映故障的修复时间。可用性是指在任意时间网 络或连接的可用概率，与故障出现频率和修复时间有关。本文考虑了 动态网络情况，业务动态到达和离开且考虑故障的修复时间，故采用 可用性比可靠性更能揭示网络的实际运行状况。在计算过程中，由于 是在线的计算，给出了用于计算可用性的分层结构，应用该分层结构 分别计算工作和保护资源的可用性，在这种改进的波长分层图内求取 路由。通过仿真发现，算法比单纯的使用共享保护和无保护的情况下 有更好的路由成功率。 提出了基于可用性的波长分配算法。用一个阈值限制短光路的波 长选择范围，这个阈值就是总波长数乘以业务请求可用性与光路可用 性之间的比值。这样，波长选择范围与业务可用性相关，对业务可用 性与光路可用性差别较大的业务调小其波长选择范围，这样长光路在 选择波长的时候有更多的机会选择可用波长从而提高长光路的路由成 功率。通过仿真表明，应用限制波长的方法，与f i r s t - f i t 算法相比， 网络可以得到较大的可用性收益，即网络承载的平均可用性有所提高， 并且在阻塞率方面也有所改善，这是因为短光路选路成功的概率比较 摘要 大，而决定网络阻塞率的主要是长光路，所以在增大长光路的波长选 择机会就便得长光路被阻塞变少。仿真发现，算法在大规模的网络内 有较明显的优势，因为大规模网络中长跳光路的比例较大，改善长跳 光路的波长选择能够带来较大收益。一 为了提高“工作保护共享的效率，本文研究了“工作保护 共享 的保护算法。对保护资源定义了三种工作模式，即抢占、孤立和混合， 这三种状态是与动态到达业务的可用性要求相关的。在这三种模式下 保护链路的可用性有不同的值。仿真表明，基于区分工作模式的情况 下，路由成功率有所提高。本算法的性能主要体现在网络所取得的收 益上，也即网络承载业务的平均级别有所提高。 本文还研究了组播保护算法。在s r l g ( s h a r i n g r i s kl i n kg r o u p ) 限制 下，光树内和树外的冗余资源都受到了很大的限制。为了减少s r l g 对网络的影响，本文提出的算法可以调节树内和树外资源的共享度， 通过设计相应的链路费用，分别定义了树内和树外的共享程度，使得 冗余资源得到有效的共享。仿真中，比较了使用与不使用树内树外综 合共享方式下的算法，本文提出的s r l g 共享算法对树的扇出数并不 敏感，随着扇出的变大，算法增大了树内的共享度，使得网络能够尽 量在树内寻找资源共享。 关键词：抗毁光网络，保护，可用性，共享，路由波长分配 i i 上海交通人学博上学位论文 r e s e a r c ho np r o t e c t i o na l g o r i t h m sf o rd e s i g n i n gf a u l t - t o l e r a n t o p t i c a ln e t w o r k s a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to f d mt e c h n o l o g y , al i g h t p a t hm a y b e c a r r yl o t so fd a t as t e a m s as i n g l ef i b e rf a i l u r eo ff i b e rc a nl e a dt ot h e f a i l u r eo fa l lt h e1 i g h t p a t h st r a v e r s i n gt h ef i b e r , a n dr e s u l t si ns i g n i f i c a n t l o s s h e n c e i ti sn e c e s s a r yt od e s i g nf a u l t t o l e r a n to p t i c a ln e t w o r k a 1 1 k i n d so fp r o t e c t i o nt e c h n o l o g i e sa r eg o o df o rf a u l tt o r l e r a n c e s e r v i c eh a s b e e np a y e da t t e n t i o nt ot h eo p t i c a ln e t w o r k s ，i e ，e n s u r i n gq o s ，p r o v i d i n g d i f f e r e n t i a t e ds e r v i c eh a sb e c o m e di m p o r t a n t o b je c t o fd e s i g n i n g f a u l t t o l e r e n to p t i c a ln e t w o r k s a v a i l a b i l i t yi sa ni m p o r t a n tm e t r i ct o m e a s u r es e r v i c ei no p t i c a ln e t w o r k s ，s ot h i st h e s i sc o n s i d e r sn o to n l y d e s i g n i n gp r o t e c t i o n b u ta l s o a v a i l a b i l i t y a w a r e u t i l i z a t i o no fs p a r e r e s o u r c ei no p t i c a ln e t w o r k s t h i st h e s i ss t u d i e sa v a i l a b i l i t y a w a r e p r o t e c t i o na l g o r i t h m ，“w o r k i n g p r o t e c t i o n ”s h a r i n g ，m u l t i c a s tp r o t e c t i o n ， a v a i l a b i l i t y - a w a r ew a v e l e n g t ha s s i g n m e n t t h ea v a i l a b i l i t y b a s e dr o u t i n ga l g o r i t h mi ss t u d i e d t h em e t r i co f r e l i a b i l i t yh a se v e rb e e nc o n s i d e r e dt op r o v i d et h ed i f f e r e n t i a t e ds e r v i c e s ， b u ti ti st h ef a i l u r ep r o b a b i l i t yi nc e r t a i np e r i o do ft i m e 。w h i c ho n l y d e n o t e st h e “h i t p r o b a b i l i t yo ft h ef a u l t h o w e v e r , i nt h ed y n a m i c n e t w o r k s a l lt h et r a f f i cc o m e so rl e a v e sd y n a m i c a l l ya n dt h er e p a i rt i m eo f t h ef a u l ts h o u l db ec o n s i d e r e d ，s ot h ea v a i l a b i l i t yi sb e t t e rt os c a l eo p t i c a l n e t w o r k st h a nt h er e l i a b i l i t y al a y e r e ds t r u c t u r et oa n a l y z et h en e t w o r k a v a i l a b i l i t yi sg i v e n b yu s i n gt h es t r u c t u r e ，t h i s t h e s i sa n a l y z e st h e a v a i l a b i l i t y o fp r i m a r ya n db a c k u p1 i n k s s e p a r a t e l y t h r o u g h t h e s i m u l a t i o n s t h es u c c e s s f u lr o u t er a t i oo fo u ra l g o r i t h ms h o w sb e t t e rt h a n o t h e r s t h ew a v e l e n g t ha s s i g n m e n ti sn o r m a l l yr e a l i z e dt h r o u g ht h ef i r s t f i t a l g o r i t h m t h ed i f f e r e n t i a t e ds e r v i c es h o u l db es a t i s f i e di nt h ea s p e c to f t h ew a v e l e n g t ha s s i g n m e n t ，s ot h et h e s i sg i v e sa na v a i l a b i l i t y a w a r e w a v e l e n g t ha s s i g n m e n ta l g o r i t h m ，w h i c hl i m i t st h es c o p eo fw a v e l e n g t h s e l e c t i o no fs h o r t e rl i g h t p a t h s l i m i t i n gw a v e l e n g t hc a nb ep e r f o r m e d t h r o u g haw a v e l e n g t ht h r e s h o l dt h a tt h em a x i mw a v e l e n g t hi sm u l t i p l i e d b yt h er a t i ob e t w e e nt h er e q u e s t e da n do f f e r e da v a i l a b i l i t y t h r o u g ht h i s t y p eo fw a v e l e n g t ha s s i g n m e n t ，t h el o n g e rl i g h t p a t hh a sm o r ec h a n c et o i i i a b s t r a c t s e l e c tt h ea v a i l a b l ew a v e l e n g t h s i ns i m u l a t i o n s ，t h ea l g o r i t h ml i m i t i n g w a v e l e n g t h so ft h es h o r t e rl i g h t p a t hc a l lm a k et h ea v e r a g ea v a i l a b i l i t ya n d b l o c k i n gp e r f o r m a n c ee n h a n c e d t h eb l o c k i n go ft h el o n g e rl i g h t p a t hi sa m a i nf a c t o rt oa f f e c tt h eo v e r a l lb l o c k i n gp e r f o r m a n c e i n c r e a s i n gt h e c h a n c eo fw a v e l e n g t hs e l e c t i o no ft h el o n g e rl i g h t p a t h sd e c r e a s e st h e b l o c k i n gp r o b a b i l i t yo ft h el o n g e rl i g h t p a t h s o t h e r w i s e ，t h ea l g o r i t h mc a n s h o wb e a e ri nt h el a r g e s c a l en e t w o r k s b e c a u s et h ep r o p o r t i o no ft h e l o n g e rl i g h t p a t h s i s l a r g e rc o r r e s p o n d i n g l yi n t h i st y p eo fn e t w o r k s i m p r o v i n gt h ep e r f o r m a n c eo ft h el o n g e rl i g h t p a t h sm a yb r i n go b v i o u s g a i n i no r d e rt oe n h a n c es h a r i n ge m e n c yo f “w o r k i n g p r o t e c t i o n t h r e e p a t t e r n sh a v eb e e nd e f i n e df o rt h ep r o t e c t i o nl i n k s ：p r e e m p t i o n ，o r p h a n a n dm i x w h i c hr e l a t et ot h er e q u e s t e da v a i l a b i l i t yo fi n c o m i n gt r a f f i c t h e d i f f e r e n tp a t t e r n sc a nl c a dt ot h ed i f f e r e n ta v a i l a b i l i t i e s t h es i m u l a t i o n s s h o wt h a tt h eb l o c k i n gp e r f o r m a n c ea n dt h ea v e r a g eg a i no fa v a i l a b i l i t y a r ea l le n h a n c e dw h i l ec o n s i d e r i n gt h ep a t t e r n so fs p a r er e s o u r c e s f u r t h e r m o r e t h et h e s i ss t u d i e so nm u l t i c a s t p r o t e c t i o n i f s i 也g ( s h a r i n gr i s kl i n kg r o u p ) i sc o n s i d e r e d t h es p a r er e s o u r c e so fi n t r e e a n do u t t r e ea r el i m i t e d i no r d e rt oi m p a i rt h ei n f l u e n c eo fs i u gt h e p r o p o s e da l g o r i t h ma d j u s t st h es h a r i n gd e g r e eo fs p a r er e s o u r c e s an o v e l l i n kc o s tf u n c t i o ni sd e s i g n e ds ot h a tt h es p a r er e s o u r c e sa r es h a r e d e f f e c t i v e l y t h r o u g hs i m u l a t i o n s t h eo v e r a l ls u c c e s s f u ls e s s i o nr a t i oo f p r o p o s e da l g o r i t h mi sb e t t e rt h a nt h ea l g o r i t h mn o tc o n s i d e r i n gt h es h a r i n g d e g r e eb e t w e e ni n t r e ea n do u t t r e e t h ep r o p o s e da l g o r i t h mi s n o t s e n s i t i v et ot h es p a n o u to ft r e e s a l o n gw i t ht h ei n c r e a s eo fs p a n o u t w h i l ee n c o u r a g i n gt h ei n t r e es h a r i n g m a n yp r o t e c t i o n sc a nb ef o u n di n t h ep r i m a r y l i g h t - t r e e s k e y w o r d s ：f a u l t - t o l e r a n to p t i c a ln e t w o r k s ，p r o t e c t i o n ，a v a i l a b i l i t y , s h a r i n g ，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 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：李永刚 日期：2 0 0 7 年7 月1 2 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密。 ( 请在以上方框内打“ ) 学位论文作者签名：李永刚指导教师签名：李乐民 日期：2 0 0 7 年7 月1 2 日日期：2 0 0 7 年7 月1 2 日 上海交通火学博上学位论文 第一章绪论 随着近年来光网络的不断发展，故障的管理变得越来越重要了。光网络变得 规模越来越大，越来越复杂，网络相关的损耗和故障所引起的数据传输中断会引 起不可估量的损失。现已经有技术保证光网络即使故障存在也能够继续提供可靠 的服务。抗毁的基本概念是在满足正常操作之外光网络有最小的冗余资源，使用 这些冗余资源来规避故障。任何保证抗毁的冗余资源都会增大费用，所以在增加 合理的费用下，有效地利用冗余资源、最大化网络的可靠性是非常重要的。同时 根据用户的需求来定制服务为光网络的设计者和运营商提出了新的课题，也是最 优配置冗余资源的可行方案。 1 1w d m 光网络基础 光网络中的光纤可以提供比同轴电缆大得多的容量用以传输数据，而波分复 用技术( w d m ) 又可以提高光纤的传输容量。w d m 能够在一根光纤上提供并行的 数条传输信道来，每个信道都有与电子系统相兼容的传输速率【l 】，一条整个光传 输谱带被分成多个不交叠的频带或波带，每个都是一个单一的传输通道，这些通 道在光域里复用在一起并在光纤上以不同的光载频进行传输，因此在不提高单一 通道速率的前提下整个光纤的吞吐量得到大大的增加，但同时要减少色度色散和 偏振色散带来的信号衰减。一根单光纤支持多个信道，能够带来巨大的带宽，w d m 传输系统可以同时支持2 5 6 个波长【2 ，3 l ，4 0 g b p s 的带科4 ，5 j 。现今w d m 已经进入商 用，并且更加普及。当需求超过单光纤所承载的容量的时候，w d m 成为一种节省 费用的有效手段，不仅能复用多种信道并且可以进行超长距离的传输，巨大容量， 长距离传输，节省费用的特点已经使w d m 成为下一代全光网络的核心技术。本文 的研究对象就是抗毁w d m 光网络，首先应将w d m 光网络内所存在的资源和波长 路由的概念简述一下。 1 1 1 光网络组成 光网络中不仅有光链路还有光节点，总之，在光网络这个大系统中，含有以 下的一些元素： 第一章绪论 节点：能够路由所有从任何光纤中的任何入纤波长通道到任何光纤中的任何 出纤波长通道，每个节点包括多波长的发送器和接收器，光空分交换和光放 大器，这些就组成了整个的光的交叉设备。 网络端口：每个节点都提供低速的本地端设备接入高速的光网络的接口，网 络的端口的功能主要是通过光电转换来实现的，它们能够连接各种s d h 交叉 设备，a t m 节点和i p 路由器，也就是更高层次的交换机和路由器都要通过网 络端口接入更底层的光网。 光链路：在两个相邻节点的之间是双向的链路，这链路许多的光缆，由很多 单向的光纤所组成。 通道：一条连接两节点之间的逻辑链路是通过波长来完成的。 光路：一条通道或者一条级联的通道，它们每个都含有一个波长，所以它们 可以跨越单跳或者多跳节点。在两节点之间建立一条连接。 在光纤通信网中，由以下的一些元件组成： 激光器：发射光信号。 滤波器：选择波长。 复用器( m u x ) 和解复用器( d e m u x ) ：组合或者分解波长。 转换器：通过某个波长输入转换器以另一个不同的波长出转换器。这种元件 只有在有波长转换的网络中出现。 交换器：选择出端口 放大器，再生器和整形器：由于噪声的积聚和传输损伤或者色散效应，信号 有衰减的现象，所以当信号的传输超过一定距离的时候需要对其进行放大再 生或整形，以恢复原信号来。 在w d m 光网络中，就是这些基础的元器件组成的，最重要的传输器件有 o a d m 和o x c 。 ，o a d m 一个光上下复用器( o a d m ) 是一个简单的只有一个入口和出口的波长路由器， 并带有本地上下路端口，o a d m 可以有波长转换的功能。 光交叉设备 如图1 1 所示，是一个基本的光交叉设备，光信号可以从两个入端口路由到两 个出端口，它有两个状态：交叉( c r o s s ) 和直通( b 岫。如果在交叉状态，上入口的信 号被路由到下出口上。而在直通状态，在上入口的信号被路由到上出口上，更复 杂的交叉结构除交叉矩阵之外还包括光放大器和解复用器，如这样的o x c 有m 个 2 上海交通人学博十学位论文 入光纤和m 个出光纤，每根光纤里有w 个波长，入纤的信号被波长解复用器解复 用，每个波长有m x m 个交换。九1 上的交换模块只交换每个端口入纤的九1 信号，从 每个交换矩阵到出端口，所有波长又被一个光解复用器组合到一起。这种o x c 包 括m 个波长复用和解复用器，和w 个m x m 的交换矩阵，且有本地上下路端口。它 可以实现以下几种功能： 交叉态 ： = ： 图1 1 光的空分交换 f i g 1 1s p a c es w i t c h 直通态 空分选择：信号能够被路由到任何一个端口。这在出现故障的时候非常的有 用，控制信号能够激活交换机制，允许波长路由到不同的端口。出故障的光 路可以另外不同的通道上运行，以避免丢失信息。 可调波长选择：通过可调滤波器加以实现。 波长转换：在光域中实现以保证透明性，波长转换器应当嵌入到整型功能模 块中。 多波长放大：补偿波长路由当中的信号，已经有实验表明级联的o x c 会引起 信号的恶化，所以o x c 级联的数目应当受到限制。 1 1 2 波长路由 路由的目标在使用现有的网络资源条件下，满足网络中某节点对之间传输数 据的需求。主要考虑光层的路由问题，用一个可用波长在节点之间建立连接。光 层的角色主要是为更高一层提供光路，满足业务需求。在w d m 光网络中同样的波 长可以分给两个不相干的工作连接上，这样可以用一个波长可以建立很多条光路， 实现波长的重用。 图1 2 所示，在w d m 光网络中的一条光路可以为其分配一个波长或者多个波 3 第一章绪论 图1 2 波长路由：无波长转换与有波长转换 f i g 1 2w a v e l e n g t hr o u t i n g ：w i t h o u tw a v e l e n g t hc o n v e r s i o na n dw i t hw a v e l e n g t hc o n v e r s i o n 长，图1 2 的左侧是每个o x c 没有波长转换设备的情况，每条光路都独立的占用一 个波长，为了防止阻塞，所以至少要需要3 个波长，图的右侧是有波长转换设备的 情况，有些光路不只是给分配了一个波长，有的光路要占用多个波长，但总的波 长使用数目就只有2 个了，第一种情况中，中继节点需要无透明的路由每个连接， 不改变其波长，在第二种情况下，中继节点必须提供波长转换器。波长路由具有 以下的一些特性： 透明性：光路能够在各种速率和协议下承载业务量，所以光层能够并发的支 持多种不同的协议。 波长重用：如图1 2 所示，波长能够在网络里能够被重复使用，两条有共享链 路的光路不能使用相同的波长，因而即使网络里的可用波长有限，能够路由 的光路的数目要超过单光纤所含有的波长数目。 可靠性：在网络元件的故障的情况下，光路可以自动的从另外的路由通过， 许多光器件都是被动的，这些可以为网络提供高的可靠性。 虚拓扑：由节点之间的光路组成的链路所勾画出的拓扑图，这个虚拓扑是提 供给更高层的拓扑图，如图1 3 所示。 电路交换：光路可以根据业务的需求建立和拆除，这些特性与电路交换网络 很相像，但是有更高的传输速率，当今的w d m 技术不能够在光层实现分组交 换，但是在更高的层次里；t n i p 层就可以实现。 4 上海交通人学博上学位论文 图1 3 根据图1 2 生成的虚拓扑 f i g 1 3v i r t u a lt o p o l o g yd r a w nf r o mt h et o p o l o g yi nf i g 1 2 实现波长路由技术有以下两种问题需要考虑：i 光路经过那个路由诸如用了 哪些链路，这属于路由问题；需要给这条光路分配哪个波长，这属于波长分配问 题：i i 高效的使用网络资源都与这两个问题密切相关，为了减少问题的复杂性， 波长路由问题与波长的选择问题需要单独的进行考虑。如果要考虑波长转换，只 要在相应的节点上加入波长转换就行了。 路由算法可以是静态的也可以是动态的。在静态路由下，路由都是固定的， 硬件都是在建网过程中预先布置好的，比如波长转换器的固定配置。动态路由， 也可以叫做重配置路由，一旦有新的业务到达就要使用现有的网络资源为其建立 路由。静态的网络比提供动态路由的网络更加经济些，而且能够用无源元件配置 的静态网络比用有源元件配置起来的动态网络更加可靠。问题是现今多数网络里 流量需求不能够预先知道的并且是随时间变化的，所以在本文中主要研究动态网 络的情况。 1 2 抗毁光网络 w d m 技术已经成为一项主要提高点到点传输容量的技术。支持w d m 的光纤 能够在每个通道上承载大量的信息。在这样的一个系统中，网络故障带来的损失 要远大于传统的网络，一个故障可以造成大量的通信会话的中断，造成大量重要 信息丢失，诸如商业交易，银行数据等。但是不幸的是，光缆断裂、电压损耗、 元件故障、软件问题、火灾这些都是通信系统常遇到的问题。所以设计一个抗毁 光网络是相当的重要的，所以不仅是用户所关心的，更是网络运营商所关心的问 题，因为服务的中断会造成收入的损失、资产损失、法律的损失、竞争力损失以 及可信度的丢失。什么是抗毁光网络? 光网络里的抗毁研究可以分两个范畴【6 j ： 第一章绪论 可靠性和生存性，可靠性是指( 将在1 3 节予以介绍) 系统实现特定功能的能力，系 统出故障的概率越低那么它就越可靠；一个网络具有生存性主要体现在灾难发生 的情况下，网络有能力恢复中断的业务。为了设计抗毁光网络，当然需要网络内 有冗余资源，恰当的配置这些冗余资源使得网络能够规避故障，使得生存性能够 保证到一个令运营商和客户都满意的级别，这些都为网络的规划和设计者提出了 挑战。不同的用户有不同的费用、服务和性能的要求，所以他们需要不同的生存 性的级别。单一的网络策略不能够成为所有用户的解决方案，因此网络设计者就 要综合各种保护和恢复技术来满足不同的客户需求，以实现简单、高效、低费用 的抗毁光网络。 保护技术是利用网络的冗余容量在故障发生时重路由业务量。有两种故障恢 复机制h 3 ，如果恢复路径和波长事先分配好的话，就称其保护策略。另外，如果 在发生故障以后，找到另外一条路由和空闲波长使得动态到达的业务恢复，就称 其为恢复策略。通常在资源利用率方面，恢复机制要好于保护机制，因为恢复机 制并不事先分配好资源，只提供恢复技术以防范各种网络故障，但是保护机制有 更短的恢复时间。 1 2 1 故障的分类 通道故障：一条链路上一条通道出故障可能由于诸如激光器损坏、收发器损 坏等故障造成的，这些故障的解决可以通过将故障通道上的业务搬移到其他 完好的通道上。 链路故障：链路上的所有通道都发生了故障，通常是由于光纤的断裂造成的， 可以将故障链路上的业务搬移到完好的链路上去。 节点故障：由于功率损耗或灾难事件的发生可能造成节点上的硬件故障。 未来的传输网络可能向更少的节点、更长的传输距离的方向发展，这样链路 的故障变得比节点故障的概率大的多- f 7 , 8 , 9 】。 光网络中，光纤断裂故障有很高的发生率，这种故障能够造成巨大的数据损 失，由于环形网络考虑生存性有很大的冗余，造成资源利用率低，而且可量测性 低，所以光网络开始从环形网到m e s h 网的转变，现在设计具有生存性的m e s h 网已经成为研究热点，这些工作主要是考虑规避链路故障和节点故障的 r i o ，11 ，1 2 ，1 3 ，1 4 1 。 6 上海交通大学博上学位论文 1 2 2 抗毁光网络中路由波长分配 近些年来，已经了有一些针对光网络路由与波长分配的研究。光网络资源的 优化问题已经从考虑整个带宽利用过渡到考虑更复杂的范畴了，比如减少昂贵光 器件( 诸如交叉连接( o x c ) ，光上下路复用器( o a d m ) 等) 的数目。 如果o x c 都配有波长转换器，那么一条光路可以被分到不同的波长，这样的 网络称为波长转换网络。如果o x c 都没有配备波长转换器，在网络中建立起一条 光路就要给光路所经链路都分同样的波长，这样的话，就有了波长连续限制，具 有这样波长连续性的网络称为波长连续网络。在一个波长连续网络内使用端到端 的保护策略，为一对源宿节点找到一对链路分离的工作和保护光路，并为其分配 一个可用波长，这种问题就是抗毁光网络内的r w a ( r 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 ) i h j 题。 通常需要选择一对最低费用的路径提供给节点对，与已往最小费用路径求取 相似，抗毁路由就是要求取费用最小的路由对，工作光路和保护光路总的费用要 最小。 在使用共享保护的时候，一条连接总的费用是它工作光路的费用加上它没有 被共享的保护费用的总量，一个路由对可以在网络规划之前都设置好，也可以在 网络动态的情况进行求取。按照不同的流量工程的考虑，又有各种链路费用方程， 诸如减少路由的跳数，链路的长度( 减少延迟) ，均衡链路业务比例( 流量均衡) ，降 低网络费用( 整个网络设备和操作的费用) ，等等。 波长分配可以在路由求取之后完成，不同的波长分配启发式算法在文献 1 5 】 中有所阐述，波长分配可以和工作保护光路的求取结合起来进行考虑。 文献 1 5 】已经证明在波长连续网络内波长分配问题是一个n p 问题，当网络有 波长转换能力的时候，这样的问题可以看作路由的优化问题，可以使用s u u r b a l l e 算法【l6 j 解决。除了用启发式算法来进行抗毁波长路由问题的求取之外，还可以使 用线形规划的办法。线性规划可以预先计算好路由对也可以动态的求取，尽管由 于线性规划的计算量太大实用性不是很强，但是它可以在设计启发式算法的时候 提供参考，在网络中有适当业务量的情况下，线性规划的方法还是很有效果的。 7 第一章绪论 1 2 3 保护和恢复 1 2 3 1 保护机制 保护机制可以分为环形保护和网状网保护。环形保护包括自动保护切换a p s ， 自愈环网，但是环保护和m e s h 保护可进一步分为链路保护和通路保护。在通路 保护里，一旦工作光路发生故障，业务流就在保护通道上重路由，工作通道和保 护通道是链路分离的；链路保护中，业务流只在故障链路周围重路由。通路保护 可以很好的利用网络资源而链路保护有比较快速的恢复时间。近期，有研究者提 出了子通路保护，将工作光路划分为数个段，然后为每一段提供段保护。与通路 保护相比，子通路保护有较好的可量测性和较短的恢复时间。 光纤通信网是一个多层结构，每一层或服务其他层或做为被服务对象，一个 多层网络可以分成一个或多个子网络。在一个层结构中，任何一层属性都是独立 与其他层而被定义的，由此增加或改变某一层并不会影响到其他层，层结构支持 多种协议和服务，并且为设计者提供了多样的生存性选择方案。第一个需要做出 决定是应该在哪一层考虑提供保护，保护技术提供一定冗余资源用来重路由故障 业务流，需要选择的是在低层或高层之间还是在多层之间进行保护【1 7 1 引。在底层 给于保护能够带来不少的收益【1 8 , 1 9 】，因为故障发生在底层，所以恢复可以立即执 行，如果不是底层保护，那么高层就要等待底层传来的故障报警之后才进行故障 的动作。根据需要恢复的数据块的大小，决定了恢复的难易程度。在更高的一层 故障可能导致多个逻辑故障，有时不可能作到完全的恢复。高层不能够保证足够 的故障恢复，保护策略在底层实现可能更加节省费用。另外，高层恢复的特点有g 能够保护特殊的业务和特殊的服务设备；如果上层提供了监测机制可能会故障恢 复会快些；不需要底层的故障恢复：要求每层都要有独立的恢复机制而且需要在 不同层调整这些恢复动作i 博j 。每一层都应该有各自的保护机制，与其他层是相互 独立的。不幸的是，这种恢复策略会引起不同层同时故障恢复，这样会引起大量 的不必要的故障报警。一种解决办法是给不同层以不同的优先级，另一种就是在 其他层监测到故障之前就在某一层实施完整快速的恢复。 没有被使用的网络资源可以作为保护，以便提高网络的生存性。现今网络有 各种的保护策略，比如为了保护点对点的链路，有1 + 1 、1 ：1 、还有l ：n 保护 2 0 , 2 1 】。 在1 + 1 保护中，业务量同时在两根独立的光纤中传输。目的节点选择其中一根光纤 接受信息。在光纤断裂的情况下，目标节点就切换到另一光纤上接收数据，这种 8 上海交通大学博上学位论文 保护技术相当迅速并且不要求信令。在1 ：1 保护中，在两个端节点之间也有两根 独立的光纤，在这种情况下，只有一根光纤作为工作光纤，在光纤故障发生时， 两个节点都要切换到备用光纤上。在单向通信系统中，光纤的断裂只能被目的节 点发现，所以需要有信令协议以便通知源节点发生故障，这个协议叫做 a p s ( a u t o m a t i cp r o t e c t i o ns w i t c h i n g ) ，这种保护方式不如i + i 保护切换迅速。在双向 通信系统中，不需要有协议的支持因为源和目的节点都能够发现故障，在1 ：1 保 护中，保护光纤没有被使用，所以它可以承载较低等级的业务量，一旦故障发生 的时候，这些业务量可以被挤占掉以激活保护，在l ：n 保护策略中，一条保护光 纤可以保护不同的n 条工作光纤，这种保护只能保护单链路的故障，不能保证多 故障下的业务流的恢复。冗余资源的分配可以使静态的也可以是动态的，静态的 保护是在网络规划时设定好的保护，动态的恢复是指在故障发生的时候找到一条 恢复路径，除去更好的利用网络资源外，动态恢复相对比较慢，因为动态恢复需 要交换大量的信令以便找到一条可选路由。 。卜工作路径 ，路径切换 - 链路切换 一” ( b ) 链路保护 ( c ) 跨接保护 图1 4 保护策略 f i g 1 4p r o t e c t i o ns t r a t e g i e s 有两种保护业务流，一种是通路切换流，另一种是链路切换流。通路切换机 制，通过重路由源宿节点之间中断的业务到另外不同的路径上，从而做到故障保 护。因此每一节点对都需要另外的链路不相关的保护路径，以便在故障情况下能 够保护业务，图1 4 ( a ) 所示。通路切换的一个好处就是能够充分利用资源，尤其 是释放出在工作路径上没有故障的资源，使得它们得到充分利用。象这种通路保 护切换机制中的释放称为残余释放。还有就是通路保护不需要为故障链路定位， 9 第一章绪论 只要探察到哪条工作路径出故障了就保护哪条路径。 另外一种保护切换模式是链路切换，链路切换的信令是由故障链路的宿节点 发起的，并不是整个路径的宿节点所发起。链路切换可以通过链路保护或跨接保 护( s p a np r o t e c t i o n ) 来实现，跨接保护是指把故障光缆上的业务切换到同一连接上 的其他光缆上，如图1 4 ( b ) 。而链路保护是重路由链路上的故障业务到其他的路 径上，如图1 4 ( c ) 。 通路保护要比链路保护复杂，因为通路保护需要为大量的源宿节点对找到一 系列的保护路径。但是，通路保护可以减少冗余容量的需求。还有根据链路切换 和路径切换而改进的保护方案是环保护( r i n gp r o t e c t i o n ) 或叫做p c y c l e 。这里就不 再赘述。 【7 】为通路保护提出了三种不同的方法，它们是，最小波长( m w ) ，链路不相 关通路( d p ) 。基于单链路故障的恢复，分别对工作光路和保护波长进行整个波长 数目的优化。对于通路保护技术中有效利用冗余资源的算法，文献 8 ，2 2 】做了阐述。 可以使用i l p 2 3 】规划方法去优化光缆、光纤、波长代价。对于i l p 规划可以运用 i l ps o l v e r 和模拟退火算法【2 4 j 解决。网络设计的优化问题大致可以分为两步：首 先建立工作光路，然后考虑冗余保护资源的分配。 为保证网络在任何单链路故障具有生存性，工作和保护资源也可以同时被优 化1 25 。，应用i l p 解决的网络资源优化问题旨在优化光纤和o x c 的数目。为了缩 小i l p 的计算空间，只有一定数量的工作保护光路对同时被考虑。 在文献 2 6 】中，d p p 、s p p 、和s l p 是以最小化整个网络的波长数目为目标的， 工作保护的波长都要被计算。在这篇论文中，资源利用率方面s p p 要优于d p p 和s l p ，s l p 与d p p 性能比较接近。 共享保护是能够节省大量资源的保护机f l ；j j t 2 2 , 2 7 】，不仅网络里的链路可以共享， 节点也可以被共享。共享保护可以分为三类，第一类是波长的共享；第二类是带 宽的共享；第三类是物理传输器件诸如o e o 、再生器的共享【2 引。 第一类的波长共享是一种比较传统的共享方式，两个或多个物理不相关的工 作光路可以共享保护波长，这些都是假设在只有单链路故障的情况，不考虑同时 有多个故障的情况；第二类是带宽的共享，类似波长共享，就是资源描述方式更 加细化，用带宽这种资源表述方式来代替波长；第三类是物理器件的共享，这个 是近期提出的一种共享方式，是把共享概念从光纤链路级别扩展到了节点部分。 文献 2 8 】具体研究了怎样共享o e o 设备，并且以最小化网络内o e o 数量为目标 设计了优化算法。 1 0 上海交通大学博 j 学位论文 w d m 网络要优于s o n e t 环形网络重要的一点就是，w d m 网络可以应用各 种不同的保护策略而且比s o n e t 环形网络更加有效，特别是在共享保护方面， w d m 光网络只需要