（通信与信息系统专业论文）宽带网络生存性研究.pdf

宽带网络的生存性研究 一一 一 摘要 f 【随着通信技术的发展和人们对通信需求的增加，网络生存性技术已成为通信网络的关 键支撑技术之寸本文主要研究宽带网络生存性的一些重要问题。 在介绍背景知识和回顾现有技术的基础上，本文首先对分布式自愈技术进行了较为深 入的研究，并提出了三个算法。第一个算法是基于消息传递机制的分布式动态自愈改进算 法。咳算法利用网络节点的先验网络拓扑知识和在恢复过程中积累的网络状态信息，构造 消息评估函数来及早丢弃无用消息，从而达到减少消息的目的。同时在选择端通过简单的 路由选择算法一次性得到符合容量一致性条件恢复路径集合，避免了传统算法的多次消息 广播过程。计算机仿真研究表明，所提算法的恢复率和恢复速度性能优于传统算法矿第二 个算法是基于状态传播机制的分布式动态自愈算法。陔算法能够快速形成k s p 恢复路径集 合，从而保证了算法的恢复效率和可预测性，同时也避免了g r o v e r 提出的s h n 算法的一些 缺陷。计算机仿真研究同样验证了算法的正确性和有效性。此外，该算法可扩展应用于节 点失效和多链路失效的恢复扩第三个算法结合了预定式和反应式自愈算法的优点，既避免 了分布式动态自愈算法中存在的可预测性差和产生消息数多的问题，也避免了预定式自愈 机制适应性差的问题，可望在恢复速度和空闲容量的利用率两者之间得到较好的折中。 接着，本文对可生存网络优化设计问题进行了探索。眨中对基于线路恢复的空闲容量 优化配置问题提出了一种启发式求解方法。该算法从任意的初始可行解开始，通过边交换 操作，逐渐优化结果，最后得到最优解或次优解。该算法有两个特点：( 1 ) 得到的是一个解 集，在此基础上可选择用户最满意的解。( 2 ) 通过调节算法参数一一搜索半径，可在算法的 计算复杂性和解的最优性之间得到较好的折中。计算机仿真研究验证了算法的有效性，并 在所给出的例子中，得到了最优解。随后，本文对于基于路径恢复的联合优化问题也提出 了一种两阶段启发式求解方法。第一阶段利用路由的分散性，对每个需求形成个有效的 可用路由集合，并分配初始工作流量和恢复流量，得到初始解。第二阶段利用最小成本路 径和最大收益路径的概念，迭代优化结果。计算机仿真也得到了较为满意的结果。一寸 此外，本文对网络生存性的估计方法也进行了考察，提出了一种基于分布式动态自愈 技术的网络生存性估计方法。本方法通过可能路由集合的办法，并结合路径恢复的不同优 先级策略来估计网络生存性，其计算复杂性为多项式。同时，对保护路径概念进行了扩展， 提出了一种新的生存性网络体系结构一一保护网络。并通过例子给出了一种简单的构造算 法，显示了这种结构的容量有效性。文中也从研究网络生存性的角度提出了一种新的评价 网络拓扑生存性的指标一一路由分散性。该指标结合了业务需求分布模式，反映了网络需 求节点对之间路由的分散性，从而比传统的网络连结度指标更能体现网络拓扑对生存性的 影响。亨， 最后，跟踪考察了全光网络的生存性技术和多层恢复机制的协调技术。佛对该领域中 一些有待进一步研究的问题提出了一些看法。， 7 - - 、 、， 关键词；生存性：自愈算法j 自愈网，可生存网络设爿i 网络恢复。 s t u d y o n s u r v i v a b i l i t y f o rw i d e b a n dn e t w o r k s a b s t r a c t w i t ht h er a p i dd e v e l o p i n go fc o m m u n i c a t i o nt e c h n o l o g ya n dt h es u s t a i n e di n c r e a s i n go f r e q u i r e m e n tf o ri n f o r m a t i o n ，t h en e t w o r ks u r v i v a b i l i t yt e c h n o l o g yh a sb e c o m ee n do ft h ek e y s u p p o r tt e c h n i q u e sf o rw i d e - b a n dc o m m u n i c a t i o nn e t w o r k s i nt h i sp a p e r , as t u d yo fs e v e r a l i m p o r t a n tp r o b l e m si nt h i sa r e ai sc o n d u c t e d o nt h eb a s i so ft h eb a c k g r o u n di n t r o d u c t i o na n dab r i e fs u r v e yo fe x i s t i n g s e l f - h e a i i n g t e c h n i q u e s ，v a r i o u sd i s t r i b u t e de e l f - h c a l i n gs c h e m a sa r er e v i e w e d ，a n dt h r e en e wa l g o r i t h m sa r e p r o p o s e d t h ef i r s t o n ei s 蛆i m p r o v e dd i s t r i b u t e dd y n a m i cs e l f - h e a l i n g a l g o r i t h m b a s e do n m e s s a g ef l o o d i n gr o u t i n gs c h e m eb yu s i n gt h eap r i o r ik n o w l e d g eo fn e t w o r kt o p o l o g yi nn o d e s a n dt h es t a t mi n f o r m a t i o nc u m u l a t e di nt h er e s t o r a t i o np r o c e s s i n g ，a n e v a l u a t i n gf u n c t i o ni s c o n s t r u c t e df o re v e r ym e s s a g e ，a n dt h eu s o l e s sm e s s a g e sa r et h u sd i s c a r d e da sf a s ta sp o s s i b l e t h r o u g hc o m p u t i n gt h i sf u n c t i o n t h a n , b yi n t r o d u c i n gas i m p l er o u t es e l e c t i n ga l g o r i t h mi n c h o o s e r ，ac a p a c i t y - c o n s i s t e n tr e s t o r a t i o np a t hs e ti no n ef l o o d i n gw a v ec a nb eo b t a i n e d ，t h u s a v o i d i n gt h em u l t i p l ef l o o d i n gw a v e s i nc o n v e n t i o n a la l g o r i t h m st h e c o m p u t e r s i m u l a t i o ns h o w s t h a tt h ep r o p o s e da l g o r i t h mi sb e t t e ri nb o t hr e s t o r a t i o nr a t i oa n dr e s t o r a t i o ns p e e dt h a nt h ee x i s t e d c o n v e n t i o n a lo n e st h es e c o n do n ei sad i s t r i b u t e dd y n a m i cs e l f - h e a l i n ga l g o r i t h mb a s e do ns t a t e p r o p a g a t i o ns c h e m e t h i sa l g o r i t h mi sc a p a b l eo fg e t t i n gak s pr e s t o r a t i o np a t hs e tr e l a t i v e l y q u i c k l y , t h e r e b yg u a r a n t e e st h er e s t o r a t i o nr a t i oa n dt h ep r e d i c t a b i l i t yb e s i d e s ，i ta l s oo v r c o m e s s o m em a i nd i s a d v a n t a g e so fg r o v o r ss h na l g o r i t h m t h ec o m p u t e rs i m u l a t i o nv e r i f i e si t s c o l t e c t n e s sa n de f f e c t i v e n e s s m o r e o v e r , t h i sa l g o r i t h mc a nb ee x t e n d e dt ot h er e s t o r a t i o nf r o m n o d ef a i l u r ea n dm u l t i p l el i n ef a i l u r ee a s e s t h et h i r do n ec o m b i n e sb o t ha d v a n t a g e so fp r e - p l a n n e da n dd y n a m i cs e l f - h e a l i n gs c h e m e s ，n o to n l ya v o i d i n gt h ep o o rp r e d i c t a b i l i t ya n dh u g e v o l u m eo fm e s s a g e si nd i s t r i b u t e dd y n a m i cr e s t o r a t i o ns c h e m e s ，b u ta l s o a v o i d i n gt h ep o o r a d a p t a b i l i t yi np r e p l a n n e dr e s t o r a t i o ns c h e m e s ，t h u sl e a d i n gt oab e t t e rn a d e o f fb e t w e e nt h e r e s t o r a t i o nr a t i oa n dt h es p a r ec a p a c i t yu t i l i z a t i o n t h ep r o b l e mo fs u r v i v a b l en e t w o r kd e s i g ni sa l s oi n v e s t g a t e di nt h i sp a p e r f i r s t , as i m p l e a n de f f e c t i v eh e u r i s t i ca l g o r i t h mi sp r e s e n t e df o rt h ep r o b l e mo fs p a r ec a p a c i t yp l a c e m e n tb a s e d o nl i n e - r e s t o r a t i o n t h i sa l g o r i t h mb e g i mw i t ha na r b i 廿a r yi n i t i a lf e a s i b l es o l u t i o na n dt h e n o p t i m i z e st h es o l u t i o ns t e pb ys t e pt h r o u g ht h ee d g e - e x c h a n g eo p e r a t i o nt oy i e l dt h eo p t i m a l s o l u t i o no rn e a r - o p t i m a ls o l u t i o n i th a st h e a d v a n t a g eo fo b t a h f i n g as e to fs o l u t i o na n d c o m p r o m i s i n g t h ec o m p u t a t i o n c o m p l e x i t ya n d t h eo p t i m a l i t yo f t h es o l u t i o nt h r o u g h a d j u s t i n gt h e s e a r c h i n gr a d i u sp a r a m e t e r c o m p u t e rs i m u l a t i o nr e s u l t sv e r i f yt h ee f f i c i e n c yo ft h i sa l g o r i t h m f o rt h ep r o b l e mo f j o i n to p t i m i z a t i o no f 扛a f f i cf l o wc o n f i g u r a t i o na n ds p a r ec a p a c i t yp l a c e m e n t , a n o t h e rs i m p l ea n de f f e c t i v eh e u i i s t i ca l g o r i t l m ai sp r o p o s e d i ti n v o l v e st w o p h a s e s a tt l l ef i r s t p h a s e ，af e a s i b l er e s t o r a t i o nr o u t es e tf o re v e r yd e m a n d i sc o n s t r u c t e d b yu s i n g t h er o u t ed i v e r s i t y , t h e na ni n i t i a ls o l u t i o nc a nb eo b t a i n e db ya s s i g n i n gt h ei n i t i a lw o r k i n gf l o wa n dr e s t c r a t i o nf l o w m a tt h es e c o n dp h a s e ，t h er e s u l ti s o p t i m i z e di t e r a t i v e l yb ye m p l o y i n gt h ec o n c e p t so fm i n i m a l - c o s t - p a t ha n dm a x i m a l - p o f i t - p a t h ar e l a t i v e l ys a t i s f a c t o r ys i m u l a t i o nr e s u l ti so b t a i n e df o rt h i s s c h e m e m e a n w h i l e ，a ne v a l u a t i o nm e t h o df o rn e t w o r ks u r v i v a b i l i t yb a s e do nt h ed i s t r i b u t e dd r r n a m i e p a t h - r e s t o r a t i o ns c h e m ei sp r e s e n t e d 1 n l i sm e t h o dc o n s t r u c t saf c a s i b l er e s t e r a t i 0 1 1r o u t es e tf o r e v e r yd e m a n da n dt h e nu s e st h i ss e tt oe v a l u a t et h es u r v i v a b i l i t yt h r o u g hv a r i o u sr e s t e r a t i o n p r i o r i t ys t r a t e g i e s t h ec o m p u t a t i o nc o m p l e x i t yo f t h i sm e t h o di so f t h ep o l y n o m i a lt y p ef u r t h e r , t h r o u g he x t e n d i n gt h ep r o t e c t i o np a t hc o n c e p t , w ei n t r o d u c e dan e v vs u r v i v a b l en e t w o r k a r c h i t e c t u r e 。- p r o t e c t i o nn e t w o r k a na s s o c i a t e ds i m p l ec o n s t r u c t i o na l g o i i t h me m p l o y i n gt h i s c o n c e p ti sa l s op r o p o s e db a s e do ng r a p h i ct h e o r y at y p i c a le x a m p l es h o w st h ec a p a c i t ye f f i d e u c y o ft h i sa r s h i t e c t u r e b e s i d e s ，t h er o u t ed i v e r s i t yc o n c e p ti si n t r o d u c e da san e wm e a s u r eo ft h e s u r v i v a b i l i t yo ft h en e t w o r kt o p o l o g y a st h i sm e a s m ec o n s i d e r st h et r a f f i cd i s t r i b u t i o na n d r e f l e c t st h ed i v e r s i t yo f 也ea s s o e i a t e dr o u t e sb e t w e e nad e m a n dn o d e p a i r , i to a nb eu s e dt os e l e c t e f f i c i e n t l ya na p p r o p r i a t es u r v i v a b l en e t w o r kt o p o l o g yf o rad e d i c a t e dt r a f f i cd i s t r i b u t i o n a st h ee n do ft h i s p a p e r , as u r v e y0 1 1t h ea l l 一0 砸c a ln e t w o r ks u r v i v a b i l i t yt e c h n i q u e si s c o n d u c t e da n dt h ec o o p e r a t i o np r o b l e mo fm u l t i p l el a y e r s r e s t o r a t i o nt e c h n i q u e si sd i s c u s s e d s o m eo f t h e i m p o r t a n tp r o s p e c t e da r e a sa s s o c i a t e dt h i sf i e l da r ep o i n t e do u t k e yw o r d s ：s u r v i v a b i l i t y , s e l f - h e a l i n ga l g o r i t h m ，s e r f - h e a l i n gn e t w o r k s ，s u r v i v a b l en e t w o r k d e s i g n ，n e t w o r k r e s t o r a t i o n i v 浙江大学博士学位论文 1 1 引言 第一章网络生存性 通信网络现在已经融入了人们的社会经济生活的各个方面。从最初的电话业务开始， 网络的可得性( a v a i l a b i l i l y y 就是网络设计中关键的一环。也即要求在正常情况下，呼叫阻 塞率足够低，而在网络故障情况下，仍然能确保必要的通信能力。随着通信网络的发展， 这种要求越来越迫切。目前，光纤通信系统得到了广泛应用，系统集成度越来越高，单个 网元失效的影响面越来越大，所以提高网络失效情况下的通信能力，即提高网络生存性已 经成为现在及将来的通信网络急需解决的一个重要课题，也是目前通信网络研究的前沿重 点之一n “。 网络故障的发生可以通过提高系统的可靠性来尽量减少，但要求网络业务百分百的可 得性是不现实的。美国联邦通信委员会曾报告【6 2 侧，在美国，每两天就会发生一次影响超 过3 万个用户的通信事故，而平均修复这些事故的时间长达5 到l o 个小时【l 】。这些事故原 因包括火灾、缆线切断、软件故障、地震、操作失误等等在我国，也不时有类似事故的 发生。 减少和预防网元失效的发生是解决问题的一个方面，但预先考虑到网元失效的不可避 免性，在网络设计之初，就使网络本身具有对抗失效的能力，或预先设定网络恢复策略， 是解决问题的另一个方面，尤其是在光纤网络中，后者显得尤为重要。 在2 0 世纪8 0 年代之前，网络设计者主要关注通信网络的可靠性( r e l i a b i l i t y ) ，其侧重 点在于网络的连接性( c n e 嘶v i _ 劝和网元的可靠性研究，而当网络发生故障时，一般采用 人工修复的办法来恢复网络。从8 0 年代开始，随着通信业务的急剧增长，大量采用了光纤 通信系统，使得单个网元承载的业务越来越多，所以，即使单个网元的失效，也可能影响 大量的客户，使客户的利益受损，某些损害甚至可能引起社会经济的动荡。再者，随着电 信市场的开放，通信业的竞争越来越激烈，网络营运商能否提供可靠的通信，已与其商业 信誉、综合竞争力等密切相关。另一方面，社会经济生活及个人的日常生活越来越依赖于 通信网络，使得用户对业务质量的要求越来越高。人工修复故障的办法已经不能满足要求， 通信客户和营运商都要求网络具有自动恢复失效的能力，即自愈( s e l f - h e a l i n g ) 能力，使失效 产生的影响降到最低。因此，仅仅研究网络的可靠性已不再足够，在这样的背景下，一个 新的研究领域一一网络生存性研究在近些年来得到了快速发展，成为一个十分活跃的前沿 研究领域。 1 2 网络生存性研究的内容 网络生存性研究包括很多方面，主要分成三类：预防、网络设计、业务管理和恢复州。 预防技术主要是指提高系统和设备的可靠性，如硬件系统的容错设计、电源备份、软件系 统的过载测试等，也包括其他一些灾难防范措施。网络设计则利用路由的分散和资源的冗 余来达到缓解失效的影响。业务管理和恢复技术是指通过业务均锭或业务恢复，减小失效 的影响。本文主要侧重后两种技术的探索和研究，具体内容主要包括；可生存网络体系结 网络可得性一般用平均无故障时问来衡量 第一章网络生存性 构、自愈技术( 或机制) 和可生存网络优化设计。这几个方面是紧密相关的，一方面，可生 存网络的体系结构决定了自愈技术和网络优化技术的采用，反过来自愈技术和优化算法则 影响网络的构造成本，进而影响网络体系结构的应用。 1 2 1 网络体系结构 网络体系结构主要指网络的分层结构、层网络的拓扑结构以及各层网络采用的传送技 术等。从研究网络生存性角度来看，一个通信网络可以分成如图1 1 所示三层( 1 。 业务层网络 由业务连接和交换设备 ( 如交换机，路由器) 组成 l 传送层网络 由传送链路及其传送设备组成 l 物理设备层网络 由光缆( 或电缆) 及其终端设备组成 图1 1 通信网络的分层结构 业务层网络是指直接面向用户的网络，该层拓扑结构主要是分级网状结构和无级网状 结构。 传送层网络是指完成信息传送功能的网络层次，它不关心所支持的具体业务的特性， 而只负责把各种速率的业务组合成标准的信息格式从信源传送到信宿。如目前普遍应用的 s d h 传送网和a t m 传送网，采用的传送技术分别是同步传送模式( s t m ) 和异步传送模式 ( a t m ) 。s d h 网主要由数字交叉链接机d c s ( d i g 眦c r o s s - c o n n e c ts y s t e m ) 、分插复用器 a d m ( a d d d r o pm u l t i p l e x e r ) 、终端复用器t m f r e r m i n a lm u l t i p l e x e r ) 等构成，a t m 网主要由 a t mv p 交换机( v p x 9 和v c 交换机( v c x ) 构成。该层拓扑结构有树形、链形、环形、网状 形等几种。 物理设备层网络由具体物理传输线路和传输设备构成，拓扑结构也是多种多样的。 1 2 2 网络恢复技术 网络恢复技术主要是指自动恢复技术，2 0 世纪8 0 年代后期，网络设计者提出了网络 故障自动恢复技术，或称自愈技术，即通过提供冗余的网络资源，并且利用这些资源构成 健壮的网络保护和网络恢复机制，使得在线通信业务绕过网络故障区域，不造成业务中断， 用户感觉不到影响或影响很小。根据不同的网络层次、层网络的拓扑和传送技术，可以采 用不同的保护和恢复机制。 网络恢复通常划分为务层恢复和传送层恢复两大类。业务层恢复涉及单个呼p 4 ( 或连接) 的重新选路以绕过失效，如动态无级选路( d n h r ) 和状态依赖性选路等。但由于网元的失效 可能影响数目巨大的业务连接，因此业务层恢复需要处理众多的连接恢复，同时由于业务 层状态变换很快，故快速恢复与优化恢复难以实现，因而通常仅适用于单个连接质量劣化 2 浙江大学博士学位论文 的情况。传送层恢复则由于传送层网络把不同的业务连接经过适配在较少的传送层路径上 传输，恢复时涉及较少的操作，加上其网络状态相对稳定，故容易进行优化恢复，且恢复 速度较快。因此，网络恢复通常在传送层上实现。由于目前传送网络主要是基于s d h ( 或 s o n e t ) 和a t m 技术，所以本文主要着重研究s d h ( 或s o n e t ) 和a t m 网络的自愈技术。 同时，由于目前i p 业务的快速增长和全光网络的出现，对传统的传送网络体系结构提出了 新的挑战i z - t ”，所以，本文对全光网络生存性研究的最新进展也进行了跟踪考察。 1 2 3 可生存网络的优化设计 可生存性网络设计，除考虑在正常情况下满足业务性能需求( 包括数量要求和质量要求) 外，还须考虑失效状态下的性能需求。优化设计的目标是，在满足这些需求下整个网络配 置成本最小。可生存网络设计决定于可生存网络体系结构和网络恢复技术的采用，鉴于拓 扑设计、可生存网络体系结构选择、设备选型等问题已经有很多文献进行了研究 h 1 【1 4 1 b 1 【1 5 1 【1 7 5 1 “i ，故本文将主要研究网状自愈网中空闲容量优化配置以及工作流量和空闲容 量联合优化问题。在网状自愈网中，采用不同的恢复技术，其优化问题形式及求解方法有 很大的不同，本文将主要考虑两种恢复技术，即：预定式恢复技术和反应式恢复技术( 也称 动态恢复技术) ，前者在失效发生之前，预先确定恢复路径集合；而后者则在失效发生后， 基于“尽力而为”的恢复策略，根据当时的网络状态，动态构造恢复路径集合。 1 3 背景知识 1 3 1 传送技术变迁与网络生存性 对网络生存性的研究是随着传送网技术的发展而发展的。图l 一2 t l 】示出了传送技术的演 化变迁情况。 最早的点对点通信的电话网，线路容量粒度( g r a l l l a d t y ) 为e 1 ( 2 m b s ) 或t i ( 1 5 m b s ) ， 交换单位是6 4 k b s ，准同步数字系列( p d 功，线路容量粒度为1 4 0 m b s ，交插连接单位是 2 m b s ，现在广泛采用的同步数字系列( s d h ) 的交插连接单位是1 5 0 m b s ，线路速率达 1 0 g b s 。而目前在长途通信网中已经采用波分复用技术( w d i v 0 ，交插连接单位是1 0 g b s ， 线路速率则高达o5 t b s 。可以看出每次技术更新，容量粒度和线路速率都以5 0 到1 0 0 倍 的速度增长。正是这个发展过程，使得今天的通信网络变成了这些技术的一个混合体，比 如p d h 信号包含在s d h 的虚容器中，而s d h 信号又是在w d m 链路上传输。图中虽没有 示出a t m ，但它是一种基于分组交换技术的能够提高网络通信效率的重要传送技术，已经 得到广泛应用。这样，目前的传送网是复杂的多层次网络，这无疑增加了生存性研究的难 度。但随着新的传送网络体系结构的提出，如：i p o v e a w d m 、a t mo v e r w d m 、s d ho v e r w d m 及全光网络，网络传送技术将得到精简，网络层次将减少，最终有望简化目前复杂 的生存性技术。 从上之分析可以得到两点结论： 1 传送技术的发展，特别是传送速率的提高，使得网络生存性越来越重要。 2 传送技术是一个逐渐演化的过程，结果是目前的传送网络成为各种技术的混合体， 基于不嗣的传送技术，有不同的网络恢复机制，对此本文也将进行跟踪考察。 第一章网络生存性 图1 - 2 传送技术的演变：传送单元和线路容量 1 3 2 网络物理拓扑与网络生存性 网络拓扑是指网络的形状，图l o 示出了通常使用的五种网络基本拓扑。 口_ _ ) _ 口 ( a ) ，扣、 乓归 ( e ) 图i - 35 种基本网络拓扑( a ) 线型( b ) 星型( c ) 树型( d ) 环型( e ) 网型 在实际应用中，各种拓扑都得到不同程度的应用m 】，而且往往是各种拓扑的混合体， 其中应用较多的是环形网和网状网。 物理拓扑是指物理设备层网络的拓扑，它与网络的生存性有密切的关系。传统的研究 主要集中在网络连接性( c c 函v 蛔) 和网络的脆弱性( v u l n c r a b i l i t y ) d 2 ”】【17 】n ”。网络的连接 性主要考虑网络连接的最薄弱的环节，而不计入业务需求。如图1 - 4 ( a ) ( b ) 两个网络拓扑， 显然( a ) 的连接性不如( b ) 的连接性。但是假如业务需求主要是集中在组 l ，2 ，3 ，4 ) 和 5 ， 6 ，7 ，8 ) 内部，而组间通信业务量较少，显然，( a ) 的生存性比( b ) 的生存性好。因为组内每 两点之间，在( a ) 中存在3 条线路不交叉的路由，而在( b ) 内只存在2 条。由上例可见，路由 的分散性似更能反映网络拓扑的生存性。t h w u 和d s a h a 等人在h 】【”2 5 1 构造可生存网 络拓扑时也都强调了路由分散的重要性。 这样，为了更好地反映网络拓扑的生存性，这里提出一个新的衡量指标，称之为网络 业务路由分散性，作为选择网络拓扑的一个依据。 4 浙江大学博士学位论文 ( a )( b ) 图1 4 网络拓扑和生存性 若节点f 和j 之间有业务需求量磊，并且它们之间存在吩条线路( 或节点) 不交叉的路由， 则业务路由分散性指标可定义为 ，卫 d i v = ( 。d o ) ( 1 1 ) d = l 其中，d 为业务需求总数。 如图l - 4 中，若组内节点和组间节点之间的业务需求量分别为2 和l ，则 ( 1 的业务路由分散性指标为：( 2 x 3 1 2 + 1 1 6 ( d t 2 s = 3 1 的业务路由分散性指标为：( 2 2 x 1 2 + 1 1 6 2 ) 2 8 = 2 8 6 若组内节点和组间节点之间的业务需求量都是为l ，则由式( 1 - 1 ) 可知 和电 的业务 路由分散性指标分别为1 9 和2 1 。 这样，我们在选择网络拓扑时就能以不同的业务需求模式作为选择依据，以较好地满 足网络生存性需求。 1 3 3 网络失效原因及生存性计划 引起网络失效的原因很多，主要包括： 自然灾害：这种灾害往往造成大范围的网络设施毁坏，抵御这种灾害只有采用分 布式控制、地理位置分散、增加备份设备、启用无线传输系统、预先计划补救措 施等方法。 人为故障：减少这种危害需从法律、管理及制度上入手。 系统故障：包括软件故障、硬件故障以及体系结构固有的缺陷，重视可靠性设计、 完善维修保养及测试计划是减少此类故障的重要措施，但采用生存性体系结构才 是治本。 在这些故障中，最常碰到的就是单个网元的失效。与自愈算法的大量研究相比，对网 络失效的研究仍未充分进行，缺乏对个案的深入分析和对各类失效的特征提取，同时也缺 少各类失效对各种业务影响程度的总结。 为了提高网络的生存性，应有一个完整的计划【4 】，大致可分成下述四步； l 主要是防止失效的产生，努力减少人为问题和环境问题的产生。主要措施包括： 加强保安，加深缆线埋设，有效的防火措施和环境控制措施，加快系统更新。 2 加快网元失效检测速度。 3 通过可生存网络设计，增强网络的自愈能力。这个阶段重点强调采用生存性体系 第一章网络生存性 结构，优化生存性策略，以及提供生存性网络设计工具。 4 人工恢复阶段，在网络本身无法自愈的情况下，强调通过周密的计划和人员培训 来达到快速的人工恢复。 1 3 4 生存性需求分析 业务恢复时间和恢复率是生存性的两个重要度量指标，不同的业务和不同的用户对生 存性的要求是不同的。表l 一1 示出了各种传统业务对恢复时间的要求1 2 1 1 1 4 6 1 。新出现的宽带 业务和实时业务( 如：v o d ，h d t v ，远程可视会议等) 对恢复时间的要求还没有研究结果 公开发表。 从表中可见，业务中断时间有两个重要的门限值。第一个是5 0 毫秒，恢复时间在此值 之内，可以满足绝大多数业务的质量要求，除瞬时冲击外业务不中断，因而可以认为5 0 毫 秒的保护恢复时间对于多数电话交换网的话带业务和中低速数据业务是透明的。第二个门 限是2 秒，只要业务中断时间短于2 秒，则中继传输和信令网的稳定性可以保证，电话用 户只经历短暂的通话间歇，几乎所有数据会话协议仍能维持，图象业务则会发生丢帧和图 象冻结现象( 几秒) ，但多数人能勉强忍受。当故障状态持续( 25 + o 5 ) 秒，则数字交换机将发 出告警信号，拆除有关话音通路连接并停止计费，这类故障显然已无法忍受。因此，2 秒 门限已作为网络恢复的目标值，称为连接丢失门限( c d t ：c o n n e c t i o n d r o p p i n g t h r e s h o l m 。 表1 1 恢复时间对各种用户业务的影响 恢复时间对各种业务用户的影响 0 到5 0 毫秒对业务有瞬间影响，重新帧同步 5 0 毫秒到2 0 0 毫秒话音业务连接中断概率小于5 信元业务重路由 2 0 0 毫秒到2 秒根据通道情况话音业务连接可能有不同程度的丢失 2 秒到1 0 秒所有的交换业务连接中断 专线业务连接中断 x 2 5 分组业务连接可能中断 数据会话业务可能超时 i 0 秒到5 分x 2 5 分组业务连接中断 数据会话业务超时丢失 5 分到3 0 分网络阻塞，对社会生活i 每业活动造成一定的影响 大于3 0 分对社会生活，商业活动造成较大影响 1 3 5 生存性及其计算 网络生存性是指在给定网络故障或随机网络故障的条件下，所关心的网络某项业务指 标的留存性( 值) 0 2 。5 ”。业务指标可以是吞吐量、保持连接的电路数或通道数、与中心节点 保持连接的节点数等。给定一个失效事件，可以求出给定指标的留存值，不同的失效事件， 该值也不同，所以它是失效空间上的一个函数，如果给出各失效事件发生概率，就可以得 到各种统计值( 如：概率均值，最坏值等) 伫2 】1 ，如果考虑自愈机制和设备修复过程，则可 以表示为一个时间函数，如图1 - 5 所示。图中t o 是失效发生时刻，在此之前，归一化的 业务指标为1 ，失效发生之后，业务指标急剧下降了s i l ，即降至s ，这时恢复机制开始启 6 浙江大学博士学位论文 动，业务指标开始上升，经过时间t a e pt a 时刻) ，指标值回升s 。，即达到s i + s r ，这时由于 空闲资源的缺乏或恢复机制本身的限制，指标值不能继续回升，这样必须通过设备修复程 序或其它更有效的恢复机制才能恢复指标，假定到达t 2 时刻，设备修复好或通过其它更有 效的恢复机制，业务指标恢复到失效之前的水平1 ，恢复过程结束。从失效开始到完全恢 复的时间就是图中的t r 。这些值表明了网络生存性的各个方面的特性。 业 务 指 标1 x s ，s ， 7 女 ，s l 一 t r | 二。 。| 7 t o t lt 2 时间 s 。是失效发生后，恢复机制启动前，业务指标x 的留存值。 s 。是失效发生后，恢复机制启动前，业务指标x 的损失值。 s r是恢复机制启动后，在时刻t t 时，业务指标x 的恢复值。 t o失效发生时间。 业务指标x 的恢复到s + s r 所花的时间。 t r完全恢复业务指标x 所花的时间。 图l 一5 生存性时间特性曲线i 】 网络生存性主要分连接生存性和业务生存性两种【2 ”。连接生存性主要考虑在给定的 网络失效状态下，两点之间是否存在连通的路由【1 “”。而业务生存性则不仅关心两点之间 是否存在连通的路由，而且关心这些路由上是否有足够的资源来承载一定的业务量 2 4 - 2 5 1 。 显然，在光纤通信网络中，我们更关心业务生存性。 在文献【2 2 】中，给出生存性的两种计算模型：随机失效模型( r o f ：r a n d o mo c e u r r e n c eo f f a i l u r es u r v i v a b i l i t ym o d e l ) 和给定失效模型( g o f ：g i v e no c c u r r e n c eo ff a i l u r es u r v i v a b i l i t y m o d e l ) t 。 随机失效模型：这种模型假定各个网元的失效是以一定的概率随机发生的。不同的故 障类型有不同发生概率，因此，必须先确定故障类型，针对每种故障类型，分别研究网络 的生存性。计算过程如下： l 获得给定故障类型的发生概率数据； 2 定义要研究的网络业务指标； 3 列出所有的故障组合可能事件 e ) ； 4 对每种可能的故障事件，确定生存性s 。； 5 对每种可能的故障事件，给出发生概率； 7 第一章网络生存性 6 计算需要的网络生存性。 给定失效模型：假定故障已经发生，且网络恢复机制已被启动，因此，不需要知道造 成失效的原因。可以说，这时一种条件生存性，用户关心的是，在给定失效情形和所采用 网络保护或恢复机制下，某种业务指标的存活值。其计算过程如下： 1 定义一种生存性尺度： 2 选择一种失效情形( 如单线路失效，单节点失效) 3 获得所有失效事件的可能组合； 4 计算网络生存性尺度。 这两种计算模型有不同的应用，前者主要用于评价整个网络抗灾难( 故障) 的能力，与 网络的可靠性的概念比较接近，在网络设计中起指导作用，但是计算复杂，特别是故障发 生概率不容易得到。而后者主要用于可生存网络设计，因为它的计算比较简单，并直接与 用户的生存性需求相联系，所以在可生存网络设计时，通常以它作为生存性需求指标。 1 3 6 网络设备和自愈网 在s d h 传送网中，与网络自愈关系最密切的是三类设备m 】：终端复用器t i m ，分插复 用器a d m 和数字交叉链接设备d c s 。下面简要介绍它们的功能特性及其在自愈网中的应 用。 电源公务告警t m n 接口 电源公务告警t m n 接1 2 1 5263 44 51 4 0 1 5 5 m b i f f s t m 功能图 1 5263 44 51 4 0 1 5 5 m b i t s f b ) a d m 功能图 1l ：m 解夏用i 5 交叉连接矩阵 n 个输入 ； d q i1 1 个输出 叫1 。怔曹田i 【 i 【i 。1 售田l f c l d c s 功能图 图1 - 6 三种s d h 传输设备功能示意【5 】 终端复用器t m ：它的主要功能( 以s t m 1 为例) 是将低速的支路信号和1 5 5 m b i f f s 的电 信号纳入s t m 1 的帧结构，并经过光，电转换为s t m - 1 的光信号，其逆过程正好相反。如 8 浙江大学博士学位论