（计算机软件与理论专业论文）基于star网络的可靠性与容错性分析.pdf

广西大学学位论文原创性声明和使用授权说明i i i f f i h i i i 丫1 ，3 8 0 4 7 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有。除已经注明的部分外，论文中不包含其他人已经发表过的 研究成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重 要帮助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名：花仁f 兰 2 0 1 0 年乡月小 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 团即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：花仁左 导师躲獗2 0 1 0 年月伊 基于s t a r 网络的可靠性与容错性分析 摘要 基于高性能计算机应用环境的危险性和复杂性，其互连网络的可靠性 与容错性必须得到保证。但是，网络元件的失效或故障往往都具有随机性 和不可预测性，这给互连网络可靠性的研究带来了不小的困难。而且，在 现有的研究中，仍然有一些问题需要解决，比如评估方法和算法的过于复 杂、统一指标体系的缺乏、寻径策略的非容错性等。不过，图论、概率论 以及数学建模等方法的应用保证了分析的严密性和逻辑性，实验分析和对 比法的应用保证了分析的正确性、结果的实用性。 本文首先对链路失效( 结点独立正常) 概率模型下s t a r 网络中仍然 存在着非失效子网的可靠性概率进行分析，结果表明s t a r 网络的可靠度 是完全可以控制在o 9 9 以上的。对比试验结果表明在同等规模、网络元 件可靠概率一致的网络环境下，只考虑链路失效而假定所有结点完全正确 情况下的网络可靠性要比只考虑结点失效而假定所有链路完全正确情况 下的网络可靠性要高。接着，本文将贝叶斯网的概率推理用于s t a r 网 络可靠性的评价中，并通过网络的二连通率来对网络可靠性进行分析。 结果表明如果失效结点数量在有条件的容错模型内，那么失效结点不同分 布情况下的网络二连通率差值可以忽略不计，而且，在现有大规模集成电 路技术条件下，失效概率可以严格限制在低于1x1 0 q 级别的概率范围内， 因此网络可靠度可以直接用网络二连通率来表示，并以此为标准将网络可 靠性控制在一个较高范围内，进而满足网络的不同实际需求。最后，本文 还对s t a r 网络下的容错寻径策略进行了研究，提出了一个具有一定白适 应性的容错寻径算法。结果表明，在可控的结点失效概率下，对于大规模 的s t a r 网络，算法仍能够在一定的时间复杂度内以大于9 9 概率找到几 乎所有的并行路径，且包含了所能找到的最短路径。 关键词：s t a r 网络可靠性与容错性结点链路失效容错模型二 连通率容错寻径 h r e s e a r c h0 nr e l i a b i l i t ya n df a u l tt o l e r a n c e o fs t a rn e t w o r k a bs t r a c t r e l i a b i l i t ya n df a u l tt o l e r a n c eo fi n t e r c o n n e c t i o nn e t w o r ku s e di n h i g h p e r f o r m a n c ec o m p u t e r sh a v et ob eg u a r a n t e e db e c a u s eo fr i s ka n d c o m p l e x i t yo fa p p l i c a t i o ne n v i r o n m e n tf o rt h e m f a i l u r e so rf a u l t sf r o m n e t w o r ku n i t sg e n e r a l l yh a v er a n d o m n e s sa n du n p r e d i c t a b i l i t y , s ot h e r ea r e m a n yl a r g ed i f f i c u l t i e si ns t u d yo nr e l i a b i l i t yo fi n t e r c o n n e c t i o nn e t w o r k n o w , t h e r ea r es t i l lm a n yp r o b l e m sw h i c hn e e dt ob es o l v e di nt h ec u r r e n ts t u d y , s u c ha st o oc o m p l e x i t yo fm e t h o d sa n d a l g o r i t h m su s e df o re v a l u a t i n g ，l a c ko f u n i f i e di n d e xs y s t e m ，n o n - f a u l t - t o l e r a n ta n ds oo n h o w e v e r , s o m em e t h o d s ， s u c ha sg r a p h t h e o r y , p r o b a b i l i t yt h e o r ya n dm a t h e m a t i c a lm o d e l i n ga n ds oo n ， e n s u r et i g h t n e s sa n dl o g i co fa n a l y s i s ，a n dt h ea p p l i c a t i o no fe x p e r i m e n t a l a n a l y s i sa n da n t i t h e s i sg u a r a n t e e sc o r r e c t n e s so fa n a l y s i sa n dp r a c t i c a lo f r e s u l t s i i lt h e p a p e r , t h er e l i a b i l i t yp r o b a b i l i t yt h a tt h e r ea r es t i l lc o r r e c t s u b 。n e t w o r k si ns t a rn e t w o r k sb a s e do np r o b a b i l i t ym o d e lo nl i n kf a i l u r ei s a n a l y z e df i r s t l y r e s u l t ss h o wr e l i a b i l i t yo fs t a rn e t w o r k sc a nb ec o n t r o l l e d a b o v e0 9 9 r e s u l t so f c o m p a r a t i v et e s ts h o w , u n d e rt h es a m es c a l eo fn e t w o r k a n dr e l i a b i l i t yp r o b a b i l i t yo fn e t w o r ku n i t ，r e l i a b i l i t yo fn e t w o r kw i t hl i n k f a i l u r ea n da l ln o d e sn o r m a li s h i g h e rt h a nt h a to fn e t w o r kw i t ha l ll i n k s i i l n o r m a la n dn o d ef a i l u r e s e c o n d l y , p r o b a b i l i s t i ci n f e r e n c eb a s e do nb a y e s i a n n e t w o r k si sp u ti n t oe v a l u a t i o no nr e l i a b i l i t yo fs t a rn e t w o r k s ，a n di ti s a n a l y z e da n de v a l u a t e db yt w o c o n n e c t i o np r o b a b i l i t y r e s u l t ss h o wi f a m o u n to ff a i l u r en o d ei sc o n t r o l l e du n d e rc o n d i t i o n a lf a u l tt o l e r a n c em o d e l ， t h ee r r o ro ft w o c o n n e c t i o np r o b a b i l i t yu n d e rd i f f e r e n td i s t r i b u t i o ns i t u a t i o n s o ff a i ln o d e sc a nb ei g n o r e d b e c a u s ef a i lp r o b a b i l i t yc a nb es t r i c t l yl i m i t e dt o a p r o b a b i l i t yr a n g e b e l o wlxlo 4r a n ku n d e rc u r r e n tv l s it e c h n o l o g y , r e l i a b i l i t yo f n e t w o r k sc a nb er e p r e s e n t e db yt w o c o n n e c t i o np r o b a b i l i t ya n d c o n t r o l l e da b o v eah i g hr a n kw i t hi ta st h es t a n d a r d ，w h i c hm e e t sd i f f e r e n tr e a l r e q u i r e m e n t sf r o mn e t w o r k s f i n a l l y , t a c t i c so nf a u l t - t o l e r a n c es e e k i n gp a t h b a s e do ns t a rn e t w o r k si sr e s e a r c h e d af a u l t t o l e r a n c e s e e k i n gp a t h a l g o r i t h m w i t hc e r t a i n a d a p t i v e i s p r o p o s e d r e s u l t ss h o w , u n d e rt h e c o n t r o l l a b l ep r o b a b i l i t yo fn o d ef a i l u r e ，t h i sa l g o r i t h mf o rs t a rn e t w o r k s w i t hl a r g es c a l ec a na l m o s tf i n da l lp a r a l l e lp a t h sb yt h ep r o b a b i l i t yo f g r e a t e r t h a n9 9p e r c e n ti nc e r t a i nt i m ec o m p l e x i t ya n dt h ee x i s ts h o r t e s tp a t hi s i n c l u d e di nt h e m k e yw o r d s ：s t a r n e t w o r k ；r e l i a b i l i t ya n df a u l tt o l e r a n c e ；n o d e l i n k f a i l u r e ；m o d e lo ff a u l tt o l e r a n c e ；t w o - c o n n e c t i o np r o b a b i l i t y ；f a u l t t o l e r a n c e s e e k i n gp a t h i v 目录 摘要i a b s t r a c t i i i 第一章绪论1 1 1 论文的选题背景与意义1 1 2 国内外研究现状2 1 2 1 拓扑结构优化设计、分析研究2 1 2 2 可靠性分析、设计研究3 1 2 3 容错路由设计及容错性分析研究4 1 3 本文的主要工作5 1 4 本文的创新点5 1 5 本文的组织结构6 第二章s i a r 网络与其它互连网络的比较7 2 1s t a r 网络拓扑结构及其表示7 2 2s t a r 网络拓扑结构的性质8 2 2 1 有效性与容错性8 2 2 2 循环分解层次结构9 2 3s t a r 网络拓扑结构与其他互连网络拓扑结构的比较9 2 4 本章小结1 2 第三章具有失效链路的s t a r 网络可靠性分析1 3 3 1 一些符号及原理简述1 4 3 2 链路失效概率模型下的可靠性分析1 5 3 2 1 基于p i e 的可靠性分析1 5 3 2 2 近似的可靠性分析1 8 3 3 链路失效概率模型下的非p i e 可靠性分析1 9 3 4 实验结果及对比分析2 1 3 4 1 实验结果2 1 3 4 2 对比分析2 2 3 5 本章小结2 4 第四章基于网络二连通率的s t a r 网络全终端可靠- 性分析2 5 4 1 准备工作2 6 4 2 自适应的容错并行路由算法2 6 4 2 1 算法提出2 6 v 4 2 2a f t p r a 算法性质的分析2 7 4 3 贝叶斯网的建立和参数设置2 8 4 3 1 贝叶斯网的建立过程2 8 4 3 2 参数的设定3 0 4 4 方法演示及仿真分析3 1 4 5 本章小结3 3 第五章s t a r 网络的容错寻径算法研究3 4 5 1 相关定义3 4 5 2 自适应规则及容错寻径算法3 5 5 2 1 自适应规则3 5 5 2 2 基于自适应规则的容错寻径算法3 6 5 3f t s p a b a r 算法的理论分析3 7 5 3 1 复杂度分析3 7 5 3 2 正确性分析3 8 5 4 实验结果及性能分析3 9 5 5 本章小结3 9 第六章总结及展望4 0 6 1 工作总结4 0 6 2 进一步的工作及展望4 0 参考文献4 1 致谢4 6 攻读硕士学位期间参与的科研项目4 7 攻读硕士学位期间完成的学术论文4 8 v l 广西大学硕士掌位论文基于s t a r 网络的可靠性与容错性分析 1 1 论文的选题背景与意义 第一章绪论 现在社会已经进入了一个i t 信息化的社会，人们在现实生活中面临的信息领域、 信息内容、信息容量等诸多方面都已经达到了一个前所未有的深度与广度，同时人们 在现实生活、学习、工作中所面临的各种科学计算问题、信息处理问题也越来越复杂， 困难。对个人而言如此，从整个国家的角度来看，也是如此，当今社会国内外的形势 越来越复杂，各个国家在科技、信息处理、通信、网络搭建与优化等领域的竞争也越 来越激烈，这其中高性能计算机的研发水平和应用水平已经成为一个国家综合国力和 科技发展水平的重要标志之一。 高性能计算机是为应对复杂的科学计算以及信息处理所开发研制的一种计算机， 从最初巨型机i l l i a ci v 的问世，到后来的s i m d 阵列机的出现，再到p v p 向量机 的诞生，它的发展是一个长期的过程。八十年代初期，高性能机器的研制方向出现了 分歧，一种是继续向单个的、高容错的、高可靠性的、更高数量级以及更完备指令集 的高性能处理器发展，另一种是向并行计算机( 处理器) 系统发展，即利用某种通信 子系统将各种具有协同处理能力的部件连接起来，构成一个大的并行计算机系统，从 而实现复杂大型问题的解决。目前由于技术条件的限制，使得并行计算机( 处理器) 系统在与前者博弈中处于优先发展地位，各个国家都纷纷加强对并行计算机( 处理器) 系统的研制工作，如美国的h p c cp r o g r a m 、日本的r w cp r o g r a m 、欧洲的 t e r a f l o p sp r o g r a m 等。在我国，主要是银河系列计算机以及曙光系列机 d a w n i n g 一1 、1 0 0 0 、- 1 0 0 0 a 、- 2 0 0 0 i 的研制，目前也处于国际领先地位。有专家 指出，并行计算机系统仍将是未来数年高性能计算机的主要方向。 目前，对并行计算机( 处理器) 系统来说，不管是其体系结构还是其有关并行算 法，在满足实际应用需求方面仍存在不足，有待提高。实际上，并行计算机( 处理器) 系统体系结构对通常意义上的计算机体系结构进行了扩展，这主要体现在通信体系结 构的扩展上。并行计算机体系结构的核心是通信体系结构，而通信体系结构的核心则 是并行计算机( 处理器) 系统互连网络。互连网络是指由若干个计算机( 或处理器等 网络组件) 按照一定的连接方式相互连接而成的网络，在这样的网络中，计算机( 或 处理器等网络组件) 都有自己的存储装置与资源，彼此间通过通信线路或者特定通信 手段进行连接，并进行信息的传递以及任务的协同完成。由于互连网络的研究在并行 与分步式计算机、计算机网络与通信、算法设计与分析、系统可靠性与容错性等方面 都起着非常重要的作用，所以它已经成为当前的热点之。目前的互连网络拓扑结构 主要有r i n g ，t r e e ，s t , m 乇，m e s h ，t o r u s 和h y p e r c u b e 等，其中s t a r 、 基于s t a r 网络的可靠性与容错性分析 m e s h 、h y p e r c u b e 是目前研究和应用最广的三种结构，一些相应的商用或研究用 的并行计算机( 处理器) 系统，如9 9 0 s t a r 1 、i n n ! l p s c 2 、n c u b e 1 0 、i i i l a c 、 c 凡“t 3 d 以及国内的曙光系列机d a w n i n g 1 等，都已经出现。 s t a r 网络是一种提出的比较早的高性能并行计算机( 处理器) 系统网络拓扑结 构。它具有很多的优点，比如h i e r a r c h i c a l 结构、结点和链路对称、直径短、顶点度 比较小、连通性高、路由算法比较简单等等，而且它还能够容纳更多的处理器，拥有 较少的通信延迟、较强的容错性以及强壮的恢复力，因此成为目前最有吸引力和最重 要的网络模型之一【1 弓2 0 2 2 3 6 - 3 8 , 5 6 - 5 8 , 7 2 - 7 5 1 。但是近年来，随着系统的规模越来越大，事务 越来越复杂，海量信息的扩展，再加上人为和硬件软件上的因素，使得以s t a r 等互 连网络为网络模型的系统变的越来越不稳定，一些网络结点和链路会出现这样那样的 问题，从而进一步影响了网络的可靠性，同时，这些故障的存在也会对网络终端间的 有效通信产生一定的影响，显然，为了实现终端间信息的顺利传送，必然要求此时的 网络仍要具有一定的容错性。 互连网络可靠性以及容错性研究是目前系统科学领域比较重要的研究分支。可靠 性理论主要研究的是在一定的网络元件失效概率的情况下，网络具有原规定功能的能 力，反映为概率值。但是当故障出现的时候，网络的整体性能会受到影响，这是无法 回避的，所以也有一些学者将网络的可靠性理解为在网络元件出现故障的情况下，网 络中仍然存在着与原网络具有相同功能的局部子网结构的可能性，也反映为概率值。 而网络的容错性研究主要针对的是在故障存在的情况下，如何保证互连网络中无故障 网络元件之间进行可靠的信息传送。一般而言，网络的容错度越高，容错性也越好， 同时网络的性能也就越好。这当然也就涉及到网络的容错路由问题，之所以这么讲， 那是因为可靠而且高效的路由算法对于信息的可靠、高效传送是至关重要的。 综上所述，本课题在综合比较、分析相关互连网络各自优缺点的基础上，以s t a r 互连网络为网络模型，在考虑网络元件可能出现的故障情况下，对网络的可靠性、容 错性以及容错路由算法进行了分析研究。在当前这个信息技术、计算机网络与通信技 术、计算技术迅猛发展的情形下，该课题在一定程度上解决了目前合理评估网络可靠 性乏力、缺乏实际可行方法、针对性不强、系统容错性能不高、寻径不充分等方面的 问题，在理论完善以及实际应用等方面都具有非凡的意义。 1 2 国内外研究现状 目前，对于互连网络可靠性以及容错性方面的研究主要集中在拓扑结构优化设计， 网络可靠性分析、设计，以及网络容错路由、容错性分析等方面。 1 2 1 拓扑结构优化设计、分析研究 近些年来，学者们寻找更加适合并行计算机( 处理器) 系统的网络拓扑结构的努 2 广西大学硕士掌位论文基于s t a r 网络的可靠性与容错性分析 力一直没有停止过。文献 4 1 0 】对立方体网络的基础结构及其变形结构进行了相关的 研究，给出了立方体网络到超立方体网络、再到广义超立方体网络等特殊变形结构的 优点和一些特性，如冗余结点及冗余链路的存在等，并结合在并行计算机系统方面的 实际应用需要，比如说更加适合网络容错的需要、高效率路由算法的实现等，进一步 探讨了立方体网络模型的优化结构。文献 1 1 1 9 】对m e s h 网络极其变形结构进行了研 究，由于m e s h 网络在网络直径、对剖宽度等方面存在诸多的不足之处，因此这些学 者在保持原网络结构及其良好性能特点的基础上不断地对它进行扩展、升级、优化， m e s h 网络从最初的二维结构到现在的3 维、多维，直至e 2 d 3 dm e s h 结构，在高可 靠性、高容错性、高效路由等方面已经逐步满足了现在的需求。由于s t a r 网络是并 行计算机系统早期重要的互连网络拓扑结构之一，也一直备受学者的关注。文献 2 0 ，2 2 】 对s t a r 网络进行了介绍，并与立方体进行了比较，指出了其在结点度、直径、操作 性等方面立方体所不具有的适合并行计算机系统的优点与特性。文献【2 1 ，2 3 2 5 1 对 s t a r 网络的容错性进行了分析、研究，给出了其适合并行计算机系统的容错特性， 但随着高性能并行计算机系统的不断发展，原有结构的一些缺点，如扩展性不太理想 等，逐渐地暴露出来，科研工作者们为了研制出进一步适合系统发展需求的互连网络 模型，在文献 2 6 2 8 中，又提出了组合星形的网络结构，该结构在容错直径，高效路 由等方面对满足系统需要有一定的优越性。 1 2 2 可靠性分析、设计研究 在可靠性分析、设计方面，并不局限于互连网络的研究，因为不同网络的研究成果 可以相互借鉴。有些学者通过神经网络的方法来对网络系统进行可靠性的评估及设计， 如在文献 2 9 中，作者提出了用神经网络估计网络系统可靠性的方法，该方法利用网络 相关参数对神经网络模型进行训练，得到误差在可允许范围内的神经网络模型，然后将 此模型用于相关网络的可靠性评估之中。文献 3 0 】对基于神经网络模型的系统可靠性分 析方法进行了比较，并建立了一种基于样本筛选的神经网络可靠性分析方法，该方法进 一步提高可靠性分析的精度。还有一些学者通过可靠性分析算法来对网络的可靠性进行 分析，在文献【3 l 】中作者建立了一种对具有不可靠结点的分布式网络进行可靠性计算的 算法，文献 3 2 】中作者对网络的k 一终端剩余连通可靠度进行了研究，并提出了一种基于 r v r 的蒙特卡洛算法，还有在文献 3 3 】中作者提出的针对两个特定网络o r c 2 网络和i r c 2 网络的可靠性算法等，这些算法一般都能编程实现，不失为可靠性网络分析、设计时的 良好手段。再有，c h e n gj i n 等人在基于遗传算法的神经网络的基础上，对结构系统的可 靠性进行了分析，提出了一种用于可靠性评估的新模型m 】，刘东等人对多阶段系统的可 靠性进行了研究，并建立了基于贝叶斯网的分析模型f 3 卯。这些方法各有各的优点，具 有一定的借鉴意义，比如文献 3 5 】中的分析模型是建立在数学语言的基础上，具有一定 的严密性，而文献【3 4 】中的方法则是具有一定的智能性。另外，一些学者提出了基于马 尔柯夫链模型的网络可靠性分析方法【_ 7 6 。1 7 8 】，它通过状态转移图的建立来对网络的可靠性 广西大掌硕士掌位论文 基于s t a r 网络的可靠性与容错性分析 进行分析，虽然该方法能够带来可靠性度量的准备结果，但它的高复杂性以及高计算量 严重制约了其在大规模网络上的应用。那么在s t a r 网络的可靠性分析、设计方面，文 献 3 6 3 7 分别从结点、链路失效的角度出发，对使得s t a r 网络中指定规模子网都失效所 应达到的结点、链路失效数量进行了分析，得到了具体的量化结果，这为严格地限制网 络故障率、提高网络的容错性提供了有效的约束依据。文献【3 8 】在节点失效概率模型的 基础上，对s t a r 网络中仍然存在着非失效子网的可靠性概率进行了分析。文献 3 9 】在比 较诊断模型的基础上对1 1 维的s t a r 网络的诊断能力进行了研究，得到了一个量化结果n 1 ， 该结果为我们判断s t a r 网络是否是可诊断的网络提供了一个依据。文献 4 0 】通过马尔可 夫链过程建立了s t a r 网络的m a r k o vr e l i a b i l i t ym o d e l ，而文献 4 1 4 3 分别在链路失效模型 下对s t a r 网络的容错性进行了研究，这为进一步分析研究大规模集成电路技术下具有 故障链路的s t a r 网络可靠性提供了依据。 1 2 3 容错路由设计及容错性分析研究 k h a l e dd a y 等人一j 提出了一种用于群网络的统一标准的容错路由策略，该策略是 基于通信结点间有效的可以识别的不相交路径的可用性，如果当前路径失效，那么就 从备选的不相交路径中选择最优或接近最优的路径。k h a l e dd a y 等人将这种策略应用 于s t a r 网络等一些满足一定连通度要求的规则网络中，得到了很好的效果。文献【4 5 】 对s t a r 网络的容错广播算法进行了研究。在文献 2 4 2 5 】中，q i a n p i n gg u 等人提出 了几种基于s t a r 图的点到点的群容错路由算法，这些算法充分考虑了错误群对路由的 影响，经作者的理论与实验的证明，不失为一个好的容错路由算法。文献 4 6 】对具有 失效结点的s t a r 网络中的由正确结点构成的路径进行了研究，找到了一条最长的正 确路径。文献 4 7 】对组合星图中的一对一容错路由算法进行了研究，文中提出的算法 可以在o ( n ) 内找到一条长度不超过d ( s 以) + 4 的路。我们知道路径算法必须要考虑其安 全性和有效性，而安全性研究的主要内容之一就是如何保障算法的无死锁性。死锁是 指系统在某一时刻存在若干信息因彼此等待网络信道资源而永远无法到达终点的情 形，因此我们说死锁也算是网络失效的一种。文献 4 8 ，7 5 】分别基于超立方体、s t a r ， 给出了满足两类最小无死锁受限条件的无死锁路径算法。高峰等人基于扩展安全向量 的概念设计了超立方体网络中的容错路 4 9 1 。随后，田绍槐等又基于扩展安全向量和 最优通路矩阵提出了扩展最优通路矩阵【5 0 】的概念并对超立方体网络中的容错路由算 法进行了进一步的改进。有关广播路由算法，1 9 9 5 年b a o 、i g a r a s h i 和k a t a n o 基于随 机分布的b y z a n t i n e 错误类型( 含结点错误和链路错误) 设计了两个所有结点到所有 结点间的广播容错路由算法【5 1 1 。而对于m e s h 网络的容错路 扫 1 1 - 1 3 , 1 7 , 1 9 , 5 2 - 5 5 】，学者们大 多会采用以下模式或限制方法：第一，错误块模型下虚通道的技术；第二，平面路由 策略下的自适应路由；第三，界限模型以及概率模型下的容错性概率限制；第四，子 网的划分及基于子网连通的路由。这些方法在不同的应用环境下有各自的特色和优 势，但在统一的应用范畴下仍然有一些值得改进的地方。比如，在使用虚通道时，结 4 广西大掌硕士掌位论文基于s t a r 网络的可靠性与容错性分析 点缓冲空间的节约、逻辑控件的简单化、错误块的非实心性和跳跃性等，还有一些如 自适应规则的改进、网络元件的相关性应用、使用子网和概率模型时系统构件之间的 关联考虑等。另外，近些年来子网及概率性容错分析在s t a r 、立方体以及m e s h 网 络中广泛展开【1 5 - 1 7 + 1 9 , 2 3 , 3 5 - 3 8 5 3 5 5 , 6 0 侧。 鉴于以上所述，在本文中，我们将借鉴其它互连网络在可靠性分析、设计，容错 路由及容错性分析等方面的优点，有针对性地对s t a r 网络的可靠性分析、设计，容 错路由及容错性分析进行探讨，研究，以求有所突破与创新。 1 3 本文的主要工作 本文在综合分析、比较各典型互连网络模型的基础上，对s t a r 网络模型的可靠 性以及容错性进行了分析，在可靠性分析以及容错性分析的时候，借鉴了用于其它互 连网络模型的可靠分析以及容错分析方面的方法，比如子网划分以及概率模型的方法 等，同时，对s t a r 网络的容错寻径算法进行了研究，具体包括以下几部分的工作： ( 一) 给出了s t a r 互连网络的定义、特性、拓扑结构，并与目前比较流行的其 它互连网络拓扑结构进行了对比、分析，综合对比了彼此的优缺点，给出了本课题选 择s t a r 网络作为并行计算机系统网络模型来进行研究的理由。 ( 二) 研究分析了s t a r 网络在链路失效独立和结点失效独立情况下的网络可靠 性，指出了现有方法存在的一些不足。对网络元件存在失效的情况下网络中仍然存在 满足具有整体网络结构、可以实现原有网络结构性能、达到并行计算机系统要求的局 部子网结构的概率进行了分析、研究，给出了以此为指标的网络可靠性的具体数学模 型，由此进一步实现了网络可靠性的定量分析。 ( 三) 研究分析了故障存在情况下的s t a r 网络的全终端可靠性，首先提出了一 个自适应的容错并行路由算法，通过该算法的多次执行，得到用于计算网络二连通率 的相关条件参数，在此基础上建立了用于推断网络二连通率的贝叶斯网模型，然后通 过基于贝叶斯网的概率推理，得到了反映网络可靠性的网络二连通率，由此进一步实 现了网络的全终端可靠性的定量分析、判断。 ( 四) 研究了独立故障存在情况下的s t a r 网络容错寻径算法，提出了一个具有 一定自适应性的寻径算法。对提出的这个算法在多方面的性质进行了分析、证明，并 进行了相应的仿真实验，实验结果表明，该算法具有很强的容错性。 1 4 本文的创新点 本文的创新工作主要体现在以下三个方面： 1 链路独立失效故障下的s t a r 网络可靠性的定量分析方法的提出，与结点失 效故障下的s t a r 网络可靠性的分析结果的对比研究。 基于s t a r 网络的可靠性与容错性分析 2 s t a r 网络二连通率的提出以及以此为指标的网络全终端可靠性的定量分析方 法的提出。 3 自适应规则及容错寻径算法的提出以及其容错性的分析、比较。 1 5 本文的组织结构 本文的组织结构大致如下： 第一章绪论 介绍了论文的选题背景及意义：全面阐述了本课题相关的国内外研究现状；介绍 了本文的主要工作及创新点。 第二章s t a r 网络与其它互连网络的比较 介绍了互连网络的典型网络拓扑结构，并进行了对比分析，给出了本文选择s t a r 网络作为并行计算机( 处理器) 系统网络模型的理由。 第三章具有失效链路的s t a r 网络可靠性分析 在链路失效概率模型的基础上，分别采用不同的分析方法对s t a r 网络的可靠性 进行了分析，建立了相应的可靠性模型。这些可靠性模型指出了链路可靠性与网络可 靠性之间的约束关系，并与结点独立失效概率模型下的网络可靠性进行了对比分析， 进而说明了本章工作的必要性及创新性。 第四章基于网络二连通率的s t a r 网络全终端可靠性分析 针对具有故障部件的s t a r 互连网络的可靠性问题，在有条件的容错模型和概率 模型的基础上，提出了一种新的评估s t a r 网络全终端可靠性的方法。 第五章s t a r 网络的容错寻径算法研究 基于自适应规则提出了一个容错寻径算法。理论推导以及仿真实验都说明了它具 有较高的可行性、优越性、正确性，并对其进行了容错性的分析。 第六章总结及展望 对本文的工作进行了总结，对以后可能继续开展的研究工作进行了展望。 6 广西大掌硕士掌位论文 基于s t a r 网络的可靠性与容错性分析 第二章s t a r 网络与其它互连网络的比较 2 1s t a r 网络拓扑结构及其表示 单向互连网络拓扑结构是并行计算机( 处理器) 系统以及高速计算网络系统中重 要的网络拓扑结构，s t a r 网络拓扑结构便是其中之一。由图论的知识，n 维s t a r 网络拓扑结构可以用一个图g n ( v e ) 来表示，记做s n ，其中v 表示结点集，e 表示链 路集。n 维s t a r 图是由n ! 个结点构成的一个无向图。结点集是由从1 到n 的这n 个自然数的所有置换所构成，即v ( s n ) = x 1 x 2 x n ix i x j ，1 7 时， 为l _ 3 n - 3l + 2 ：当萨4 ，6 时，为i 下3 n - 3l + 3 。 l z jl z j 宽直径【1 0 , 5 9 】：给定宽度c o ，( 两个结点之间宽度为缈的某个容器的长度是指所有并行路 径中长度最大值；两个结点之间的宽缈距离是指所有宽度为w 的所有容器长度的最小 值) 图g 中任意两点间的宽缈距离的最大值。由于宽直径很好地将连通度和直径结合起 来，因而与单独的某个参数相比，它能更好地对互连网络的容错性和性能效率进行衡量， 基于此，在实时处理系统中，宽直径是衡量网络优劣的一个重要参数。 限制( 边) 连通度【5 7 l ：所有限制( 边) 分离集中的最小阶数。有s t a r 网络的限制连通度及 广西大掌硕士掌位论文基于s t a r 网络的可靠性与容错性分析 限制边连通度均为2 n - 4 ( n 4 ) 。 点到点并行路径数f 5 8 】：网络中指定的两个不同点间的不相交路径个数。有s t a r i 网络的 并行路径数为n 1 。 点到多点路径数 3 5 s 】：网络中给定的固定点与其他n 1 个不同点，可以构造n 1 条不相交 路径连接该固定点到其他n 1 个不同点。 s t a r 网络的鲁棒性【3 6 - 3 7 】：使得网络中所有的n k 阶子网都存在失效的失效结点数或失效 链路数。因为k = l 和k = 2 为实际中常碰到的两种分析状态，所以以此为例有s t a r 网络的 如下的结果( n 3 ) ： 失效结点数：k = l 时为n ；k = 2 时若n 为质数为n ( n 1 ) 否则小于等于n ( p 1 ) ，其 中p 为大于等于n 的质数。 失效链路数：k = l 时为n + 2 ：k = 2 时小于等于( n - 1 ) n ( p - 1 ) ，其中p 为大于等于n 的最 小质数。 2 2 2 循环分解层次结构 在g 。，e ) 中，将v 以第n y u 上不同的元素为准，划分成分属于不同子网的结点集合， 记为v j m x i x 2 x 3 x i 1 x i x i + l x n 2 k d l l _ j g ，无重复的x k -