（计算机应用技术专业论文）mesh网络容错性的概率分析研究.pdf

摘要 m e s h 嘲络是迄今为止最为罩要和最具吸引力的并行计算机系统网络拓扑结 构之。本文提出全新的基丁概率模型研究m e s h 网络的容错性问题的理论，捉 了k - m e s h 子网结构的方法，本文基于k - m e s h 予网结构研究了二维雨1 t 维m e s h 网络的容错性，并基于k - m e s h 予网结构提出了高效的二维和三维m e s h 网络单播 和广播容错路由算法，从概率的角度分析了各种算法的有效性。 本文首先在每个结点具有独立的出错概率的情形下研究m e s h 网络的容错性， 提出基于k - m e s h 予网结构的概念：即k - m e s h 子网连通性。证明了当网络结点出 错概率给定r 寸，随着网络规模的增加，m e s h 网络的连通概率将任意地趋向无穷小。 因此，对于以m e s h 网络为拓扑结构的并行计算机系统的研究者和制造商提出一个 实际而重要的课题：当网络连通概率和网络规模给定时，网络结点的出错概率的 、| 界应控制在多大的范围之内。本文严格推导出m e s h 网络的连通概率的个下 界。研究结果表明实际规模的以m e s h 网络为拓扑结构的并行计算机系统是能容许 相当多的出错结点的，因此也是相当可靠的。研究结果也表明了三维m e s h 网络有 优于其它流行的网络拓扑结构的优势。与规模相当的二维m e s h 网络相比，三维 m e s h 网络在保持较高的连通概率的同时能容许更多的网络结点出错。而与规模相 当的超立方体网络相比，三维m e s h 网络在保持较高的连通概率的同时享有更低的 结点度。 本文基于k - m e s h 子网结构提出了基于局部信息的和分却式的二维和三维 m e s h 网络单播容错路由算法。因为容错路由算法是基于k - m e s h 子网结构设计的， 所以本文从概率的角度研究了单播容错路由算法的有效性，推导出容错路由算法 的成功概率。本文运用严格的数学推理，证明了二维m e s h 网络结点出错概率只要 控制在1 8 以内，则对于多达2 5 0 0 0 0 个结点的二维m e s h 网络，路由算法具有 9 9 的概率确保找到正确结点组成的路径。当结点出错概率不大于25 时，即使 对于规模达到3 7 3 2 4 8 个结点的三维m e s h 网络，路由算法仍具有9 9 ( 3 4 3 成功概率。 路由算法的时间复杂性是线性的，模拟结果表明路由算法所构造的路由路径长度 非常接近于两结点之间的最优路径长度。 第1 页 本文基于k - m e s h 子网结构提出了、基于局部信息的和分布式的二维和三维 m e s h 网络广播容错路由算法，并对其容错性进行概率分析。基于独立的结点出错 概率，本文推导出广播容错路由算法成功的概率，理论结果表示广播容错路由算 法能容许相当多的错误结点，通过模拟结果验证了广播时间步是接近最优的。 本文提出的单播和广播容错路由算法只要求结点知道它的邻结点的状态，而 无需知道整个网络信息，也就是说，这些算法是基于局部信息的；另外，算法在 路由过程中，都由各子网独立完成路由操作而不需考虑算法在其它子阕中操作的 状态，所以，算法是高度分布式的。因此提出的算法具有很好的实际意义。这些 容错路由算法不仅从不同侧面证明了提出的容错模型的合理性和有用性，而且表 明提出的容错路由算法具有很好的理论价值和实用价值。提出的概率分析方法在 确定网络容错模型和网络容错路由算法的容错概率的下界时具有普遍意义，该方 法也能够用于研究其它层次结构的网络和其它的网络通信问题。 关键词：互联网络，m e s h 网络，容错性，容错模型，容错路由算 法，概率分析 第1 i 页 a b s t r a c t m e s hn e t w o r kt o p o l o g yi so n eo ft h em o s ti m p o r t a n ta n da t t r a c t i v en e t w o r kt o p o l o g i e si np a r a l l e lc o m p u t e rs y s t e m ss of a r i nt h i st h e s i s ，w es t u d yt h ef a u l tt o l e r a n c e o fm e s hn e t w o r k su n d e rap r o b a b i l i s t i cm o d e la n dp r o p o s ean e wc o n c e p tc a l l e d k - s u b m e s hs t r u c t u r ei nt w o - a n dt h r e e d i m e n s i o n a lm e s hn e t w o r k s w h i c hb u i l d st h e b a s i so fo u rp r o p o s e df a u l tt o l e r a n tm o d e l s ，a n dw ep r o p o s es i m p l ea n de f f i c i e n tf a u l t t o l e r a n tu n i c a s ta n db r o a d c a s tr o u t i n ga l g o r i t h m sa n da p p l yp r o b a b i l i s t i ca p p r o a c ht o v a l i d a t i n gt h ep r o p o s e dm o d e l sa n da l g o r i t h m s t h et h e s i ss t u d i e st h ef a u l tt o l e r a n c eo fm e s hn e t w o r k su n d e ram o r er e a l i s t i c m o d e li nw h i c he a c hn e t w o r kn o d eh a sa ni n d e p e n d e n tf a i l u r ep r o b a b i l i t ya n di n t r o d u c e sk - s u b m e s hc o n n e c t i v i t yb a s e do nt h ec o n c e p to fk - s u b m e s hs t r u c t u r e w ep r o v e t h a t i ft h en o d ef a i l u r ep r o b a b i l i t yi sf i x e d ，t h e nt h ec o n n e c t i v i t yp r o b a b i l i t yo fm e s h n e t w o r k sc a l lb ea r b i t r a r i l ys m a l lw h e nt h em e s hn e t w o r ks i z ei ss u f f i c i e n t l yl a r g e t h u s i ti sp r a c t i c a l l yi m p o r t a n tf o rm u l t i c o m p u t e rs y s t e m sm a n u f a c t u r e rt od e t e r m i n et h e u p p e rb o u n df o rn o d ef a i l u r ep r o b a b i l i t yw h e nt h ep r o b a b i l i t yo fn e t w o r kc o n n e c t i v i t y a n dt h en e t w o r ks i z ea r eg i v e n w ed e v e l o pn o v e lm e t h o d st of o r m a l l yd e r i v el o w e r b o n n d so nt h ec o n n e c t i v i t yp r o b a b i l i t yf o rm e s hn e t w o r k s o u rr e s u l t ss h o wt h a tm e s h n e t w o r k so fp r a c t i c a ls i z ec a nt o l e r a t eal a r g en u m b e ro ff a u l t yn o d e st h u sa r er e l i a b l e e n o u g hf o rm u l t i c o m p u t e rs y s t e m s w ea l s o s h o wan u m b e ro fa d v a n t a g e so f t h r e e d i m e n s i o n a lm e s hn e t w o r k so v e ro t h e rp o p u l a rn e t w o r kt o p o l o g i e sc o m p a r e dt o t w o d i m e n s i o n a lm e s hn e t w o r k s ，t h r e e d i m e n s i o n a lm e s hn e t w o r k sa r em u c hs t r o n g e r i nt o l e r a t i n gf a u l t yn o d e s ，w h i l ef o rp r a c t i c a ln e t w o r ks i z e ，t h ef a u l tt o l e r a n c eo f t h r e e d i m e n s i o n a lm e s hn e t w o r k si sc o m p a r a b l ew i t ht h a to fh y p e r c u b en e t w o r k sb u t e n j o y sm u c h l o w e rn o d ed e g r e e t h et h e s i sp r o p o s e se f f i c i e n tu n i c a s tr o u t i n ga l g o r i t h m sf o rt w o - a n dt h r e e - d i m e n - s i o n a lm e s hn e t w o r k sb a s e do nt h ec o n c e p to fk - s u b m e s h ，t h o s ea l g o r i t h m sa r ed 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 nb a s e dd u et ot h ef a c tt h a to u ra l g o r i t h m sa r ed e s i g n e db a s e d o nk - s u b m e s hs t r u c t u r e ，w ea p p l yp r o b a b i l i s t i ca n a l y s i so nt h ef a u l tt o l e r a n c eo fo u r 第1 i i 页 r o u t i n ga l g o r i t h m s s u p p o s ee a c hn o d eh a sa ni n d e p e n d e n tf a i l u r ep r o b a b i l i t y ，w ed e r i v et h ep r o b a b i l i t yt h a to u rr o u t i n ga l g o r i t h m ss u c c e s s f u l l yr e t u r naf a u l t f r e er o u t i n g p a t h o u ra l g o r i t h m sr u d i nl i n e rt i m ea n do t l rs i m u l a t i o nr e s u l t ss h o wt h a tt h el e n g t ho f t h er o u t i n gp a t h sc o n s t r u c t e db yo u ra l g o r i t h m sa r ev e r yc l o s et ot h eo p t i m a ll e n g t h t h et h e s i sd e v e l o p se f f i c i e n tb r o a d c a s tr o u t i n ga l g o r i t h m sf o rt w o - a n dt h r e e - d i m e n s i o n a lm e s hn e t w o r k sb a s e do nt h ec o n c e p to fk - s u b m e s hs t r u c t u r e t h e s ea l g o r i t h m sa r e d 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 nb a s e d s u p p o s ee a c hn o d eh a sa l li n d e p e n d e n tf a i l u r e p r o b a b i l i t y , w ed e r i v et h ep r o b a b i l i t yt h a to u rb r o a d c a s tr o u t i n ga l g o r i t h m ss u c c e s s f u l l y b r o a d c a s tam e s s a g ef o rag i v e ns o u r c en o d et oa l ln o n f a u h yn o d e s ，o u rr e s u l t ss h o w t h a tb r o a d c a s tt r e eb yo u ra l g o r i t h m sc a l lt o l e r a n tq u i t eaf e wf a u l t yn o d e s s i m u l a t i o n r e s u l t ss h o wt h a to u ra l g o r i t l n n sa r ep r a c t i c a l l ye f f i c i e n ta n de f f e c t i v e ，a n dt h et i m e s t e p so fo u ra l g o r i t h m sa r ev e r yc l o s et ot h eo p t i m a i n w ep o i n to u tt h a tt h e s eu n i c a s ta n db r o a d c a s tr o u t i n ga l g o r i t h m sh a v ep r a c t i c a l l y i m p o r t a n ts i g n i f i c a n c e o nt h eo n eh a n d ，o u ra l g o r i t h m sa r el o c a li n f o r m a t i o nb a s e di n t h es e n s e ，b e c a u s ee a c hn o d ek n o w so n l yi t sn e i g h b o r s s t a t u sa n dn og l o b a li n f o r m a t i o no ft h en e t w o r ki sr e q u i r e db yo u ra l g o r i t h m si nt h ec o u r s eo f r o u f i n g ，o nt h eo t h e r h a n d ，w h e nr o u t i n ga l g o r i t h m sa r er u n n i n gi ne a c hk - s u b m e s h ，t h i sk - s u b m e s hc a ni n - d e p e n d e n t l y f i n i s h r o u t i n go p e r a t i o n sa n d d o e s n tc o n s i d e r o p e r a t i o n s i no t h e r k - s u b m e s h ，s oo u ra l g o r i t h m sa r ed i s t r i b u t e db a s e d i na d d i t i o n ，o u ra l g o r i t h m sa r e v a l u a b l eb o t hi nt h e o r ya n di np r a c t i c e o u rs c h e m eh a sv e r yg e n e r a ls i g n i f i c a n c ef o r d e t e r m i n i n gl o w e rb o u n d so nt h en e t w o r kf a u l tt o l e r a n c ea n df a u kt o l e r a n tr o u t i n ga l g o r i t h m s o u rm e t h o di sa l s oa p p l i c a b l et os t u d yo fo t h e rh i e r a r c h i c a ln e t w o r ks t r u c t u r e sa n do t h e rn e t w o r kc o m m u n i c a t i o n p r o b l e m s k e yw o r d s ：i n t e r e o n n e c t i o nn e t w o r k s ，m e s hn e t w o r k s ，f a u l tt o l e r a n c e f a u l tt o l e r a n tm o d e l ，f a u l tt o l e r a n tr o u t i n ga l g o r i t h m ，p r o b a b i l i s t i ca n a l y s i s 第1 v 页 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致访，的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的剌料。与我共 同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。 作者签名：如日期：! 型年上月l 日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：越导师签名：隆日期：竺年旦月罩日 第。章绍论 第1 章绪论 本章首先介绍什么是m e s h 网络，然后介绍本课题的研究意义，然后分机m e s h 脚络容错模型、容锗路山算法及概牢方法在容销性方面的研究蚬状，然后介绍本 课题的研究内容和本文的主要创新点，最后是本文的组织结构。 1 1m e s h 网络简介 本节给出 维m e s h 网络m ，的定义和_ 维、三维m e s h 网络的定义，并对其 结构及相互关系进行分析。它们是贯穿本论文的基础。 定义1 1 ：m 维m e s h 网络) n 维m e s h 网络：k 元h 维( 一a r y 一d i m e n s i o n a l ) 的m e s h 网络( 简称m 维m e s h 网络) 是共有胪个网络结点，共有胛( 驴一胪。1 ) 条边， 内部结点的度为2 ，网络直径为n ( k - 1 ) 的网络。 n 维m e s h 网络中的每个结点“有一个地址：( “l ，2 ，u n ) ，这罩，“，( 0 1 ， 1 ) 对应j 二维西j ：结点 的位置。两个结点“：( l ，“2 ，) 和v ：( f i ，v 2 ，v n ) 相邻当且仅当有一个元素不同。 定义1 2 ：( 二维m e s h 网络) 二维m e s h 网络 厶。是由m 行 列构成，共有 m x n 个结点，其中结点按坐标狂，y ) 给出，x = 1 ，2 ，m ，y = 1 ，2 ， 。两个结 点相邻则它们的坐标值只有一维不同且差值为1 ，称这样两个结点为邻接结点。 图1t 是二维m e s h 网络的图例，图中有4 x 4 = 1 6 个结点和2 x ( 4 2 4 ) = 2 4 条边 其网络直径为6 。 定义1 3 ：( 三维m e s h 网络) 三维m e s h 网络 厶。q 构成一个立方体，共有 m x n x q 个结点，其中结点按坐标0 ，y ，z ) 给出，x = l ，2 ，m ，y = 1 ，2 ，”，z 2 1 ， 2 ，q 。两个结点相邻则它们的坐标值只有一维不同且差值为1 ，称这样的两个 结点为邻接结点。 图1 2 是三维m e s h 网络的图例，图中有4 x 4 x 4 = 6 4 个结点和3 x ( 4 3 4 2 ) = 1 4 4 条边，其网络直径为9 。 第1 页 博士学位论文第一章绪论 图1 1二维m e s h 网络 面d图1 2 三维m e s h 网络 毛4 很明显，二维m e s h 网络m 4 。是由4 个一维m e s h 网络通过将对应的结点用 一条边依次连接起来构成的。而三维m e s h 网络m 4 。4 。4 则是由4 个二维m e s h 网络 m 4 。t 通过将对应的结点用一条边依次连接起来构成的。由此，我们不难推断出四 维m e s h 网络m 4 。4 。4 。4 是由4 个三维m e s h 网络m 4 。4 。4 通过将对应的结点用一条 边依次连接起来构成的。一方面，基于m e s h 网络出现了相当多的其它m e s h 网络 的变形拓扑结构，因为我们的研究方法也可以扩展到其它变形结构上去；另一方 面，目前现已制造出的基于m e s h 网络拓扑的是二维和三维m e s h 网络。所以，本 文只对上述规则的m e s h 网络拓扑结构的容错性及容错路由算法进行研究。 1 2 课题的研究意义 自从2 0 世纪7 0 年代世界上首台巨型机i l l i a ci v 问世算起，高性能计算机发 展的历史到现在已经3 0 多年了。在此期间，出现了各种不同类型的并行机。大型 并行计算机系统一般可分为六类：单指令多数据流机s i m d ( s i n g l e h a s t r u c t i o n m u l t i p l e d a t a ) 、并行向量处理机p v p ( p a r a l l e lv e c t o rp r o c e s s o r ) 、对称多处理机 s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) 、大规模并行处理机m p p ( m a s s i v e l yp a r a l l e l p r o c e s s o r ) 、工作站集群c o w ( c l u s t e ro fw o r k s t a t i o n ) 、和分布共享存储d s m ( d s t r i b u t e ds h a r e dm e m o r y ) 多处理机。巨型机从s i m d 的阵列机，发展到p v p 的向量机，它们曾经是高性能计算领域的杰出代表，但现在已被8 0 年代初兴起的 并行计算机系统取代。现在流行的并行计算机系统主要有四种：s m p 、m p p 、c o w 和d s m 。对并行计算机来说，无论是在并行计算机系统体系结构方面还是在并行 算法方面，其发展水平都还相对比较低。因此，加强并行计算机系统体系结构和 第2 页 博士学位论文 第一章绪论 并行算法的研究有助于加速该领域的发展。 高性能计算机领域的研究和发展水平是衡量一个国家的科技发展水平和综合 国力的重要标志。近年来，人类对计算机性能要求是无止境的，在诸如预测模型 的构造和模拟、工程设计和自动化、能源勘探、医学、军事以及基础理论等领域 研究中都对计算提出极高的具有挑战性的要求。美国、日本、欧洲各国政府都高 度重视高性能计算机领域的研究和发展。1 9 9 3 年美国的“高性能计算和通信计划 ( h p c cp r o g r a m ) ”，即美国总统科学战略项目；日本的“真实世界计算计划( r w c p r o g r a m ) ”，欧洲的“万亿次计算机计划( t e r a f l o p sp r o g r a m ) ”，其主要目标都是 研制万亿次量级的高性能并行计算机系统。美国1 9 9 6 年提出的更高性能并行计算 机系统的研究计划还有“加速战略计算创新计划( a s c i p r o g r a m ) ”和“千万亿次 计算机计划( p e t a f l o p sp r o j e c t ) ”。我国的高性能计算机的发展起步也比较早。国 内主要有国防科大银河系列( y h 1 ，y j 一2 ，y h 一3 和y h 一4 ) 计算机和国家智能机 中心的曙光系列( d a w n i n g l ，d a w n i n g 一1 0 0 0 ，d a w n i n g 一1 0 0 0 a ，d a w n i n g - 2 0 0 0 一i 和 d a w n i n g 3 0 0 0 ) 计算机等。国内的这些亿次，1 0 亿次，1 0 0 亿次，万亿次以至1 0 万亿次计算机的发展历程表明我国的高性能计算机的研究在全世界范围是很不错 的。 并行计算机系统体系结构是对通常意义上的计算机体系结构的扩展，即扩展了 通信体系结构。通信体系结构是并行计算机体系结构的核心，通信体系结构的核 心则是并行计算机系统互联网络。并行计算机系统互联网络的研究，主要包括并 行计算机系统互联网络的拓扑结构、基本通信操作、容错路由算法、交换方式和 流控机制等。并行计算机系统互联网络的研究是当今的一个研究热点。国内外现 已对各种主要的并行计算机互联网络拓扑结构如r i n g ( 环) ，t r e e ( 树) ，s t a r ( 星 型) ，m e s h ( 网孔) ，t o r u s ( 环绕) 和h y p e r c u b e ( 超立方体) 等进行了大量研究， 并且对其中的一些拓扑结构已研制出了相应的商用和研究用的并行计算机系统。 由于m e s h 网络拓扑结构结构简单、可扩展性好、容易实施、递归的结构及在很多 的并行计算应用中能约简消息的延时、网络通信能力的可扩展性等优点，深受研 究者和实践者的欢迎。而且，一些商用的并行计算机系统体系结构如i l l i a ci v 、 g o o d y e a rm p p 、t e r ac o m p u t e rs y s t e m 0 6 、i n t e lp a r a g o n i s 7 1 , i n t e lt o u c h s t o n ed e l t a 【6 l 】、 s t a r t f o r dd a s h 5 9 、m ta l e w i f e 吲、c r a yt 3 d 30 1 、b l u eg e n es u p e r c o m p u t e r 0 4 1 、 m a s p a r i o s , s 6 系列和国内的国家智能机中心的曙光系列机器等都采用了m e s h 网络 第3 页 博十学位论文第章绪论 拓扑结构作为处理机之问的互联网络结构。因此，本文主要对m e s h 网络进行研究。 n 一方面，作为火规模并行计算机系统研究中最为重要和最有吸引力的网络模型之 一，m e s h 网络不仅成为许多理论研究的基础模型，而且也是国内外许多并行计算 机系统所采用的拓扑。另一方面，随着计算机互联网络规模的扩大，某些结点出 错的可能也随之增加，研究m e s h 网络容错问题是这一领域中非常必要和重要课 题。因此，本课题无论从理论上还是从实践上都具有很强的研究意义。 1 3 国内外研究现状与分析 在并行计算机系统中，c p u 、存储器、i o 设备、网络接口等不同组成部分都 要通过互联网络彼此连接起来。互联网络根据网络距离可人致分为并行计算机互 联网络、局域网络、广域网络等。对称多处理机( s m p ) 、大规模并行处理机( m p p ) 、 分布共享存储多处理机( d s m ) 和工作站机群( c o w ) 等几种主要的并行计算机， 其核心都是并行计算机互联网络。随着并行计算机互联网络规模的不断扩大，并 行计算机互联网络的容错性及其研究变得越来越重要。 表1 】部分静态互联网络特性( 该表部分数据出自文献【1 2 0 ) 互联网络网络规模 度链路数网络直径 宽度对称 线阵列 2111否 _ 二维m e s h瓜x 矗4 2 ( x 一届) 2 瓜一1而否 二维m e s h狐瓶。瓶6 3 ( l 疳) 3 刘2 1v _ v 2 否 星形m 1 l 12 l n 2 j 否 二义树 3- 12 1 1 0 9 一1 )1否 超立方体 = 2 ”n n 乜 2是 在并行计算机系统的互联中，互联网络可以分成两大类。一种是静态互联网络： 是指处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点链接是 保持不变的。另一种是动态互联网络：是用开关单元构成的，可按应用程序的要 求动态地改变连接组态。典型的静态网络有线阵列、m e s h 网络、连接、超立方体 网络、立方环、洗牌交换网、星形网、蝶形网络等。典型的动态网络包括总线、 交叉开关和多级互联网络等。 在表1 1 中，为网络的总结点数。胛为超立方体网络的维数。结点度：是指 第4 页 博十学位论文 第一章绪论 出或入一个结点的边数。网络直径：是指网络中任意两个结点之l 、日j 的最长距离 即最大路径数。对剖宽度：是指对分网络各半所必须移去的最少边数。对称性 如果从任意结点看嘲络都一样，则该网络为对称的。 本文对一种常见的并行计算机系统互联网络m e s h 网络进行广泛深入的 研究。m e s h 嘲络是大型并行计算机系统研究中最为重要和最有吸引力的网络模型 之一。与其它的网络模型相比，m e s h 网络有其特殊的优势，如它的结构简单、规 则及良好的扩展性，易于v l s i 实现。例如，与另一种常用的并行计算机系统拓扑 超立方体网络相比，一方面，从结点的度来看，m e s h 网络结点的度相当低( 如一 维m e s h 网络中结点的度为4 ) ，而超立方体网络结点的度是随结点数( 或维数) 的增加而增加的。因此，从制造技术上柬说，m e s h 网络比超立方体网络更容易实 现。另一方面，从扩展性方面来看，当网络需要增加结点时，超立方体网络只有 通过增加维数来增加结点的数目，而当维数增加时，将会引起每一个结点与其它 结点通信的端口数增加，m e s h 网络结点的度则是固定的，当需要增加结点时，只 是相应的边缘上结点的度发生了改变，并不影响到其它结点问的通信。所以，m e s h 网络不仅成为许多理论研究的基础模型，而且也是许多并行计算机系统所采用的 拓扑。如前所述的一些已经生产出来的并行计算机系统t e r ac o m p u t e rs y s t e m 、i n t e l p a r a g o n 、s t a n f o r dd a s h 、m i ta l e w i f e 、c r a yt 3 d 、b l u eg e n es u p e r c o m p u t e r 、 m a s p a r 系列和国内的国家智能机中心的曙光系列机器等都采用了m e s h 网络拓扑 结构作为处理机之间的互联网络结构。在并行计算机系统中，网络拓扑、交换技 术、路由算法和路由器结构是对系统性能影响最为重要的因素。在具体介绍本文 所做的m e s h 网络研究内容之前，这里对近年来有关m e s h 网络的国内外研究现状 和水平从m e s h 网络拓扑结构、m e s h 网络容错模型、m e s h 网络容错路由算法和 m e s h 网络容错模型和容错路由算法的概率分析研究等几个方面进行综合评价和 分析。 1 3 1m e s h 网络拓扑结构的研究 网络拓扑定义了网络中结点连通的方式，包括结点度、链路数、网络直径、 对剖宽度和网络是否对称等。理想的网络拓扑应该具有较小的结点度和网络直径， 围绕这一目标，各种各样的拓扑结构被提出。 m e s h 网络拓扑结构是最早提出的网络拓扑结构之一，由于结构简单、可扩展 第5 页 博士学位论文第一章绪论 性好、容易实施、递归的结构以及在很多的并行应用中能减少消息的延时、网络 通信能力的可扩展性等优点而深受研究人员和实践者的欢迎。但是，人们也发现， m e s h 网络在网络直径、对剖宽度上存在诸多的不足之处，要设计和实现高维的 m e s h 网络以及对m e s h 网络进行扩展( 升级) 则仍存在一些问题。因此，一些研 究人员和实践者提出了多种m e s h 网络的变型。下面对现已提出的一些主要的 m e s h 网络的变型或扩展进行介绍。 b h u y m a 和a g r a w a l 提出了g h c 网络( g e n e r a l i z e dh y p e r c u b e ) 。g h c 网络可 以看作是m e s h 网络的推广，它包含了r i n g ，h y p e r c u b e 和m e s h 等一大类拓扑结 构，其直径与度的乘积较小，并且具有较强的容错能力。 ”一维t o r u s 网络的定义类似于”维m e s h 网络，但它的连通性要好于m e s h ， 共有胪网络结点。与m e s h 网络不同，t o r u s 网络为边结点提供了绕边，即对应的 边结点也通过链路连通起来，所以，t o r u s 网络的每个结点的度都是2 n ，其网络直 径为n ( k - 1 ) 2 ，网络的对剖宽度为2 矿，图1 3 中给出一个二维的t o r u s 网络t 4 5 。 理论上，从结点度、网络直径和对剖宽度来说，高维m e s h 和t o r u s 网络更应该受 到欢迎。但实际上，由于工程上的限制，例如网络范围( 或容量) 和链路带宽却 成为主要的障碍。因此，山维的m e s h 和t o r u s 网络在实际中并不多见。 。 一 ，f 巡 i | - ji 1 一 。 这 ，一、l 。对1 d“ ，一 j 一 巡01弋 图1 3 二维的t o m s 网络矗。5 图l4_ 二维的i l l i a c 网络厶5 如c r a y t 3 d 、c r a y t 3 e 则采用三维的t o r u s 网络，而i n t e l s a n d i a o p t i o n r e d 则采用s p l i t 二维m e s h 。 另一种基于m e s h 的变形网络是i l l i a c 网络，如图1 4 中给出一个二维的i l l i a c 网络厶x 5 0 它是在垂直方向上带环绕，而在水平方向上呈蛇状。所以，i l l i a c 网络 第6 页 博十学位论文第章绪论 的结点度也恒为2 甩，网络直径为1 ，而对剖宽度为2 。 基于树的网络能获得对数级的网络直径，但其对剖宽度只有l ，所以，网络中 的数据传递相当困难。因此，基于二叉树的网络：m e s h 树( m e s h o f - t r e e ) 网络 被提出。它是通过在m e s h 网络的每行和每列顶端置入棵二叉树获得，这样可以 提供更大的对剖宽度，从而解决网络带宽问题。 考虑到大规模并行计算机系统的网络延时及为了连接更多的网络结点，有的研 究者把传统的互联网络中的点和边的功能进行互换，得到一种新的网络拓扑结构， 称之为反图拓扑( i n v e r t e d g r a p ht o p o l o g y ) 结构。基于m e s h 和t o r u s 网络，文献 1 4 4 1 中提出大规模并行计算机系统中的新的互联网络( n i n ) ，并对其进行理论分 析和模拟测试。结果表明该新型网络县有较短通信延时和较高的吞吐率，同时又 增加网络结点的连通性。 前面已经指出，要设计和实现高维的m e s h 网络以及对m e s h 网络进行扩展( 升 级) 仍存在一些问题。实际上，这一问题可能会随着微电子学和超大规模集成电 路技术的进步而得到最终解决。因此，本文仍然基于最先提出的m e s h 网络进行研 究，并且本文的研究方法和一些结论很容易扩展到高维m e s h 网络及m e s h 网络的 变形上去。 1 3 2m e s h 网络容错模型的研究 一些研究者现已提出了m e s h 网络上的多种网络容错模型，它们在容错性、简 单性、是否需要网络的全局状态信息等方面各有特点。有的容错模型只考虑结点 的容错性，有的容错模型只考虑边( 也称为链路) 的容错性，有的容错模型则同 时考虑结点和边的容错性。实际上，在结点容错模型中，边的错误可用连接该边 的两个结点中的任何一个出错进行模拟；在边容错模型中，结点的错误可用与该 结点相关的所有边出错进行模拟。更进一步，根据结点和或边错误的错误行为的 不同，还可以区分最常研究的两种错误类型：其一称为f a i l s t o p 类型( 也称为c r a s h 类型) ，即错误结点或错误边不能传输任何信息；其二称为b y z a n t i n e 类型，即错 误结点或边可能对传输经过该结点或边的信息进行任意的改变，甚至于捏造错误 的信息。容错模型在考虑对错误进行分类时，另一个很重要的特征是错误持续时 间的长短，根据此特征可将错误分为静态( 或永久性) 错误类型和动态( 或瞬态) 错误类型两类。下面是现已提出的一些m e s h 网络容错模型的简单介绍。 第7 页 博士学位论文第一章绪论 近年来，国内外学者在研究m e s h 网络容错路由算法时，提出了大量的容错模 型。c j + g l a s s 和lm n i 最先提出拐弯模型( t u r nm o d e l ) 1 4 7 - 5 0 1o 该模型通过分 析消息路由时拐弯的方向和拐弯形成的环，阻止一些环的产生，达到找到最小和 高度自适应性的路由。1 9 9 5 年，r l h a d a s 等提出一种基于原点( o r g i n b a s e d ) 的路由策略 5 3 。5 扪。在该方法中，任意一个结点被定为原点，其它结点坐标按位置 依次给出。并且，网络通道分为不相交的两个子网：入子网( i ns u b n e t w o t k ) 和 出子网( o u ts u b n e t w o t k ) 。该模型能在每维有k 个结点的n m e s h 网络上容许至 少( k - 1 ) ”个错误结点。 1 9 9 5 年，r v b o p p a n a 和s c h a l a s n i 提出最为典型的容错模型：错误块模型 ( f a u l t b l o c k m o d e l ) u i 。即所有的错误结点被包含在一些不相交的“矩形块”中。 后来，他们的研究小组又扩展了这一概念，包含的错误区可以是非矩形的实一i i , 的 错误块，如十字形、l 形、t 形等凸1 1 2 , 1 4 。 还有如a a c h i e n 和j h k i m 提出的平面路由策略【2 6 】；还有负优先路由 策略；j w u 提出基于安全向量的路由策略 1 0 7 , 1 1 0 , 1 1 1 ，d j w a n g 提出的最小连通 分量模型等j 。 尽管人们现己提出了多种m e s h 网络容错模型，但是它们的容错能力都相当有 限。按照传统的容错性定义，胛一维m e s h 的容错性是珂一l ，所以，m e s h 网络的容错 性是非常低的。如在二维m e s h 网络中，只要2 个结点出错即可破坏m e s h 的连通 性。在三维m e s h 网络中，3 个结点也就足够了。因此，人们在研究m e s h 网络容 错性时，大多采用一定的模式和限制，但限制错误模块的形状要牺牲相当多的正 确结点。我们提出一种新的不同的方法来度量m e s h 网络的容错性。本文应用一种 更为真实的模型即假定每个结点具有独立的出错概率，然后研究m e s h 网络的容错 性。本文研究表明m e s h 网络可容许相当多的错误结点而仍能确保正确结点的具有 较高的连通概率。另外，基于子网结构和概率模型研究各种容错路由算法也是相 当有意义的。 1 3 3m e s h 网络容