（计算机应用技术专业论文）基于规则网络的可靠性与容错性分析.pdf

基于规则网络的可靠性与容错性分析 摘要 随着集群技术的发展，结点和链路的失效不可避免。因此，在有 结点和链路失效下对通信终端间存在可靠通信路径的概率和所有正 常结点的互通率进行研究就非常有必要了。由于网络中结点和链路的 失效具有随机性和不可预测性，这将给对规则网络的可靠性与容错性 研究带来巨大的困难。因而在对规则网络可靠性和容错性研究进行建 模时，通常只考虑分析其在不同条件下的可靠性和容错性，以降低其 研究难度和成本。对比分析其研究结果，也能对规则网络的可靠性和 容错性进行较为客观和准确的评估，以达到可利用的参考价值。 本文通过建立马尔科夫模型、子网概率模型和组合模型首先详细 探讨了e - 2 d m e s h 网络在链路失效独立和失效相关情形下的可靠性， 结果表明在链路失效独立时的可靠性要比链路失效相关时的可靠性 高。接着对可修复链路模式进行了研究分析，证明了不可修复链路模 式的可靠性要比可修复链路模式低。为了使模型更真实地反映网络的 运行环境，本文通过构造多级事件状态分解法以对具有结点和链路失 效情形下的网络可靠性进行了研究，基于该方法分析了多达上千个结 点的e - 2 d m e s h 网络在结点和链路失效率在一可控值时网络仍能达到 非常好的可靠性。另外，研究分析了e - m e s h 中正常结点可达时结点 失效率应控制在范围以达到9 9 以上的互通率。还提出了在e - 2 d m e s h 网络上的一个基于局部信息和分布式的容错单播路由算法，并对3 维 m e s h 网络上的自适应路由算法和确定性路由算法进行了比较，结果证 明了自适应路由算法的健壮性。 关键字：规则网络( e - m e s h ) ； 子网和概率模型；组合模型； 可靠性与容错性；马尔科夫模型； 多级事件状态分解法：路由算法 r e s e a r c h0 nr e l i a b i l l t ya n df a u l tt o l e r a n c e o fr e g u l a rn e t w o r k a b s t r a c t r e s e a r c ho nr e l i a b i l i t ya n df a u l tt o l e r a n c eo fr e g u l a rn e t w o r k ，w i t h t h ef a s te n l a r g e m e n to f p a r a l l e lc o m p u t e r si n t e r c o n n e c t i o nn e t w o r k ，n o d e a n dl i n kf a i l u r ew i l lb ei n e v i t a b l yh a p p e n e di nr e g u l a rn e t w o r k t h e r e f o r e ， t h es t u d yo ft h ep r o b a b i l i t yo fr e l i a b l ep a t hb e t w e e nt h et e r m i n a l sa n dt h e c o n n e c t e dr i g h tn o d e si sn e c e s s a r yu n d e rt h ec o n d i t i o no fl i n ka n dn o d e f a i l u r e d u et ot h ep r e d i c t a b i l i t ya n dr a n d o m n e s so f t h ef a i l u r eo fl i n k s a n dn o d e s ，w h i c hw i l le n l a r g ed i f f i c u l tt ot h es t u d yo fr e l i a b i l i t ya n d f a u l tt o l e r a n c eo fr e g u l a rn e t w o r kw h e nm o d e l i n go fr e l i a b i l i t ya n df a u l t t o l e r a n c eo fr e g u l a rn e t w o r k o f t e nc o n s i d e r i n gt h ep a r tc o n d i t i o no f r e l i a b i l i t ya n df a u l tt o l e r a n c ei no r d e rt or e d u c et h ed i f f i c u l t ya n dc o s t c o m p a r ew i t ht h es t u d yr e s u k s ，w ec a i la c q u i r eao b j e c t i v ea n dp r e c i s e e s t i m a t e s oc a nr e c e i v ev a l u er e f e r e n c e s i nt h i sp a p e r , b yp r o p o s i n gt h em a r k o vm o d e l ，s u b n e tm o d e la n d c o m b i n a t i o nm o d e l ，t h er e l i a b i l i t yo f e - 2 d m e s hn e t w o r kw i t h f a i l u r e d e p e n d e n t a n d f a i l u r e i n d e p e n d e n t l i n k si ss t u d i e d ，a n dt h e s i m u l a t i o n r e s u l t ss h o wt h a t t h e r e l i a b i l i t y o fn e t w o r kw i t h f a i l u r e d e p e n d e n tl i n ki sl e s st h a nt h eo n ew i t hf a i l u r e i n d e p e n d e n tl i n k s t oi n v e s t i g a t et h em o d e lo fe 一2 d m e s hw i t hr e p a i r a b l el i n k s ，p r o v i n gt h e r e s u l tt h a tt h er e l i a b i l i t yo fn e t w o r kw i t hu n r e p a i r a b l el i n k si s l e s st h a n t h eo n ew i t hr e p a i r a b l el i n k s i no r d e rt os i m u l a t em o r ea u t h e n t i cs i t u a t i o n ， am u l t i l e v e ld e c o m p o s i t i o na l g o r i t h mo ft h ee v e n ts t a t e ss p a c ei sg i v e n t oi n v e s t i g a t et h em o d eo fe 一2 d m e s hn e t w o r kw i t hn o d ea n dl i n kf a i l u r e b a s e do nt h ea l g o r i t h m ，t h er e l i a b i l i t yo fe - 2 d m e s hn e t w o r kw i t ho v e r o n et h o u s a n dn o d e sc a nr e a c hh e i g h t ，w h e nt h ef a i l u r ep r o b a b i l i t yo ft h e n o d ea n dl i n ki sc o n t r o l e di nab o u n d b e s i d e s ，i no r d e rt or e m a i n c o n n e c t e dp r o b a b i l i t yl a r g e rt h a n9 9 i ne m e s hn e t w o r k ，w h a tb o u n d t h a tt h en o d ef a i l u r ep r o b a b i l i t yi sc o n t r o l e di sp r o v e d ，a n dan o v e la n d s i m p l ef a u l tt o l e r a n c eu n i c a s tr o u t i n ga l g o r i t h mb a s e do nt h ec o n c e p to f k - e 一2 d m e s hi sp r o p o s e d ，w h i c hi sd i s t r i b u t e da n dl o c a li n f o r m a t i o n l a s t l y , c o m p a r i n gt h ea d a p t i v er o u t i n ga l g o r i t h mw i t ht h ed e t e r m i n i s t i c r o u t i n ga l g o r i t h m ，t h es t u d ys h o w st h a tt h ea d a p t i v er o u t i n ga l g o r i t h mi s m o r er o b u s t k e yw o r d s ：r e g u l a rn e t w o r k ( e - m e s h ) ； r e l i a b i l i t y a n df a u l t t o l e r a n c e ；m a r k o vm o d e l ； m o d e lo fs u b n e ta n dp r o b a b i l i t y ； c o m b i n a t i o nm o d e l ； m u l t i l e v e ld e c o m p o s i t i o na l g o r i t h mo ft h e e v e n ts t a t e ss p a c e ；r o u t i n ga l g o r i t h m 广西大学学位论文原创性声明和使用授权说明 原仓l j 性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得 的成果和相关知识产权属广西大学所有。除已注明部分外，论文中不包含其 他人已经发表过的研究成果，也不包含本人为获得其它学位而使用过的内 容。对本文的研究工作提供过重要帮助的个人和集体，均已在论文中明确说 明并致谢。 论文作者签名：锈 弘彳年易月呼日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： | 囹即时发布 口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 黼一题抽签耘叫月啪 基于规则网络的可靠性与为：锘性分析 第一章绪论 1 1 论文的选题背景及意义 集群技术的研究和发展是衡量一个国家科技发展水平和综合国力的重要标 志。如今它己在多个领域得到了重要的应用，越来越多的关键部门都对超级计算 机系统产生了很强的依赖。这些系统的计算机若出现问题，将带来巨大的损失。 由于规则网络其结构简单、规则、易于扩展且易于电路实现等优点而成为超级计 算机系统所采用的拓扑结构n 3 。因此，对以规则网络为拓扑结构的超级计算机系 统的可靠性和容错性进行研究分析正好满足了市场的这种需求。有着非常广阔的 应用前景，具有非常重要的实际价值。 随着电路集成技术的快速发展，多处理器计算机系统的价格也被越来越多的 公司企业所接受，这为多处理器并行计算机系统的应用提供了广阔的市场空间。 因此，并行多处理器系统的可靠性和容错性必须得到最基本的保证。目前，以规 则网络为拓扑结构的网络系统随着科技的进步得到了长足的发展，而由于其规模 的的迅速膨胀给系统的可靠性和容错性研究带来了巨大的挑战，且系统可靠性和 容错性研究滞后于该系统的发展。因此，如何设计可靠性和容错性更高的系统和 对系统的可靠性和容错性进行研究分析已成为当务之急。 由于系统的规模越来越大，事务越来越复杂，对其的分析和设计也变得非常 困难，同时，人们也越来越关注系统的正常工作能力。因此，系统的可靠性和容 错性问题也就显得越来越重要了。当前，对规则网络为拓扑结构的多处理器计算 机系统的研究主要集中于如何提高系统的业务性能，对其可靠性与容错性问题的 考虑却不够充分。 系统的可靠性与容错性是多处理器并行计算机系统的一项重要性能指标，目 前已引起了人们较为广泛的关注。国外在这方面已进行了多年的研究，国内在这 方面的研究起步较晚，以规则网络为拓扑结构的多处理并行计算机系统是未来计 算机的发展方向之一，对其的研究是一个十分重大且复杂的课题，也是目前多处 理器计算机系统发展过程中有待解决的问题之一。 1 2 国内外研究现状 广西大掌硕士掌位论文 囊：于规更网络的可靠性与容错性分析 随着多处理器计算机系统网络规模的不断扩大，结点的失效和链路的失效不 可避免。因此，对该系统网络可靠性和容错性问题进行研究就显得很有必要了， 即保证在网络中存在结点或链路失效的情况下，终端间仍然保持可靠的通信或正 常结点互通。已经有学者对m e s h 网络口一4 j ，6 7 - 吼9 1 、超立方体网络n 仉儿m m 1 4 3 、星型 网络n “埔1 等为拓扑结构的并行多处理器计算机系统在结点失效独立情况下的容 错性进行了研究，但是这几种网络拓扑在结构上总存在着一些欠缺。如：m e s h 网络有良好的扩展性，但是没有超立方体的强容错性；超立方体具有强容错性、 直径短等优点，但是不便于扩展；星型结构便于操作，但是由于其容错性较差， 在设计并行多处理器计算机系统时已不被采用。于是有学者提出在m e s h 网络拓 扑结构上增加两条对角线以形成可扩展的m e s h 网络拓扑结构e m e s h 网络 n j 7 1 ，它具有近似于超立方体的强容错性，又拥有m e s h 网络的良好扩展性。 1 2 1 网络可靠性与容错性模型的研究 近年来，在研究通信网络可靠性时，有些学者只考虑链路失效独立情况下系 统网络的可靠性n8 1 9 3 ，但实际上由于负载等因素的影响，一条链路的失效会影响 到其它链路的失效率，这就是链路的失效相关，它不考虑链路失效后对其进行修 复，也就是假设链路在失效后是不可修复的，而在实际系统网络中，为了保证数 据通信的安全，都进行了冗余设计，这就为在有链路失效时对其进行修复提供了 方便，并且在短时间内是不会影响到系统网络正常通信的，于是有学者提出了在 链路可修复情况下系统网络的可靠性盟0 2 川。在研究具有失效链路系统网络可靠性 时，有学者提出了组合模型方法瞳羽，它要求把网络分成子网，通过子网可靠性的 串并联组合得到整个网络的可靠性。例如，m e n e z e s 等人使用组合模型方法分析 了多级网络的可靠性豫3 2 们，由于链路失效的相关性和e - m e s h 网络结构的特殊性， k - e - 2 d m e s h 子网的可靠性不能通过串并联组合模型来分析。又有学者提出使用 马尔科夫链模型来对系统网络可靠性进行分析，它主要是通过建立状态转移图 来分析系统网络的可靠性。例如，b r o w n 等人利用分级马尔科夫链模型分析了分 布式系统的的可靠性口6 一”，丽对于较大规模的网络结构，应用马尔科夫链模型往 往又显得太过复杂且计算量过于庞大。鉴于组合模型和马尔科夫链模型在研究系 统网络方面的特性，本文作者首次提出了组合模型与马尔科夫链模型相结合的方 法来研究分析e - m e s h 网络在链路失效隋况下的可靠性。 2 广西大掌硕士掌位论文| j 于规更网络的可靠性与窖错铂。伊析 在多处器计算机系统网络中，很少有学者同时考虑结点和链路都失效的情 形，大多只考虑结点或者链路的失效。如文献 2 8 ，2 9 只考结点失效独立情况下 系统网络的容错性，文献 1 8 对链路失效独立和链路失效相关情况下系统网络的 可靠性进行了研究分析。在考虑结点和链路失效的可靠性计算方法中，现有的方 法如f a c t o r i n g 法，b u z a c o t z 法运算量都很大，只能分析中小规模网络。文献 3 0 提出的多边形化简方法，只能减小等效网络的状态空间，仍需要进行大量的 计算。网络分解技术 着眼于处理事件而不是基本事件，从而大大提高了运算速 度，然而，这种方法用于计算大规模并行多处理器计算机网络时仍具有较大的运 算量。基于上述原因，本文采用网络分解技术对结点和链路失效下子网的可靠性 进行定量分析，再通过组合模型计算出整个系统网络的可靠性。 本文主要针对了e - m e s h 网络在结点失效、链路失效、结点和链路都失效情 况下对其可靠性和容错性进行了研究分析。 1 3 本文的主要工作 本文以并行多处理器计算机系统的网络拓扑结构为研究对象，对e - m e s h 网 络拓扑结构进行建模与分析，从多个不同的角度对其可靠性与容错性进行了研 究。具体来说，本文的内容主要包括如下几个方面： 1 、研究分析了e - m e s h 网络在链路失效独立和链路失效相关条件下系统网络 的可靠性，指出了现有方法存在的一些不足，实现了较大规模系统网络可靠性的 定量分析。 2 、提出了马尔科夫链模型与组合模型在链路不可修复与链路可修复下的应 用，证明了对较大规模的e - m e s h 链路失效率在合理范围内时仍能保持相当高的 可靠度。 3 、构造了多级事件状态分解法对有结点和链路失效情况下的系统网络可靠 性进行了研究分析，该方法比当前的一些主要模型有更好的适应性，能应用于大 规模的系统网络且有较小的运算量优势。 4 、研究分析了e - m e s h 网络在结点失效独立情形下整个网络的容错性，并 分析比较了m e s h 网络的容错性，得出了有意义的结论。 5 、提出了结点失效独立下e - m e s h 网络上的容错单播路由算法，该算法证 3 厂。西大学硕士掌位茛艺炙羲于规更网络的可靠佳与容错性分析 明了结点失效率控制在定的范围内时，算法畿以较高的概率找到一条路径遍历 网络中的所有正常结点。 6 、对3 一维m e s h 网络上确定性路由算法与自适应路由算法进行了比较，分 析证明了3 一维m e s h 网络上自适应路由算法优于确定性路由算法。为今后在 e - m e s h 上路由算法的研究提供了依据。 1 4 本文工作的创新点 本文的创新工作主要体现在以下几个方面： 1 、对e - m e s h 网络在链路失效独立和链路失效相关条件下的可靠性进行了分 析比较，得出了在链路失效独立下的可靠性要高于链路失效相关下的可靠性。 2 、对e - m e s h 网络在链路不可维修与可维修状态下的可靠性进行了研究分析， 得出了在链路可维修状态下的可靠性要好于链路不可维修状态下的可靠性。 3 、对e _ m e s h 网络在结点与链路都失效情形下的可靠性进行了研究分析，构 建了状态空间分解法，得出了定量的分析结果。 4 、对e - m e s h 网络在结点失效独立情形下网络的容错性能进行了研究分析， 证明了大规模e - m e s h 网络在结点失效独立下仍然保持相当高的互通率。 5 、构建了在有失效结点的e - m e s h 网络上的容错单播路由算法，该算法有力 地表明了当结点失效率控制在某一范围内时，算法能以相当高的概率找到由正常 结点组成的路径。 6 、从概率的角度对3 d m e s h 网络上确定性路由算法和自适应性路由算法进行 了分析比较，实验结果表明，在3 d m e s h 网络上自适应路由算法优于确定性路由 算法。 1 5 论文的组织结构 本文针对规则网络存在结点或链路失效情况下，构建了不同的模型对其可靠 性与容错性进行了研究分析。本文各章节的安排如下： 第一章绪论 主要介绍了论文的选题背景，阐述了论文选题的意义，对本课题的国内外研 究现状进行了介绍；介绍了本文的主要工作及创新。 d 广西大掌硕士学位论文 基于规皿g 网络的可靠性与容铬性分析 第二章e - 2 d m e s h 网络中链路失效模型的可靠性分析 首先对链路失效独立的e - 2 d m e s h 网络进行了分析，并建立了相应的可靠性 研究模型，接着建立了链路失效相关的e - 2 d m e s h 网络可靠性模型，利用福克一 普朗克方程对其进行求解并通过m a t l a b 仿真工具对模型进行了仿真，最后比较 了在两种模式下网络的可靠性。 第三章具有可修复链路的e - 2 d m e s h 网络可靠性 总结前人对拓扑结构的研究工作，对e - 2 d m e s h 网络分别在单工链路不可修 复与可维修模式下进行了研究并建立了相关的可靠性模型，最后对它们的可靠性 进行了比较且绘制出了可靠性曲线，得出了有意义的结论。 第四章具有失效结点和链路的e - 2 d m e s h 网络可靠性 讨论了前人在研究具有结点和链路失效情况下网络可靠性时采用的方法策 略及其不足，提出了采用子网和网络分解技术对e - 2 d m e s h 网络进行研究的新方 法。并对该方法进行了实验验证，证明了该方法的可行性。 第五章e - l f f e s h 网络的容错性分析 利用分块策略对e - m e s h 网络在结点失效独立情形下网络的容错性进行了研 究分析，并给出了要使网络保持较高的互通率，结点的失效率应控制在的范围。 第六章e - 2 d m e s h 网络容错单播路由算法 在前面几章的基础上，提出了e - 2 d m e s h 网络上的容错单播路由算法，该算 法是基于局部信息及分布式的。对该算法进行了实验验证，结果表明了该算法的 健壮性。 第七章3 一维m e s h 网络中两种路由的研究 首先构造了在3 一维m e s h 网络上的确定性路由算法与自适应路由算法，并求 出了这两种算法分别在3 一维m e s h 网络上找到由正常结点组成路径的概率为某一 值时网络结点的失效率并对这两种算法的健壮性进行了比较。 第八章总结 5 广西大掌硕士掌位论文基于规曼g 网络的可靠性与客错性分析 对本文的工作进行了总结，对后续研究进行了展望。 6 r - 西大掌硕士掌位论文基于规舅9 网络的可靠性与容错性分析 第二章e - 2 d m e s h 网络中链路失效模型的可靠性分析 集群技术的研究和发展是衡量一个国家科技发展水平和综合国力的重要标 志。如今它已在多个领域得到了重要的应用，越来越多的关键部门都对超级计算 机系统产生了很强的依赖。这些系统的计算机若出现问题，将带来巨大的损失。 由于规则网络其结构简单、规则、易于扩展且易于电路实现等优点而成为超级计 算机系统所采用的拓扑结构。因此，对其可靠性进行研究将成为人们关注的重 要课题。 网络可靠性是网络的关键性能之一，它表示从网络中任意结点到其它所有结 点至少存在一条路径的概率2 1 。网络可靠性可以通过组合模型和马尔科夫链模型 来分析。组合模型方法要求把网络分成子网，通过子网可靠性的串并联组合得到 整个网络的可靠性。例如，m e n e z e s 等人使用组合模型方法分析了多级网络的 可靠性2 鲥。由于链路失效的相关性和e - 2 d m e s h 网络结构的特殊性，k - e - 2 d m e s h 子网的可靠性不能通过串并联组合模型来分析。马尔科夫链模型方法通过建立状 态转移图来分析网络的可靠性n 8 1 。例如，b r o w n 等人利用分级马尔科夫链模型分 析了分布式系统的可靠性汹 2 7 3 3 l 。而对于较大规模的网络结构，应用马尔科夫链 模型往往又显得太过复杂且有庞大的计算量。鉴于组合模型和马尔科夫链模型在 研究网络可靠性方面的特性，本章采用组合模型和马尔科夫链模型相结合的方法 来分析e - 2 d m e s h 网络链路失效情况下的可靠性。 本章主要运用系统负载共享模型绉钉，利用马尔科夫链模型对链路失效下 k - e - 2 d m e s h 子网的可靠性进行定量分析，再通过组合模型计算出整个e - 2 d m e s h 网络的可靠性。在链路失效条件下，分析了每一个结点到其它所有正常工作结点 至少存在一条通信路径的概率，即采用互通率来评价e - 2 d m e s h 网络的可靠性。 2 1e - 2 d m e s h 网络的可靠性模型 在这里用e m 。来表示一个规模为朋玎的e - 2 d m e s h 网络，并假定网络只能 进行单向传输数据，即链路为单工链路。方向如图2 一l 所示。 规模为m ，? 的e 一2 d m e s h 结构，可分成( m 七) ( ，7 k ) 个不相交的k e 一2 d m e s h 7 广西大掌硕士掌位论文 基亏叫盹则网络的可靠性与客错性分析 子网，整个e - 2 d m e s hn - 绍e m 被分成耽尼行和n k 列，每行与每列上分别有 子网个数为n k ，和mtkc 图2 一l 给出了6 x6 的e - 2 d m e s hn - 绍e m 6 x 6 被分成4 个 图2 - 1 譬一e 一2 d m e s h 于网划分策略 f i g2 - 1t h ep a r t i t i o n i n gs t r a t e g yo f k - e - 2 d m e s h 当前在研究网络可靠性时，一般都认为链路失效独立。事实上，网络间链路 是共享通信负载的n 韶。条链路的失效，会导致消息选择其它链路路由，使得其 它链路上的负载增大，进而使得这些链路有更高的失效风险。因此，链路失效是 相互关联的。 2 1 1 链路失效独立的可靠性模型 令e m 为一规模为k k 的e - 2 d m e s h 网络，为了方便起见，本文以3 x3 规模 的3 一e 一2 d m e s h 子网为例来分析子网可靠性模型。有9 个结点，单向不可修复的 链路组成的e m ，如图2 2 所示。依据电子工业标准设链路失效服从指数分布，正 常工作时网络上链路失效率均为元。与链路失效独立相对应的马尔科夫链状态转 换图如图2 3 所示。 在图2 2 中，我们假定所有虚线表示的链路都是有效链路，实线表示的链路 具有失效性。 定义2 1 由于链路失效，在实线表示的链路部分，除结点瓯不能接收消息 和结点d 。不能发送消息外，在子网中如果存在一个结点不能接收或者发送消息 时，网络即不连通( 网络失效) 。 图2 3 中，状态i ( i = 0 , 1 ，1 0 ，f ) 表示有f 条链路失效，子网仍互通的状态。 o 状态为初始状态，f 状态为不通状态。有向弧上数字为在出时间内的状态转 移概率。 8 f - 西大掌硕士掌位论文 蓉于规更网络的 - a j - 靠性与容错性分析 一 醛 ， 、 n o l 。 ， ；、 ，。 ，p 、一 图2 23 33 - e 一2 d m e s h 子网 图2 3 失效独立时的马尔科夫链状态转 f i g2 - 23 x33 - e - 2 d m e s h f i g2 - 3t h es t a t et r a n s i t i o nd i a g r a mo fm a r k o vw i t hf a i l u r c - i n d c p c n d c m 下面建立子网的状态转换图，在不可维修的3 3 规模子网中，若在失效的i 条 链路外又有链路失效，那么失效链路的生成导致状态从f 向j ( j = f ，f + 1 ，1 0 ，f ) 转移。以下分别讨论已失效链路外链路失效时导致各状态转移的情况。 0 寸f ：表示从正常状态变为网络失效状态，根据定义2 - i ，容易得知，只 要图2 2 中左右两边四条链路中的任意一条失效，网络即进入不连通状态。因此 从o 状态转移到f 状态的概率为e - 4 触。 o 一1 ：表示子网从0 条链路失效变为有1 条链路失效，子网仍然互通。因 为子网共有2 0 条可失效链路，除了能使网络从正常状态转移到不连通状态的四 条链路，剩下1 6 条链路中的任意一条都能使网络从0 状态转移到l 状态。因此 转移概率为e - 1 6 尬。 0 0 ：网络保持原状态的概率为1 一e - 2 0 他。 同理，可以得出f 寸j ( i = 1 , 2 ，1 0 ，f ；j = f ，i + 1 ，1 0 ，f ) 状态转移概率，结果 如图2 3 所示。 为了分析子网的可靠度r ，以下建立子网的状态转移方程。 在t = t 时刻：定义e m 3 处于0 状态下，畏u , - f 常状态下的概率为p ，处于 f ( f = 1 ，2 ，l o ) 状态t ，e m 。仍然互通的概率为p “，e m 3 处于f 状态下的概率为 p f l o t = t + t 时刻： 0 、在0 状态下，只有e m ，从t 时刻开始t 时刻内没有链路出现故障，才 9 广西大掌硕士学位论文 基于规更g 网络的可靠性与容错性分析 能保证删3 维持正常状态，此时的概率为：p 岍厶r = 风，( 1 - 2 0 ；j x t ) + 。( 缸) 。 1 、删。处于1 状态有两种情况，t = t 时e m 。处于1 状态下，经t 仍为1 状态，此时的概率为局，( 1 - 1 9 2 a t ) + d ( 血) ；t = ti 对e m 3 处于0 状态，经过t 后变为l 状态，此时的概率为p o j1 6 2 z x t + o ( a t ) 。故在t = t + x t 时刻，1 状态的 总概率为： 巩+ f2p t ，r ( 1 1 9 2 a t ) + p o f1 6 2 2 9 + o ( a t ) 对应的方法，可得t = t + x t 时刻处于歹( ，= 2 , 3 ，1 0 ，f ) 状态的概率分别为 p 2 ，f + 血2p 2 ，。( 1 1 8 2 a t ) + p 1 j1 5 2 m + d ( 址) 乜，+ f2 乜，( 1 1 7 2 a t ) + p 2 ，1 4 2 a t + o ( 6 t ) p 4 ，+ r2 鼽，：( 1 1 6 2 a t ) + p 3 ，1 1 2 a t + d ( & ) p 5 。，+ f 2 p 缸( 1 1 5 l t ) + p 4 。；9 a 2 l t + o ( a t ) p 6 ，+ f 2 p 6 ，( 1 1 4 a 2 0 ) + p 5 ，8 元f i a + o ( a t ) p 7 ，+ r 2 p 7 j ( 1 1 3 2 a t ) + p 6 ，7 2 a t + d ( 出) ， p s ，f + 厶f = p s 。，( 1 1 2 尬) + p 7 ，5 z f + o ( a t ) ， p 9 ，f + 血= p 9 ，( 1 1m a t ) + p 8 ，2 2 a t + o ( a t ) p m + 血2p 10 f ( 1 1 0 2 a t ) + p 9 j 础+ o ( m ) p f ，“矗f = p o ，4 2 a t + p 1 。f4 2 a t + p 2 ，4 勉+ p 3 ，f6 2 2 l t + p 4 ，7 2 a t + p 5 ，f7 2 x t + p 6 ，7 尬f + p 7 ，8 2 a t + p 8 ，f1 0 2 5 2 + p 9 ，1 0 2 z k t + p 1 0 ，1 0 2 a t + o ( a t ) 由此，可得e m 3 的可靠性在这里，定义可靠度r ，( r ) ( o i 1 0 ) 为e m ，到 时刻t 有f 条链路失效仍互通的概率 定理2 - 1 设e m 3 中每条链路的独立失效率为彳，则e 嵋的互通率为 尺( f ) = p “ 1 0 ( 2 1 ) 广西大掌硕士掌位论文基于规则网络的可靠性与容错性分析 其中p 。，r = p 2 0 m ，p 1 j = - 1 6 e 五o m + 1 6 e 一1 蛐，p 2 ，l = 1 2 0 e - 2 吮一2 4 0 e 一1 9 血+ 1 2 0 e 一1 胁，p 3 ，f = - 5 6 0 e 2 0 m + 1 6 8 0 e 一1 叻一1 6 8 0 e 一1 8 m + 5 6 0 e 一1 弛，p 4 ，f = 15 4 0 e - 2 蚴 6 1 6 0 e 一1 9 m + 9 2 4 0 e 一1 胁一6 1 6 0 e 一1 7 m + 1 5 4 0 e 一1 铀，p 4 r = 1 5 4 0 e 以叻一6 1 6 0 e 一1 9 m + 9 2 4 0 e 一1 姚一6 1 6 0 e 一1 7 m + 1 5 4 0 e 一1 缸，p 5 = - 2 7 7 2 e 一2 0 m + 1 3 8 6 0 e 一1 蛐一2 7 7 2 0 e 一1 8 m + 2 7 7 2 0 e 一1 似一1 3 8 6 0 e 一1 6 刀+ 2 7 7 2 e 一1 跏， 5 5 4 4 0 e 一1 8 刀一7 3 9 2 0 e 一1 7 m 上5 5 4 4 0 e 一1 6 m p 6 。= 3 6 9 6 e 屯。刀一2 2 1 7 6 e 一1 9 m + 2 2 17 6 e 一1 5 尉+ 3 6 9 6 e 一1 拙，p 7 j = 一3 6 9 6 e - 2 0 加+ 2 5 8 7 2 e 一1 9 加一7 7 6 1 6 e 一1 8 m + 1 2 9 3 6 0 e 一1 似一1 2 9 3 6 0 e 一1 6 m + 7 7 6 1 6 e 一1 5 m 一2 5 8 7 2 e 一1 4 血+ 3 6 9 6 e 一1 址，p 8 - f = 2 3 10 e 一2 0 知一18 4 8 0 e 一1 9 血+ 6 4 6 8 0 e 一1 胁一 1 2 9 3 6 0 e - 1 7 m + 1 6 1 7 0 0 e 一1 劬一1 2 9 3 6 0 e 一1 5 m + 6 4 6 8 0 e 一1 拙一1 8 4 8 0 e 一1 3 m + 2 3 1 0 e 一1 执，p 9 = - 1 5 4 0 3 e 。2 0 m + 4 6 2 0 e 一1 锄一1 8 4 8 0 e 一1 8 加+ 4 3 1 2 0 e 一1 仙一 6 4 6 8 0 e - 1 6 m + 6 4 6 8 0 e 一1 锄一4 3 1 2 0 e 一1 4 m + 1 8 4 8 0 e 一1 3 m 一4 6 2 0 e 一1 2 m + 1 5 4 0 3 e 一1 ， p 1 。j = 1 5 4 3 e 一2 0 m 一1 5 4 0 3 e 一1 9 m + 2 3 1 0 e 一1 8 m 一6 1 6 0 e 一1 7 刀+ 1 0 7 8 0 e 一1 铋一 1 2 9 3 6 e - 1 5 m + 1 0 7 8 0 e 一1 铆一6 1 6 0 e 一1 3 m + 2 3 1 0 e 一1 2 m 一1 5 4 0 3 e 一1 1 m + 1 5 4 3 e 一1 0 刀 证明：前面我们已经建立了e m ，的状态转移方程，根据福克一普朗克方程式 汹j ，可得以下方程组： ，功= - 2 0 勿0 f 嘲，出= 一1 9 l j + 1 叻砧 咖2 l ，出= 一1 矽2 j + 1 s 矽1 。f 如，出= 一1 7 勿3 j + 1 4 助2 ， 觑j 功= 一1 脚4 ，+ 1 坳3 ， 如，7 丞= 一1 5 矽5 。，+ 9 纸， 和6 ，出= 一1 4 和6 f + 8 印5 ， 觑，出= 一1 3 幼7 ，+ 7 印6 ， 觑，西= 一1 狮8 ，+ 5 和7 ， 和9 ，出= 一l l 谚9 ，+ 2 幼8 f 咖l 功= 一1 0 勿lo ，+ 幼9 ， l 勿f ，出= 4 细o ，+ 4 印l f + 4 印o ，+ 4 矽2 j + 6 勿3 ，f + 7 勿钾+ 7 勿5 ，f + 7 劫6 ，+ 8 幼7 ，+ l n 矽w + 1 0 矽9 ，+ 1 0 广西大掌硕士掌位锐吁 基亏哆圮则网络的可靠性芎霉。锗性分析 初始条件为：p o ，。= l ，p 呻= 0 ( f - 1 ，2 ，1 0 ，d 。求得此微分方程的解为 p u ( 0 fs 1 0 ) ，在上面已经列出。因为可靠度只，( f ) = 足一l ( f ) + p f f ，r o ，= 只。， 1 0 所以容易得出e m ，的可靠度为r ( r ) = z p “。得证。 1 - - 0 图2 4 失效独立时e - 2 d m e s h 的可靠性图2 5 失效相关时的马尔科夫链状态转换图 f i g2 - 4t h er e l i a b i l i t yo f e - 2 d m e s hw i t hf a i l u r e - i n d e p e n d e n tf i g 2 - 5t h es t a t et r a n s i t i o nd i a g r a mo fm a r k o v w i t hf a i l u r e - d e p e n d e n t 由于规模为m xf 的e - 2 d m e s h 网络可被分成( m 3 ) ( n 3 ) 个不相交的 3 - e - 2 d m e s h 子网，根据我们的设定，当每个子网互通时，整个e - 2 d m e s h 网络 1 0 e m 。就互通。依据定理2 - 1 ，可得删棚。的可靠度为( z p ，。) ”州9 。根据可靠性 i = 0 手册，取五= 3 5 0 9x1 0 - 6 ，可得不同规模下链路失效独立时e - 2 d m e s h 的可靠性。 结果如图2 4 所示，可靠性曲线都是通过m a t l a b6 5 中的库函数绘制出来( 虚线 为3 3 e 一2 d m e s h 的可靠性，实线为1 2 1 2 e - 2 d m e s h 的可靠性) 。 2 1 2 链路失效相关的可靠性模型 失效相关是由于通信负载共享，某条链路的失效使得其它链路有更高的失效 风险。在负载共享模型中，某部件的失效，使得其它部件有如下失效规则：公平 负载共享规则、局部负载共享、单调递增负载共享口副。本章正是采用局部负载 共享规则进行研究。 即具有同源结点的条链路失效后，剩下的k 一歹条链路的失效率会增大为原 来的k ( k 一) 倍。本章只对该种情况的可靠性进行研究分析，其它情况下的可靠 1 2 广西大掌硕士掌位论文墓于规更9 网络的引 性与客错性分析 性暂不作讨论。链路失效相关时对应的状态转换图如图2 5 所示。 下面我们对状态转换图的建立进行分析，e m ，初始处于0 状态，所有链路的 失效率均为力，若图2 2 中左右两边四条链路中的任意一条失效，网络即进入不 连通状态。因此从0 状态转移到f 状态的概率为一尬。若除这四条链路外的任 意一条链路失效，e m 3 则进入1 状态，此时的转移概率为e - 1 6 他。e m ，保持为0 状态的概率则为1 8 - 2 0 尬。不妨假设在0 状态进入l 状态过程中，链路a 失效， 根据公平负载共享规则，此时与该链路具有相同源结点的另外两条链路的失效率 变为3 2 五，。其它状态间的转移概率见图2 5 。 同理，可建立e m ，链路失效相关下t + t 时刻的状态方程 p 岍f2p o ，( 1 2 0 a s t ) + o ( a t ) p 1 + f = p 1 ，( 1 2 0 2 a t ) + p o ，1 6 a m + o ( a t ) p 2 j + r = p 2 ，( 1 2 0 a m ) + p l j1 6 2 m + d ( 垃) p 3 j + f = p 3 ，。( 1 2 0 2 m ) + p 2 f1 6 2 m + o ( a t ) p 4 h f = p 4 ，( 1 2 0 a a t ) + p 3 ，1 3 2 a t 十o ( a t ) p 5 ，魁= p 5 ，( 1 2 0 2 缸) + p 4 ，1 1 勉 + d ( 址) p 6 p f = p 6 ，( 1 2 0 勉f ) + p s 9 2 a t + d ( 缸) p 7 j + r = p 7 ，f ( 1 2 0 2 m ) + p 6 ，。3 1 3 2 a t + o ( a t ) p 8 f + f = p 8 。，( 1 2 0 2 m ) + p 7 ，1 7 2 2 a t + d ( 出) p 9 。，+ f = p 9 ，( 1 - 2 0 2 m ) + p 8 7 2 2 m + o ( 6 t )