（计算机科学与技术专业论文）基于离散概率模型的二端网络可靠性分析.pdf

北京邮电大学博十论文 基于离散概率模型的二端网络可靠性分析 摘要 在经济生活日益依赖于通信网的今天，网络故障不仅会带来巨大的数 据损失，甚至会导致灾难性后果。利用网络可靠性分析，工程人员可以增 强网络可靠性，减少故障时损失。尽管网络可靠性分析已经取得了大量成 果，但如下方面还需要开展进一步研究： 第一，网络结点不可靠时的可靠性分析。传统的网络可靠性分析通常 假设结点可靠，这在一些新的网络研究领域是不成立的，譬如自组织网络、 灾难环境网络。而且，当网络结点众多时，可靠性分析中的计算量将变得 非常庞大。 第二，网络部件故障非统计独立时的可靠性分析。传统的网络可靠性 分析通常假设部件故障统计独立，这会给某些网络的可靠度评估带来很大 的偏差，譬如极端环境下的网络。另外，当非统计独立故障较多且网络规 模较大时，可靠性分析将变得非常困难。 第三，网络部件重要性分析。传统的网络可靠性分析主要讨论可靠度 计算，不能从部件故障角度全面了解网络可靠性，缺乏高效的计算方法。 第四，网络运行时可靠性分析。传统的网络可靠性分析主要研究可靠 性设计指标，其成果不能很好地反映运行时的网络可靠性。 通信网有着庞大的规模和动态复杂性，经典的故障分布函数很难描述 网络的故障特性。为降低复杂性，解决一般性问题，本文采用了主流的网 络可靠性模型时间独立的离散概率模型。另外，本文只讨论了二端网 络的可靠性问题，但其成果可以推广到k 端网络和全端网络。 针对网络可靠性分析中存在的上述问题，本文从四个方面开展了研究 工作： ( 1 ) 研究了结点不可靠网络的可靠性分析，提出了基于标记因子划分 的网络可靠度评估算法一m f p ( m a r k e d f a c t o rp a r t i t i o n ) 和基于特征识别 的s t r e e t 网络可靠度评估算法s n r ( s t f e e tn e 帆o r kr e l i a b i l i t v ) ，解决 了部分规模较大而结点不可靠的网络可靠度评估问题。最后，针对无线传 感网的众多不可靠结点，提出了能有效评估可靠度的算法一e f ( e n h a n c e d f a c t o r i n g ) 。 北京邮电人学博士论文 1 ) m f p 改进了基于有序二叉判定图( o b d d ，o r d e r e db i n a 叫d e c i s i o n d i a g r a m ) 的可靠性分析方法。在创建o b d d 过程中，利用边替代( e r ，e d g e r e p l a c e m e n t ) 运算处理网络中的不可靠结点。同时，从两个方面减少了计 算量：分解网络时，根据子网的标记因子划分来识别同构子网，避免分解 同构子网带来的重复计算；利用o b d d 来存储网络结点和边的状态，减少 了冗余状态。 2 ) s n r 是专门针对s t r e e t 网络的方法，其基本原理与m f p 相同。s n r 利用源端位置信息作为子网特征，识别s t r e e t 网络分解过程中出现的同构 子网，从而减少重复计算。 3 ) 增强因子分解算法在网络分解过程中采用h a s h 表来存储同构子网 的可靠度，提高了计算效率。 ( 2 ) 研究了一类常见的非统计独立故障共因失效，提出了分析共 因失效网络可靠性的算法c n r ( c o m m o n c a u s e f a i l u r en e 呐o r k r e l i a b i l i t v ) 和无线传感网可靠性的算法- w r ( w i r e l e s s s e n s o r n e 研o r k s r e l i a b i l i t v ) 。解决了部分共因事件较多且规模较大网络的可靠度评估问题， 讨论了有共因失效的无线传感网可靠度评估问题。 1 ) c n r 改进了基于o b d d 的共因失效可靠性分析方法。为降低分析 复杂性，c n r 算法未考虑结点不可靠的情况。由于c n r 方法只需要递归 创建一个o b d d 结构，在共因事件较多、网络规模较大时，这种方法可节 省大量计算开销。关于如何创建共因失效网络的o b d d ，本文又提出了两 种方法：基于布尔运算的方法和基于共因变量集的方法。第一种方式比较 灵活，第二种方式有较高的存储效率。 2 ) w r 算法充分考虑了无线传感网中的大量共因事件和不可靠结点， 借用了c n r 创建共因失效网络o b d d 的思路，利用结点扩张法来处理无 线传感网中的不可靠结点。 ( 3 ) 研究了网络部件重要性分析。讨论利用b i r n b a u m 测度、关键重 要度和风险增长区间等部件重要性指标来描述网络可靠性，提出了基于 b i m b a u m 测度的链路重要性评估算法一b i l ( b i m b a u m i m p o r t a n c eo f l i n k ) 和基于风险增长区间的网络可靠性评估算法一r i ( r i s k i n c r e m e n t ) 。 b i l 充分利用o b d d 结构来高效计算b i m b a u m 测度、关键重要度和风险 增长，发现网络薄弱环节，确定引发故障的最可能部件。而r i 能够对部件 故障时的网络稳定度进行分析，为网路抗毁性提供了又一个参考指标。另 i l 北京邮电人学博士论文中文摘要 外，针对无线传感网中不可靠结点，提出了基于风险增长的结点重要性评 估算法_ w n i ( w i r e l e s sn o d ei m p o r t a n c e ) 。 ( 4 ) 针对网络运行时可靠性分析，提出了两个可靠性测度：基于故障 检测的指标容错m p l s 网络的可靠性测度；基于可用带宽测量的指标 自愈i p 网络可靠性测度。最后，为分析容错m p l s 网络运行时可靠性， 设计并实现了一个开销较低速度较快的故障检测方法一自适应的l s p 故 障检测机制。 关键词：网络可靠性，二端网络，离散概率模型，有序二叉判定图 l i i 北京邮电大学博士论文 r e l i a b i l i t ya n a i s i so ft w ot e r m i n a l sn e t w o r k b a s e do nd i s c r e t ep r o b a b i l i t ym o d e l a b s t r a c t a st h ee c o n o m ys o c i e t yd e p e n d so nc o m m u n i c a t l o nn e t w o r k sm o r ea n dm o r e ， t h en e t 、o r kf a i l u r e sw i l lb r i n ga b o u tag r e a td a t al o s so re v e nd i s a s t e r w i t ht h e n e 帆o r kr e l i a b i l i t ya n a l y s i s ，t h ee n g i n e e r sc a ne n h a n c et h en e 帆o r kr e l i a b i l i t y a n dr e d u c et h el o s sw h e nt h ef a i l u r e st a k ep l a c e u t h o u g ht h en e 咐o r k r e l i a b i l i t ya n a l y s i sh a sb e e nd i s c u s s e dw i d e l y ，s o m ew o r k sn e e dt ob ef u r t h e r e d ： f i f s t l y ， t h e r e l i a b i l i t ya n a l y s i s o fn e m o r kw i t h i m p e 血c t n o d e s t i l e t r a d i t i o n a la s s u m p t i o no fp e r f e c tn o d e si si n a p p r o p r i a t ef b rn e wf i e l d ss u c h 硒 a dh o cn e t w o r k sa n ds o m en e t w o r k si nd i s a s t e re n v i r o n m e n t f u n h e m o r e ，t h e n u m b e ro fr e l i a b i l i t yc o m p u t a t i o n sw i l ll a 唱e l ye x p a n dw h e nt h e r ea r em a n y i m p e r f e c tn o d e s s e c o n d l y ， t h ef e l i a i b i l i t y a n a l y s i s o fn e t w o r kw i t hd e p e n d e n tc o m p o n e t s f a i l u r e s b e c a u s et h e c o m p o n e t s f a i l u r e sa r e u s u a l l y a s s u m e dt ob e s i n d e p e n d e n t ( s t a t i s t i c l y - i n d e p e n d e n t ) ，t h et r a d i t i a n lm e t h o d so v e r e s t i m a t et h e n e 咖r kr e l i a l b i l i t y f u r t h e m o r e ，t h i sa s s u m p t i o ni si n a p p r o p r i a t ef b rn c t w o r k s i ne x t r e m ee n v i r o n m e n t w h e nt h en e 帆o r ks c a l ea n dn u m b e ro fd e p e n d e n t f a i l u r e sa r el a r g e ，t h en e 俩o r kr e l i a b i l i t ya n a l y s i sw i l lb e c o m ed i f f i c u l t t h i r d l y ，t h ei n l p o r t a n c ea n a l y s i so fn e t w o r kc o m p o n e n t s t h et r a n d i t i o n a l m e t h o d sm a i n l yf o c u so nt h er e l i a b i l i t yv a l u e s ，a n dl i t t l er e l i a b i l i t yi n f b r i n a t i o n c a nb ek n o w nf 而mt h ep o i n to fc o m p o n e n t sf a i l u r e s t h e r en e e d ss o m e e f 托c t i v em e t h o d sf o rt h ei m p o n a n c e a n a l y s i so fn e t w o r kc o m p o n e n t s f 0 u r t h l v ，t h em n t i m er e l i a b i l i t va n a l y s i sa b o u tn e t w o r k s t h et r a n d i t i 伽a l m e t h o d sm a i n l yd i s c u s st h e r e l i a b i l i t y m e t r i c sf o rd e s i g n ，w h i c hc a nn o t i n d i c a t et h er e l i a b i l i t yw h e nt h en e t w o r k sa r eo p e r a t i n g b e c a u s eo ft h el a r g es c a l ea n dd y n a m i cc o m p l e x i t y ，i ti sd i f f i c u l tt od e s c r i b e t h en e t w o r kf a i l u r e sw i t ht h o s ec l a s s i cf a i l u r ed i s t r i b u t i o nf u n c t i o n s t o s i m p l i f yt h ec o m p l e x i t ya n dr e s o l v et h eg e n e r a lp r o b l e m ，t h i st h e s i sm a k e s u s e o fc u r r e n t p r e v a l e n t m e t h o d d i s c r e t e p r o b a b i l i t y m o d e l sw i t ht i m e i n d e p e n d e n c e 吣t h o u g ho l n yt h et w ot e r m i n a l sn e t w o r k sa r ed i s c u s s e d ，t h e 北京邮电大学博士论文 m e t h o d sc a nb ea p p l i e di n t ot h er e s e a r c h e so fk - t e m i n a ln e t w o r ka n da u t e r m i n a ln e 觚o r l 【 t h i st h e s i sf b c u s e so nt h en e t w o r kr e l i a b i l i t va n a l v s i sa n dc a r r i e so u tt h e f o l l o w i n gr e s e a r c h e s ： ( 1 ) t h er e l i a b i l i t ya n a l y s i sa b o u tn e t w o r k sw i t hi m p e r f e c tn o d e s t w o e n h a n c e do b d d ( 0 r d e r e db i n a r yd e c i s i o nd i a g r a m ) m e t h o da r ep r e s e n t e d ， w i t ht h en a m e so fm f p ( m a r k e df a c t o rp a r t i t i o n ) a n ds n r ( s t r e e t 卜k t w o r k r e l i a b i l i t y ) t h em f pe v a l u a t e st h en e t w o r kr e l i a b i l i t vb a s e do nt h em a r k e d f a c t o rp a r t i t i o n ，a n dt h es n re v a l u a t e st h en e t w o r kr e l i a b i l i t vb a s e do n c h a r a c t e ri n d e n t i f i c a t i o n t h e s em e t h o d sc a ne v a l u a t et h e1 e l i a b i l i t i e so fs o m e l a r g en e 柳o r k sw i t hi m p e e c tn o d e s o t h e 刑i s e ，w i t hc o n s i d e r a t i o no fm a n y i m p e r f e c tn o d e s ，t h ee f ( e n h a n c e df a c t o r i n g ) i sp r e s e n t e dt oe v a l u a t et h e r e l i a b i l i t yo fw s n 似i r e l e s ss e n s o rn e 呐o r k s l 1 ) m f pe n h a n c e st h er e l i a b i l i t ya n a l y s i sm e t h o db a s e do no b d d d u r i n gt h e o b d dc o n s t r u c t i o n ，t h ee r ( e d g er e p l a c e m e n t ) o p e r a t i o n sa r ee x e c u t e dt o r e p r e s e n tt h ei m p e r f e c tn o d e sw i t ho b d dn o d e s t w op o i n t si m p r o v et h e c o m p u t a t i o ne f f i c i e n c yf o ft h el a r g es c a l en e t 、7 l ，o r l 【s ：d u r i n gt h ed e c o m p o s i t i o n ， t h em a r k e df a c t o rp a r t i t i o n sa r eu s e dt oi d e n t i f yt h ei s m o p h i cs u b n e t w o r k sa n d t h er e p e a t e dc o m p u t a t i o n sa r ed e c 陀a s e df r o mt h e s en e t w o r k s ；t h es t a t e so f n o d e sa n de d g e sa r es t o r e di no 王；【) da n dt h er e d u n d a n ts t a t e sa r ed e c r e a s e d 2 ) 7 i h ec o m p u t a t i o nc o u r s eo fs n ri ss i m i l a rw i t hm f p b u ti s i se s p e c i a lf o r t h es t r e e tn e 觚o r k s t h ed i f f e r e n c e i st h ei d e n t i f i c a t i o no fi s m o p h i c s u b - n e m o r k s ，s n rm a k e su s eo ft h es o u r c en o d ep o s i t i o nt oc h a r a c t e r i z ee a c h s u b - n e 啊o r k sa n di n d e n t i f yt h o s es u b n e t w o r k sw i t hs a m es t r u c t u r e s 3 ) e fe n h a n c e st h ef a c t o r i n ga n di m p r o v e se f f i c i e n c yw i t hh a s ht a b l e ，w h i c h s t o r e st h er e l i a b i l i t i e so fi s m o p h i cs u b n e t v l ，o r k s ( 2 ) 7 1 1 l er e l i a b i l i t ya n a l y s i sa b o u tn e t w o r k sw i t hc c f ( c o m m o nc a u s e f a i l u r e ) b a s e do nt h em o d e lo fc o m m o nc a u s e f a i l u r e ， t h ec n r ( c o m m o n c a u s e f a i l u r e n e t w o r k r e l i a b i l i t v )a n dw r ( w i r e l e s s - s e n s o r n e 帆o r k sr e l i a b i l i t y ) a r ep r e s e n t e d t h ec n ri sf o rag e n e r a l n e 帆o r k sw i t ha c f ，a n di tc a na n a l y z et h el a r g en e t w o r k sw i t hm a n vc o m m o n c a u s ee v e n t sf c c e ) 1 ) 1 1 l l ec n r i sa ne n h a n c e do b d da l g o r i t h m ，a n dt h en o d e sa r ea s s u m e dt o v 北京邮电大学博上论文 b ep e r f e c tf o rs i m p “f i c a t i o n d u r i n gt h er e l i a b i l i t y c o m p u t a t i o n s ，o n l yo n e r e c u r s i v eo b d dc o n s t m c t i o ni se x e c u t e d w h e nt h en e t w o r ks c a l ea n dc c e n u m b e ra r e l a r g e ，t h i sk i n do fo b d dc o n s t m c t i o ng r e a t e l yd e c r e a s e st h e r u n n i n gt i m e a b o u tt h eo b d dc o n s t m c t i o n sf o rc c fn e t w o r k s ，t w om e t h o d s a r ep r i ) p o s e d ：t h ef i r s to n ei sb a s e do nb o o l e a no p e r a t i o n ，a n di ti sm o r en e x i b l e ； t h es e c o n do n ei sb a s e do nc o m m o nc a u s ev a r i a b l es e t s ，a n di ti sm o r es t o r a g e e f f i c i e n t 2 ) w i t ht h ec o n s i d e r a t i o n so fl a r g en u i n b e ro fc c e sa n di m p e r f e c tn o d e s ， w rc a ne v a l u a t et h er e l i a b i l i t yo fw s n t h eb a s i cp r i n c i p l eo fw ri ss a m i l i a r w i t hc n r ，b u ti te f 托c t i v e l yr e s o l v e st h ei m p e r f e c tn o d e sp r o b l e mw i t hn o d e e x p a n s i o n ( 3 ) t h ei m p o r t a n c ea n a l y s i s o fn e t w o r kc o m p o n e n t s s o m ei m p o n a n c e m e t r i c sa r ed i c u s s e d ：b i r n b a u mm e a s u r e m e n t ，c r i t i c a li m p o r t a n c e ，r i s k i n c r e m e n t i n t e a l ， e t c t w o i m p o n a n c ea n a n l y s i s m e t h o d sf o r 9 9 n e r a l n e t w o r l 【sa r ep r e s e n t e d ：b i l ( b i m b a u mi m p o n a n c eo fl i n k ) a n dr i ( r i s k i n c r e m e n t ) 1 1 l eb i oc o m p u t e st h eb i m b a u mi m p o r t a n c eo fl i n k s ，a n di n d i c a t e s t h ew e a k n e s sa n dt h ef a u l tc o m p o n e n tw i t ht h em o s td r o b a b i l i t v a sa n e v a l u a t i o nm e t h o df o rt h er i s ko fc o m p o n e n tf a i l u r e ，t h er i oc a na l s oa n a l v z e t h en e 觚o r ks t a b i l i t y ，w h i c hc a nb eu s e da si n v u l n e r a b i l i t ym e t r i c o t h e 州i s e ， b a s e do nm er i s ki n c r e m e n t ，t h e 、n i ( w i r e l e s sn o d ei m p o r t a n c e ) i sp r e s e n t e d t oe v a l u a t et h en o d ei m p o r t a n c eo fw s n ( 4 ) t h er e l i a b i l i t ya n a l y s i sb a s e do nn e t w o r km e a s u r e m e n t t h er e l i a b i l i t y m e t r i c sa r ep r e s e n t e df o rf a u l t t o l e r a n tm p l sn e t 、) l ，o r ka n dr e s i l i e n ti pn e 艄r o r k t h eo n ef o rm p l sn e t w o r ki sb a s e do nt h en u m b e ro ff a i l u r e a n dt h eo n ef o r i pn e t w o r ki sb a s e do na v a i l a b l eb a n d w i d t h f o rt h er u n t i m er e l i a b i l i t va n a l v s i s o fm p l sn e t w o r k ，a na d a p t i v el o o p b a c km e c h a n i s mf o rl s pf a i l u r ed e t e c t i o ni s p r e s e n t e d i ti saf a s ta n dl o wc o s t sm e t h o df o rm p l sf a i l u r ed e t e c t i o n k e yw o i m s ：n e t 、) l ，o r kr e l i a b i l i t y ，帆ot e r m i n a l sn e 帆o r k ，d i s c r e t ep r o b a b i l i t y m o d e l ，o r d e r e db i n a 巧d e c i s i o nd i a g r a m 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 申请学位 本人签名 处，本人承担一切相关责任。 日期： z 哩：! ：鲤 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以 公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇 编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文注释：本学位论 文不属于保密范 本人签名： 导师签名： 日期：兰咝：三：望 日期： 互! ! 翌：! 北京邮电大学博士论文 第1 章绪论 第1 章绪论 本章包含三部分内容：首先，对课题的背景进行了总结，引出了本课 题所要研究的问题；然后，介绍了本论文的研究内容；最后，介绍了论文的 结构和安排。 1 1 本课题的研究背景 今天的通信网，尤其是主干网络，承担着海量数据的传输，因部件故障导致的通 信中断将给用户带来巨大损失。为减少故障风险以及故障发生时带来的损失，工程人 员在设计通信网时必须着重分析网络可靠性，通过反复评估可靠性来优化网络结构1 1 一。 这种可靠性需求在承担关键任务的专用网中表现得尤为突出：如果在设计阶段未充分 考虑各种因素对网络可靠性的威胁，那么故障发生时所导致的通信中断将带来灾难性 的后剿硒j 。譬如，分析气象监测网络可靠性时，需要充分考虑各种灾害天气对通信设 备的破坏，通过采取保护措施来增强网络的抗毁能力；分析战术网可靠性时，需要全 面考虑各种攻击带来的破坏，通过部署故障恢复策略来提高网络的抗攻击能力。 除了作为通信网设计的关键指标，网络可靠性也是网络维护和管理的重要依据。 通过可靠性分析，可以得到部件重要性指标和运行可靠性指标，这些可以用来帮助工 程人员完成如下工作【j 卜1 2 】：发现网络中最脆弱的链路或结点，通过重点保护这些部件来 降低网络故障的风险；判断引发网络故障的最可能部件，以便故障发生时及时排除故 障，减少故障时损失；分析网络运行状态，对可能出现的故障进行预警，并采取主动 措施来减少故障时损失。 尽管如今的可靠性理论和可靠性工程技术取得了长足的进步，但是那些经典的可 靠性故障模型并不完全适用于网络系统。如今的通信网有着庞大的规模和动态复杂性， 经典的故障分布函数很难描述网络的故障特性【1 3 l 。为降低复杂性，解决基本的可靠性 问题，目前主流的网络故障分析方法都采用时间独立的离散概率模型1 1 3 j 。 最早的网络可靠性分析起源于电话交换网的可靠度评估，真正成为研究热点是在 第一个计算机网络鲫a n e t 诞生之后的上世纪七八十年代【1 3 】。这个时期，网络可靠性分 析主要讨论如何计算网络连通性，譬如，网络的连通度和结合度计算，网络连通概率 计算等等。其中，以网络连通概率精确计算为代表的网络可靠度计算问题被b a l l 等学 者证明为n p 难题，并得到了广泛研究【l 引。此时的网络规模较小、结构简单，主要的研 究方向包括：小规模网络和特殊结构网络的可靠度精确计算方法、一般网络可靠度的 北京邮电大学博士论文 第1 章绪论 近似计算方法。相应的成果有【6 ，1 4 j ：应用容斥原理精确计算网络可靠度、应用因子分解 精确计算网络可靠度；树型网络、可串并化网络可靠度的多项式复杂度计算法；网络 可靠度边界值的计算；网络可靠度的仿真近似计算。 进入上世纪八十年代后期和九十年代，网络规模和用户数量快速增长，网络的流 量急剧增加。工程人员发现即使网络连通也不能保证网络可靠工作，网络拥塞会引发 性能下降，并进一步导致部分业务无法正常运行。这个时期，从性能角度分析网络可 靠度成为研究的热点，并出现了基于网络业务的可用性指标研究【1 5 1 酬。电路交换网中， 呼损成为计算网络可靠度的重要参数；分组交换网中，时延成为计算可靠度的重要参 数。另外，针对性能逐渐下降直至网络服务失效，出现了对多态网络可靠性的研究1 1 7 ，l 剐。 但由于网络自身动态性和路由策略的影响，从性能角度精确分析可靠性存在很大的困 难1 1 9 ，2 0 】。另外，基于连通性的可靠度计算研究也进入了一个新领域。出现了一些可用于 中等规模和较大规模网络的计算方法，譬如，故障树方法和o b d d 方法【2 1 彩】。 进入二十世纪，随着网络应用场景和结构形式的变化，网络可靠性分析又面临了 新的问题。传统的可靠性分析一般假设网络中的保护措施足够维持结点可靠运行，这 在一些新的应用领域是很难成立的。譬如：自组织网络中，结点会因为电源耗竭或者 外界物理破坏而失效，此时不能再忽略结点故障对可靠性的影响：灾难环境网络中， 结点和备份结点会同时因为外力破坏而失效，此时忽略结点故障会高估网络的可靠度。 关于结点不可靠的研究并不多见，最初的解决办法就是把结点不可靠转化成结点可靠 问题，这将以增加计算复杂度为代价【川，而较为有效的方法有a b o e l f o t o h 的因子分解 方法和k | u o 的o b d d 方法1 2 4 ，2 5 l 。另外，传统的可靠性分析假设部件故障统计独立，这 在某些条件下也不成立。譬如：一次地震可能导致多个部件同时失效，一次外界打击 可能导致几个部件相继失效，此时忽略部件故障的相关性也会高估网络的可靠性，会 在设计时为后期故障埋下隐患。关于部件故障非统计独立的研究也不多见，早期的方 法有p a g e 和p e 玎y 提出的组合方法【矧，最新有代表性的成果是x i n g 的o b d d 方法【2 7 捌。 传统的研究重点放在如何有效计算可靠度，但一个可靠度数值或者边界值所包含 的可靠性信息并不充分，它既不能帮助工程人员了解网络的脆弱环节，也不能说明网 络运行时可靠性。因此，可靠性研究需要一些能全面反映全网可靠性的指标。这就引 起了关于网络部件重要性的研究和网络运行时可靠性的研究。早期的重要性研究往往 忽略部件的随机概率，从网络生成树数目、最短路径长度等入手分析部件的重要度 【2 9 3 1 】，而新近的研究更关注部件自身故障在其重要性中的作用。另外，现有的网络运 行时可靠性的分析主要依赖于运行时的历史数据统计1 2 0 j 。 当今的网络正在向各个领域深度延伸，其结构形式、布局规模、用户数量以及应 用场景正经历着翻天覆地的变化。这种变化使得网络可靠性面临着更多挑战：网络的 故障原因更加复杂，而网络的故障概率空前增加。从工业生产到科研开发到国防应用， 2 北京邮电大学博士论文第1 章绪论 因为网络的可靠性问题导致的网络故障不仅会带来巨大的数据损失，而且会带来灾难 性的后果。所以，网络可靠性研究得到了政府、企业和学者的广泛关注，与网络生存 性、抗毁性一起成为人们日益关注的问题。 本文的讨论仅限于二端网络的可靠性。这里的二端是指网络的两个端点，一个称 为源端，而另一个称为终端。如果在这两个端点之间讨论网络的某些属性，则称该网 络为二端网络。讨论通信网可靠性时，可以把二端网络的问题推广到k 端网络( k 个 端点之间通信可靠) ，全端网络( 网络中所有端点间通信可靠) 。当前互联网中很多场 景可以放到二端网络中讨论：新兴的端到端应用，如网络视频、网络电话等；而电信 运营商也非常关心端到端的网络可靠性，通过增加保护措施来保证特殊业务的服务质 量。 1 2 本文的研究内容和意义 本文的研究内容包括如下四个方面： 第一，研究了结点不可靠网络的可靠性分析。改进现有的o b d d 分析方法，提出 了基于标记因子划分的网络可靠度评估方法一m f p ( m a r k e d f a c t o rp a n i t i o n ) 和基于 特征识别的s t r e e t 网络可靠度评估方法s n r ( s t r e e tn e m o r kr e l i a b i l i t y ) 。传统的方 法是把不可靠结点转化成可靠结点来处理，这以增加计算复杂度为代价。本文的两种 方法是先为网络创建结点可靠的o b d d ，再利用边替代( e r ，e d g er e p l a c e m e n t ) 运算 处理o b d d 中的边变量，最后生成结点不可靠网络的o b d d ，具有较高的计算效率。 另外，在评估规模较大网络时，传统的因子分解方法在分解网络过程中存在大量的冗 余状态和重复计算，极大地降低了计算效率。本文通过如下方法来克服这一问题：分 解网络过程中，如果发现下一步分解的子网与曾经分解过的某个子网同构，就不再分 解该子网，直接利用同构子网的0 b d d 结构来创建全网的0 b d d ，避免分解同构子网 来带来的重复计算；利用o b d d 来存储网络状态，减少了冗余计算。关于同构子网的 处理，m f p 采用标记因子划分来识别同构子网，而s n r 把源端位置信息作为子网特征， 识别s t r e e t 网络分解过程中出现的大量同构子网。另外，针对无线传感网中众多不可靠 结点，提出了能有效评估无线传感网可靠度的算法e f ( e n h a n c e df a c t o r i n g ) ，采用 h a s h 表存储同构子网可靠度，提高可靠度计算效率。 第二，研究了共因失效网络的可靠度分析。在x i n g 的组合故障模型之上提出了分 析共因失效网络可靠性的算法一c n r ( c o m m o n c a u s e f a i l u r e n e 觚o r kr e l i a b i l i t y ) 和 分析无线传感网可靠性的算法w r ( w i r e l e s s s e n s o r - n e t w o r k sr e l i a b i l i t y ) 。x i n g 的 0 b d d 方法是当前最具代表性的共因失效网络分析方法，但当共因事件较多、网络规 模较大时，需要递归创建太多的共因失效网络的0 b d d ，因而执行效率低下。本文提 出的o b d d 创建方法只需要递归创建一个0 b d d 结构，这会在很大程度上降低了计算 3 北京邮电大学博上论文第l 章绪论 开销。关于如何创建共因失效网络的o b d d ，本文给出了两种方法：基于布尔运算的 方法和基于共因变量集的方法。第一种方式比较灵活，第二种方式有较高的存储效率。 另外，针对无线传感网中存在大量结点和共因事件的特点，本文把c n r 算法的思想应 用到无线传感网分析中，提出了w r 算法，较好地解决了共因失效和结点较多的问题。 第三，研究了网络部件重要性分析。提出了基于b i m b a u m 测度的链路重要性评估 方法b i l ( b i m b a u mi i i l p o n a n c eo fl i n k ) 和基于风险增长区间的网络可靠性评估方 法r i ( r i s ki i l c r e m e n t ) 。b i l 充分应用o b d d 来分析部件重要性，能同时计算b i m b a u m 测度、关键重要度和风险增长区间，可发现网络薄弱环节，确定最可能故障部件。而 r i 能够对部件故障时的网络可靠性稳定度进行分析，为网路抗毁性描述提供了又一个 参考指标。另外，针对无线传感网中不可靠结点，提出了基于风险增长的结点重要性 评估算法w n i ( w i r e l e s sn o d ei i l l p o r t a n c e ) 。 第四，研究了基于网络测量的可靠性分析。提出了基于网络测量的网络可靠性测度： 容错m p l s 网络的可靠性测度和自愈i p 网络可靠性测度。容错m p l s 网络的可靠性测 度根据故障次数来评价网络运行时可靠性，而自愈i p 网络可靠性测度根据测量的可用 带宽来评价网络运行时可靠性。另外，为分析m p l s 网络可靠性提出了一个自适应的 l s p 故障检测机制，根据延迟和检测包超时来调整故障检测周期，不仅能在业务要求 的时延范围内快速检测故障，而且把网络丌销控制在较低水平。 1 3 本文的结构和安排 本文的剩余部分内容安排如下： 第二章首先引入了二端网络的离散概率模型。然后描述了网络可靠性指标：确定型 测度、概率型测度、性能测度和网络部件重要性测度。最后综述了网络可靠性分析的 现状并指出了该研究领域所面临的挑战，着重介绍了：某些特殊网络的多项式复杂度 计算方法、网络可靠度的精确计算方法、网络可靠度的近似计算方法、基于性能的可 靠性分析以及网络部件重要性分析。 第三章首先介绍了o b d d 基本原理、运