（计算机软件与理论专业论文）局部扭曲立方体容错路由策略研究.pdf

重庆大学硕十学位论文中文摘要 摘要 互连网络为多计算机系统中处理器单元之间的通信提供了一种有效的机制， 随着并行计算机互连网络规模越来越大，网络中出现处理机故障或处理机间的边 故障的可能性也越来越大。因此，在出现处理机故障或处理机间的边故障的情况 下，互连网络之间高效的通信成为评估该网络的一个重要依据。 局部扭曲立方体作为超立方体的变体，是一种新型的网络拓扑结构，保持了 超立方体的很多优点的同时，其自身也有很多非常好的性质，直径大约只有超立 方体的一半，拥有更好的容错和嵌入属性。基于局部扭曲立方体的这些良好的特 性，使其成为最为重要和最有吸引力的网络模型之一。 本文主要是对n 维局部扭曲立方体存在节点故障或边故障的情况下，如何实现 消息传递进行了研究。下面是本文的主要研究工作： 在节点故障的情况下，提出了一种基于节点安全级概念的单播容错路由算 法。该算法除了考虑邻接节点的安全状况外，还充分利用了局部扭曲立方体自身 特有的结构，使得信息尽可能沿最优路径传递。通过模拟仿真实验可知，算法具 有较高的容错能力。当故障节点的数目达到或超过一半时，算法仍能保持一个相 当高的容错路由成功率，且算法所选路径在多数情况下是最优路径。 在边故障的情况下，基于局部信息的思想，通过存储其邻接节点的边故障 信息数组并引入消息回溯机制，设计了一种单播容错路由算法。仿真实验表明， 当有大量的边发生故障时，该算法也能成功地实现消息传递。 在节点故障的情况下，基于路由能力的概念提出了一种单播容错路由算 法，该算法首先寻找最短路径上满足路由能力值要求的邻接节点，其次寻找非最 短路径上满足路由能力值要求的邻接节点。这样求得的容错路径首先是最优路径， 其次为次优路径。 基于立方体分割的思想，设计了一种广播容错路由算法。通过证明可知， 若源节点为安全节点，算法产生的广播树是最优的；若源节点为非安全节点( 故障 节点数小于，1 ) ，广播能够在n + l 步内完成。 接着，我们提出了一种基于单播的多播容错路由算法，该算法通过把局部 扭曲立方体多播组节点分成若干个较小的子集合，多播消息只在各个子集合问进 行路由，并由各子集合独立完成消息传递。 关键词：局部扭曲立方体，路由容错路由，单播，广播，多播 重庆大学硕十学位论文英文摘要 a b s t r a c t i n t e r e o n n e c t i o nn e t w o r k sp r o v i d ea ne f f e c t i v em e c h a n i s mf o rc o m m u n i c a t i n gd a t a b e t w e e np r o c e s s o r si n p a r a l l e lc o m p u t i n gs y s t e m s w i t ht h ei n c r e a s i n g s i z eo f i n t e r c e n n e c t i o nn e t w o r k s ，i tb e c o m e sm u c hl i k e l yt h a tt h e r ee x i s tf a u l t yn o d e so r a n d f a u l t yl i n k si na l li n t e r c o n n e c t i o nn e t w o r k c o n s e q u e n t l y , t h ec o m m u n i c a t i o ne f f i c i e n c y o fa ni n t e r c o n n e c t i o nn e t w o r ki nt h ep r e s e n c eo ff a i l i n gn o d e s l i n k si sam a j o rc o n c e r n i ne v a l u a t i n gt h ee f f e c t i v e n e s so f t h i sn e t w o r k a san e w1 ( i n do fv a r i a n t so ft h ew e l l k n o w nh y p e r c u b e s ac l a s so fg r a p h sk n o w n a st h el o c a l l yt w i s t e dc u b e s ( l t q s ) h a sr e c e n t l yb e e np r o p o s e da sc a n d i d a t e sf o rt h e t o p o l o g yo fi n t e r c o r m e c t i o nn e t w o r k w 1 l i l er e t a i n i n gs o m en i c ep r o p e r t i e so fa h y p e r c u b e ，al o c a l l yt w i s t e dc u b eo u t p e r f o r m sah y p e r e u b eo ft h es a l t l es i z ei nt e r m so f s m a l l e rn e t w o r kd i a m e t e ra sw e l la sb e t t e rg r a p h - e m b e d d i n ga b i l i t y d u et ot h e s e r e a s o n s l t q sh a v er e c e i v c dc o n s i d e r a b l ea t t e n t i o n t h i st h e s i sa d d r e s s e sh o wt or o u t em e s s a g e si naf a u l t yn - d i m e n s i o n a ll t q t h e m a i nc o n t r i b u t i o i l so f t h i st h e s i sa r e1 i s t e db e l o w an o d e f a u l t t o l e r a n tu n i c a s tr o u t i n ga l g o r i t h mi sp r o p o s e db ye m p l o y i n gt h e s a f e t y - l e v e lt e c h n i q u ea n de x p l o r i n gt h es t r u c t u r a lp r o p e r t i e so fl t q u n d e rr e a s o n a b l e a s s u m p t i o n s ，t h i sa l g o r i t h mc a n r o u t eam e s s a g ea l o n gas h o r t e s tp a t hf r o mt h es o u r c et o t h ed e s t i n a t i o n e x p e r i m e n t a lr e s u l t sj u s t i f yt h eu t i l i t yo ft h i sa l g o r i t h m b ys i m u l a t i o n s ， w ef i n dt h a tt h ea l g o r i t h mc a l la c h i e v eas a t i s f a c t o r yp e r c e n t a g eo fs u c c e s s f u lr o u t i n g e v e ni ft h en u m b e ro ff a u l t yn o d e si sm o r et h a nh a l fo ft h et o t a ln u m b e ro fn o d e s a n d t h er o u t es e l e c t e di sh i g m yp r o b a b l et ob eas h o r t e s tp a t h al i n k f a u l t - t o l e r a n tu n i c a s tr o u t i n ga l g o r i t h mi sa d v i s e db yu s i n gaf a u l ta r r a y a n du t i l i z i n gt h er e c o l l e c t i o nm e c h a n i s m s i m u l a t i o nr e s u l t sd e m o n s t r a t et h a t ，w i t ht h i s a l g o r i t h m am e s s a g ec a l lb er o u t e ds u c c e s s f u l l ye v e nw h e nal a r g en u m b e ro fl i n k s b r e a kd o w n a ne f f i e i e n tf a u l t t o l e r a n tu n i c a s tr o u t i n ga l g o r i t h mi ss u g g e s t e db ye m p l o y i n g t h ec o m c e p to f r o u t i n gc a p a b i l i t y s i m u l a t i o nr e s u l t ss h o wt h a tt h i sa l g o r i t h mc a ne n s u r e a no p t i m a lo rs u b o p t i m a lu n i c a s t i n g af a u l t - t o l e r a n tb r o a d c a s ta l g o r i t h mi sd e v e l o p e db a s e do nt h ec o n c e p to f d i v i s i o n a lh y p e r c u b e t h e o r e t i c a la n a l y s i ss h o w st h a ta no p t i m a lb r o a d c a s tt r e ec a nb e f o r m e dw h e nt h es o b r c en o d ei ss a f e , a n dab r o a d c a s tr e q u i r e sa tm o s t + ls t e p sw h e n i i 重盎查堂堡兰垡堡塞 茎塞塑墨 t h es o u r c ei su n s a f ea n dt h e r ea r en om o r et h a nnf a i l i n gn o d e s au n i c a s t - b a s c dm u l t i c a s tr o u t i n ga l g o r i t h mi sp r e s e n t e db yd i v i d i n gt h e m u l t i c a s ts e ti n t oas e to f s m a l l e rs u b s e t sa n dc a r r y i n go u tt h em u l t i c a s tf o rt h e s es u b s e t s i n d e p e n d e n t l y k e y w o r d s ：l o c a l l yt w i s t e dc u b e ；r o u t i n g ；f a u l t - t o l e r a n tr o u t i n g ；u n i c a s t ；b r o a d c a s t ； m u l t i c a s t 1 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆盔堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 脊砟 签字日期：加 年f 月刁日 学位论文版权使用授权书 本学位论文作者完全了解重废太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重鏖太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 力。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：r 水币 签字日期：绷年j 月纠日 导师签名： 小椒 签字日期：l , o - 1 年，月2 , 1e t 重庆大学硕十学位论文1 绪论 1 绪论 1 1 引言 人们总是追求更高性能的计算能力，并行计算机则是实现高性能计算能力的 有效技术途径。近年来，在国防、太空、汽车制造业和科学领域都出现了大量具 有巨大挑战的应用问题，它们要求计算机具有每秒万亿次级浮点运算( t e r a f l o p s ) ， 甚至更高级别的计算能力。高性能商用微处理器技术取得了迅猛的发展，为并行 计算机的实现提供了前所未有的、坚实的物质基础，使高性能大规模计算机的实 现成为可能。 但是，多处理机系统的规模越来越大，系统中出现处理机故障或处理机间的 边故障的可能性也随之增加，这就要求系统有一定的容错和检错能力，以保证系 统的正确运行。因此系统的可靠性很大程度上依赖于它的容错能力，容错能力的 好坏往往直接影响到系统的性能。这样就需要我们设计较好的容错路由策略，尽 可能多地记录系统中存在的最优通路的信息，使得当系统中存在故障的情况下实 现更有效的容错路由，达到提高整个系统性能的目的。最理想的容错路由算法应 当是，只要源、目的节点间存在通路就可以把消息沿最短通路传递到目的节点的 算法。目前，互连网络为多计算机系统中处理器单元之间的通信提供了一种有效 的机制，互连网络的拓扑结构决定着多处理机系统中处理器单元之间协同工作的 能力。因此，选择或设计一种高效、可靠的多处理器互连拓扑结构对组建多计算 机系统是非常重要的。同时，基于多计算机系统互连网络拓扑结构容错路由算法 的研究也已经成为一个很重要的课题。 1 2 互连网络拓扑结构介绍 互连网络按几何形状分为两大类：规则网和不规则网。规则网又分为静态网 和动态网两种。所谓静态网是指网络拓扑结构中各节点间有专用的链路，这些链 路是固定连接的不能重新组合。而动态网是指网络拓扑结构中，各节点间的链路 可以通过设置网络的开关来重新组合。 当前互连网络拓扑结构有很多种，常见的网络拓扑结构有：线性列阵形网 ( 1 i n e a rm a r y ) ，环形f * c r i n g ) 、网格形网( m e s h ) 、树形网( t r e e ) 、蜂窝网( h o n e y c o m b ) 、 超立方体形( h y p e r c u b e ) 、扭曲立方体( t w i s t e dc u b e ) 、m o b i u s 立方体( m o b i u sc u b e ) 、 交叉立方体( c r o s s e dc u b e ) 、总线形l 网( b u s ) 、全互连网、蝶形网( b u t t e r f l yn e t w o r k ) 、 洗牌交换( s h u f f l e e x c h a n g e ) 、交叉开关网( e r o s s b a rs w i t c hn e t w o r k ) 、b e n e s 网、 s t a r a n 网、数据交换网等等。在图1 1 中列出了部分拓扑结构。 重庆大学硕十学位论文1 绪论 ( g ) 全互连网 ( e ) 二叉树( f ) 超立方体 ( h ) 总线型网( i ) 交叉开关网 图1 1 网络拓扑结构 超立方体p 】互连拓扑结构是一种在实践中得到广泛应用的互连网络模型之一。 例如，i n t e lc m 一2 【4 】，i p s c i 。i p s c 2 c 5 l 以及n c u b e 6 】等机器采用的都是超立方体结 构。这是因为基于超立方体的互连网络有很多优秀的性质，比如：对称性，可递 归构建性，更重要的是基于超立方体的互连网络具有较强的容错性。 然而，对于一个具有2 “个结点，连通度是n 的网络拓扑结构来说，节点总数 对数级的网络直径并不是最优的，也就是说，在保证连通度和节点总数不变的前 提下，可以设计出网络直径更小的互连拓扑结构，这就促使人们展开了对超立方 米一众 | | 警硷 重庆大学硕士学位论文1 绪论 体变体及其性质的研究，如：平衡超立方体t 7 j ( t h eb 加c e dh y p e r c u b e ) 、环立方体 鹏 ( c u b e c o n n e c t e d c y c l e ) 、超级立方体一 ( s u p e r c u b e ) 、扭曲立方体【1 川( t w i s t e d c u b e ) 、局部扭曲立方体【1 1 1 ( l o c a l l y t w i s t e dc u b e ) 、莫比乌斯立方体 1 2 , 1 3 1 ( m o b i u s c u b e ) 、交叉立方体1 1 4 , 1 5 ( c r o s s e dc u b e ) 、超级交叉立方体【1 6 1 ( s u p e rc r o s s e dc u b e ) 等等。 局部扭曲立方体，作为一种新型的网络拓扑结构，是超立方体的一个变体， 由v a n g t l q 于2 0 0 4 年提出。它不仅保持了超立方体的很多优点，对称性，可递归构 建性等，而且其直径也只有超立方体的一半，在路由能力方面强于超立方体，拥 有更好的容错和嵌入属性。局部扭曲立方体具有很好的发展前景，目前对局部扭 曲立方体容错路由的研究还很少。本文就是着重研究基于局部扭曲立方体网络拓 扑结构的容错路由算法。 1 3 国内外研究现状 随着网络规模的不断扩大，网络中出现链路和或节点故障的概率也随之增大， 从而使得网络的容错性研究变得日益重要。因此，一些研究者针对目前已有的超 立方体互连网络中的各种容错模型，设计了大量的单播( u n i c a s t i n g ) 与多播 ( m u l t i c a s t i n g ) 容错路由算法。 超立方体互连网络中单播容错路由算法的研究 1 9 9 7 年w u t ”1 基于安全级别容错模型提出了一种基于超立方体互连网络的单播 容错路由算法，利用该算法，源节点通过比较自己的安全级、邻接节点的安全级、 以及到目的节点的h a m m i n g 距_ 离即可快捷地找到一条到目的节点的最优或次优通 路。1 9 9 9 年g 8 1 等针对具有大量故障节点的容错超立方体互连网络进行了研究， 基于安全级别容错模型提出了三种新的单播容错路由算法。2 0 0 0 年w u t ”1 等对基于 s 啪容错路由算法进行改进，提出了一种基于扩展安全向量容错模型嬲哟超立方 体互连网络单播容错路由算法。2 0 0 0 年高峰【2 0 1 等基于最优通路矩阵容错模型o p m 提出了一种超立方体互连网络的单播容错路由算法，并证明了该算法具有比基于 s i ce s 啪单播容错路由算法更好的容错性能。2 0 0 2 年田绍槐基于扩展最优通路 矩阵模型凰卯m 提出了一种超立方体互连网络的单播容错路由算法，证明了该算法 的容错性能优于基于伪谢容错模型的单播容错路由算法。2 0 0 2 年，4 b 蒯2 2 1 等基于非 安全向量容错模型u s 瞄黾出了一种超立方体互连网络的单播容错路由算法，证明了 该容错路由算法在路由距离及路由可达率等方面都优于基于s 瞎错模型的单播容 错路由算法。2 0 0 2 年c h e n t 2 ”等基于子立方体的连通性容错模型提出了一种超立方 体互连网络的单播容错路由算法，证明了该容错路由算法在具有不超过5 0 故障节 点的情况下，如果路径存在，则一定能成功找到一条从源节点到目的节点的安全 重庆大学硕十学位论文1 绪论 路径。2 0 0 4 年w a n g _ 【2 4 1 等针对超立方体结构的多处理机系统中出现链路故障的情况， 提出了极大安全通路向量的概念，给出了一个建立_ m s p 趿其容错路由的算法，与 基于安全向量及扩展安全向量的容错路由算法相比，m s p 嘿s v 以及点s 啪最大扩 展。2 0 0 4 年彳山眺【2 5 1 等基于概率容错模型提出了一种超立方体互连网络的单播容错 路由算法，并证明了该容错路由算法具有较小的平均路由距离，因此具有良好的 容错性能。 超立方体互连网络中多播容错路由算法的研究 1 9 9 2 年l e e t 2 “等基于安全节点s n ( s a f en o d e ) 的概念提出了一种超立方体互连网 络上的广播容错路由算法，该算法利用邻接节点的安全级别来进行路由选择。1 9 9 3 年w u t 2 7 1 修改了安全节点的概念，并在此基础上提出了一种容错超立方体互连网络 上的广播容错路由算法。1 9 9 5 年，w u t 2 8 l 又基于安全级别容错模型乩提出了一种超 立方体互连网络上的广播容错路由算法。1 9 9 8 年，c h i u 和c h e n t 2 9 1 基于路由能力的 概念提出了一种超立方体互连网络上的多播容错路由算法。1 9 9 9 年d o b r e v l ”1 等给 出了具有动态故障节点的超立方体互连网络上的一种最优广播容错路由算法。 2 0 0 0 年b e r m o n a ”1 等对电路交换模式( c i r c u i ts w i t c h e dm o d e l ) 下的超立方体互连网 络上的广播容错路由算法进行了研究。2 0 0 1 年m a s u y a m a t ”1 等对n 维超立方体互连网 络上的所有节点到所有节点间的广播容错路由算法进行了研究。2 0 0 2 年，w a n g 禾t c h e n t ”l 针对具有大量故障节点的立方体网络，提出了一种广播容错路由算法。2 0 0 3 年w u t 3 4 1 对超立方体互连网络的广播容错路由算法进行了研究，基于d s l 容错模型 提出了一种新的广播容错路由算法，该算法利用二项式树( b i n o m i a ，t r e e ) 进行广 播，其时间复杂度与基于乩容错模型的广播路由算法相同，但容错能力更强。2 0 0 3 年砌，珂”1 基于三口容错模型对超立方体互连网络的广播容错路由算法进行了研究， 给出了一种容错超立方体上进行了最优广播的充分条件，并依据该充分条件给出 了相应广播容错路由算法，证明了新算法在路由性能及容错性能上均要优于基于 乩容错模型的广播容错路由算法。2 0 0 3 年m a s u y a m a | 蚓等在其前述研究基础上提出 了一种适用于最多n 2 个故障节点的容错超立方体互连网络上的所有节点到所有节 点间的广播容错路由算法。 1 4 论文的组织结构 论文共分5 章。第1 章为论文的绪论部分，第2 章到第4 章是论文的主体部 分，第5 章是论文的结束语部分。 第1 章为绪论。首先介绍并行计算机的有关知识以及几种常见的网络拓扑结 构，然后介绍本课题的研究意义，接下来，综述超立方体网络容错路由算法的研 究现状和水平，最后对论文的组织安排进行了大纲性的介绍。 4 重庆大学硕士学位论文l 绪论 第2 章对本文将要研究的局部扭曲立方体进行了详细介绍，对后面将要用到 的一些基本概念和算法作了必要的陈述。然后介绍了现有的3 类典型的容错路由 算法。第1 类算法是基于本地信息的容错路由算法，第2 类算法是基于非本地信 息的容错路由算法，第3 类算法是基于图搜索的容错路由算法，并对这些算法进 行了详细的实例分析。本文在第3 、4 章提出的单播、广播、多播容错路由算法都 是基于本章提出的局部扭曲立方体。 第3 章介绍本文设计的基于局部扭曲立方体的3 个简单的单播容错路由算法。 第1 个算法是基于节点安全级概念的单播容错路由算法。第2 个算法是基于局部 信息的思想而提出的单播容错路由算法。第3 个算法是基于节点路由能力概念的 单播容错路由算法。 第4 章首先介绍了一种基于局部扭曲立方体的广播容错路由算法。该算法是 基于立方体分割思想而设计的，通过证明，当源节点为安全节点时，该算法产生 的广播树是最优的。接着，提出了一种基于单播的多播容错路由算法。 第5 章是结束语。在结束语中对本文的研究工作进行了总结，并对进一步的 研究工作进行了展望。 5 重庆大学硕士学位论文2 基础知识 2 基础知识 在研究多计算机系统时，通常用图g ( 旧来表示多计算机系统，顶点集矿表 示处理器单元的集合，边集e 表示通信链路的集合。在以后的章节中，处理器单 元称为节点或顶点，而通信链路称为边。 2 1 局部扭曲立方体及其性质 为了尽可能的保持原有超立方体的性质，g 于2 0 0 4 年提出了一种比已有超 立方体变体更为接近超立方体的变体一局部扭曲立方体1 1 1 j l t q 。( n - d i m e n s i o n a l l o c a l l yt w i s t e dc u b e ) 。在一个局部扭曲立方体中，两相邻节点的标号有一位或连续 的两位不同。l t q 的优势之一在于其直径只有g 的一半左右，并且一个u 1 函可 由两个g 1 通过某种方式互相连边构成，并且其路由算法也比较容易实现。对于 这种新型的超立方体变体结构，y a n g 等人做了深入的研究1 3 7 , 3 8 + 3 9 1 。 定义2 1 1 ( 递归定义) ：2 ，一个维局部扭曲立方体( 1 0 c a l l yt w i s t e d c u b e ，l t q ) 定义如下： l t q 2 是由分别标记为0 0 ，o l ，1 0 和1 l 的四个节点组成的图，其节点问相 邻的四条边分别为 o o ，0 1 ) ， o l ，1 1 ) ， 1 1 ，1 0 ) ， 1 0 ，0 0 ) 。 当厅2 3 时，l t q n 由两个相同的u g 1 按照如下步骤获得：在其中一个l t q 1 的每个节点标记前添加0 ，记为o l t q n 1 i 在另一个l t q 1 的每个节点标记前添加 1 ，记为1 l t q 。然后将o l t q i 中的每个节点o x 2 x 3 x n 和i l t q 。i 中对应的节点 1 c 砭+ 而k x n 相连，其中+ 表示模2 加。 定义2 1 2 ( 非递归定义) ：n 2 ，栉维局部扭曲立方体l t q 是一个以 0 ，i ) 4 为节点标号集的图。l t q 。中的两个节点工= x 1 恐翰和y = y l y 2 协相邻当且仅当： 对于某个i 茎k 曼甩一2 ，豫= y 女且秘+ 1 = 雎+ i + 而，且对于其它，k ，有昂 2 y r 。 对于某个k ，l l ，厅) ，有瓤= j ，。，且对于其它，k ，有矗= 弦。 图2 1 伍b ) 分别是栉= 3 ，4 时局部扭曲立方体互连结构。 6 重庆大学硕士学位论文2 基础知识 图2 1 局部扭曲立方体 f i g 2 1 l o c a lt w i s t e dc u b e 下面先给出本文将要用到的一些概念。 对于畦i 刀一1 ，用e n , i ( 简称为的来表示长度为n 的二进制字符串，其第i 位为l ， 其余位全部为0 。也即： 印= 1 0 0 0 0 0 ，e l = 0 1 0 0 0 0 ，e 2 = 0 0 1 0 0 0 ，e n 1 = 0 0 0 0 0 1 。 同时，对于o si 曼h 一3 ，我们用最，f ( 简称为蜀) 来表示长度为月的二进制字符串， 其第i 和f + l 位为1 ，其余位全部为0 。另外，昂1 = e n - i ，易= e n ，也即： 昂= 1 1 0 0 0 0 ，占i = 0 1 1 0 o o ，e 2 = 0 0 1 l 0 0 ，磊- 2 = 0 0 0 0 1 0 ，晶i = 0 0 0 0 0 1 。 a l g o r i t h m 2 1s c a n ( x = x l x 2 翰) i f o = 矿) r e t u r n ( m ) ； e l s e ，= m i n f ：= 1 ) ； c a s e 甩一l ，r ：r e t u r n ( s c a n ( x + e r ) u 唧) ) ； c a s e ( ，n 一2 ) & ( 并+ i = o ) ：r e t u r n ( s c a n + e r ) u o ) ) ； c a s e ( ，s n 一2 ) & & + i = 1 ) ：r e t u r n ( s c a n ( x + e r ) u 昂 ) ； ) ) a l g o r i t h m 2 2e _ s c a n ( x = x l x 2 而) i f 0 = o n ) r e t u r n ( ) ； e l s e p ：2 m i n f ：x i 2 1 ) ；r e t u r n ( e s c a n + e r ) u p r ) ) ；) ) 7 重庆大学硕士学位论文2 基础知识 a l g o r i t h m 2 3e _ s c a n ( x = x l x 2 ) i f ( x = 矿) r e t u r n ( o ) ； e l s e r ：= m i n f ：而= 1 ) ；r e t u r n ( e _ s c a n ( x + 动u 巨”；) ) a l g o r i t h m 2 4r o u t e _ b m ( 五力 m = s c a n ( 工+ j ，) ； s w i t c h ( x n i ，y n 1 ) c a s e ( 0 ，0 ) ：m e = e s c a n ( 工+ y ) ； i f ( 1 叫i m l + 2 ) m = m e ； e l s e m = m + e n i ，e n - i ) ； b r e a k ； c a s e ( 1 ，1 ) ：m e 2 e _ s c a n ( 工+ y ) ； i f ( i 删i m i + 2 ) m = m e ； e l s e m = m + 晶i ，晶1 ； b r e a k ； c a s e ( 0 ，1 ) ：b r e a k ； c a s e ( 1 ，0 ) ：b r e a k ； ) r e t u r n 舱 例如，令x = 0 0 1 1 1 0 1 1 0 1 0 1 1 0 ，则s c a n ( x ) = e 3 ，e 5 ，e 7 ，e l o ，e 1 2 ) ，e _ s c a n = p 3 ， e 4 ，e 5 ，e 7 , e 8 ，e l o ，e 1 2 ，e 1 3 ，es c a n = 历，历，尾，风，e 9 ，e 1 2 。 2 2 三种典型的容错路由算法介绍 容错是指在部件失效情况下网络运作的能力，然而容错实现技术往往是以巨 大的性能降低为代价的。下面，我们将介绍三种典型的容错路由算法，并对特定 的容错路由算法通过实例进行了分析。 2 2 1 基于本地信息的容错路由算法 如果源节点和目的节点的地址有m 位不同，则消息将按源到目的节点的最短 路径穿越维，这种维序称为坐标序并用一个维列表表示。在一个中问节点上，不 重庆大学硕士学位论文 2 基础知识 在通向目的节点最短路径上的维成为备用维。当从一个中间节点通往目的节点的 所有最短路径都被故障阻塞时，消息将路由到备用维上。被故障阻塞的维以及备 用的维都保存在消息头的聍位标记中。这样，消息就包含了以下几部分： ( m ， c l ，c 2 ，c t 】，m e s s a g e ，d ) 。m 值代表到目的节点的距离，标记d 在源节点初始 化为0 ，一个中间节点接收到一个消息后，选择坐标序中的一维来路由。然后消息 头更新，减小m 并把经过的维从坐标序中清除。当所有最短路径都被阻塞时，m 的值增加并将备用维加入坐标序中，标记d 被更新，消息沿备用维进行绕道路由。 这种方法具有( 厅1 ) 的容错度，路由算法如下所示。 a l g o r i t h m 2 5 使用备用维的容错路由 输入：消息， q ，c 2 ，c i 】，m e s s a g e ，d ) 过程： 若m = o ，则已到达目的节点。 户1 到m ：若链路c ，无故障，则沿链路c ，发送消息 ( 聊一l ，【c l ，c 2 ，c j - 1 , c ，c 埘】，m e s s a g e ，d ) 并停止。 如果所有处于最短路径上的维都被故障阻塞，则： 1 ) 户1 到历：d o = 1 产记录所有的被阻塞维+ 2 ) 令h 为最小备用维，使d 。= o 。 3 ) d = l ，沿维h 发送消息( m + 1 ， c l ，c 2 ，e 。，h i ，m e s s a g e ，d ) 。 0 0 1 0 图2 2 绕过故障的s a f 路由 f i g2 2 s a fr o u t i n ga l g o r i t h m s 例如，针对图2 2 中边( 1 1 1 0 ，l 1 0 0 ) 并d ( 1 l l l ，1 1 0 1 ) 为故障边的情况下，假设一个 消息从图2 2 中的节点0 0 1 0 路由到节点1 1 0 1 ，起始消息应为：( 4 ，【3 ，2 ，1 ，0 】， m e s s a g e ，o o o o ) 。在源节点运行的路由算法把消息更新为( 3 ，【2 ，1 ，o 】，m e s s a g e ， 9 重庆大学硕十学位论文2 基础知识 o o o o ) 并送到节点1 0 1 0 ，该节点把消息更新为( 2 ，【1 ，o 】，m e s s a g e ，0 0 0 0 ) 并送到节 点1 1 1 0 。这时，下一维上有一个故障，所以消息更新为( 1 ， 1 】，m e s s a g e ，0 0 0 0 ) 并送到节点1 1 1 l 。这时消息必须进行绕道路由，因为唯一通往目的节点的路径已 被故障阻塞。标记中与这一维对应的位被置位，最低备用维也被置位。被更新的 消息( 2 ， 1 ，0 】，m e s s a g e ，o o v ) 将送到节点1 1 l o ，然后消息更新为( 1 ，【l 】，m e s s a g e ， 0 0 1 1 ) 并再次送到节点l l i l 。在节点l l l l 时，便可以选择维2 作为空闲维，因为此 时标记值为0 0 1 l ，被更新的消息( 2 ，【1 ，2 】，m e s s a g e ，0 1 1 1 ) 路由到节点1 0 1 1 ，然 后经维l 和维2 可到达节点1 1 0 1 。 2 2 2 基于非本地信息的容错路由算法 l e e 和h a y e s 在 2 6 1 中介绍了不安全节点的概念。一个无故障节点如果与两个 以上的故障节点或不安全节点相邻，则它就是一个不安全节点。下面给出了一种 基于不安全节点概念的容错路由算法描述。 a l g o f i t h l n 2 6 使用不安全节点的容错路由 过程： 如果在到达目的节点的最短路径上存在一个非故障邻接节点，则把消息发 往该邻接节点并停止。 如果在到达目的节点的最短路径上存在一个不安全邻接节点，则把消息发 往该邻接节点并停止。 把消息发往任一非故障邻接节点( 当故障数小于f ，砣j 时，这样的邻接节点 必然存在) 并停止。 w u 2 7 1 放松了三卯中的条件，对不安全节点的概念进行了修改，提出了扩展 不安全节点的概念。这种不安全节点的概念在二进制超立方体可以扩展为多个不 同级别的安全。 安全级可以看做是一种非本地的状态信息，故障的位置和分布编码位于一个 节点的安全级中，故障节点的确定位置并没有指出。实际上，故障位置的信息是 为了更好地找到最短路径。利用如下特性，安全级可以实现这一目的。如果一个 节点的安全级为s ，那么对于此节点接收的、距离其目的节点不超过s 的任何消息， 在到达目的节点的最短路径上至少存在一个邻居节点，其安全级为孓l 。这个到达 目的节点的最短路径上的邻居称为优先邻居，剩下的邻居成为备用邻居。显然， 如果消息不能被送达目的节点，则所有优先邻居的安全级都将小于d 1 ，这里d 是 到目的节点的距离，并且备用邻居的安全级都将小于d ，一旦每个节点的安全级都 计算出来，消息就可以按如下所示算法进行路由。 a l g o r i t h m 2 7 使用安全级的容错路由 输入：消息( 消息，目的) ，坦g = 当前节点地址。目的地址，d 是达到目的节点 重庆大学硕七学位论文 2 基础知识 的距离 过程： 若t a g = o ，则已经达目的。 若至少存在一个安全级大于等于d 1 的优先邻居，则把消息发送到安全级最 高的优先邻居上。 若至少存在一个安全级大于等于件l 的备用邻居，则修改t a g 并把消息发送 到该邻居上。 0 0 1 0 图2 3 基于安全级的容错路由 f i g2 3 f a u l t t o l e r a n tr o u t i n gu s i n gs a f e t yl e v e l s 例如，针对图2 3 所示的具有4 个故障节点的二进制超立方体，节点都标记了 它们相应的安全级。节点1 1 0 0 的安全级为2 ，那么距离节点1 1 0 0 为两跳步的每个 节点都能通过长度不超过2 的一条路径到达。考虑到节点0 1 1 0 的一条路径。如果 维序按升序进行路由，那么维序路由路径会被故障节点1 1 1 0 阻塞。但是有一条替 代路径可用：经过节点0 1 0 0 。注意，节点0 1 0 0 与节点1 1 0 0 邻接，并且在到达节 点o l l o 的最短路径上，安全级为4 。这个例子说明了安全级的全局特性，故障确 切分布是未知的，但到达节点的可用最短路径已编码在安全级中，它可以用来进 行路由的本地决策。 2 2 3 基于图搜索的容错路由算法 基于图搜索技术的路由算法提供了路由的最大灵活性，消息包可以对节点问 所有可能的路径进行搜索，并在对应的一组链路上进行路由。尽管路由开销比较 大，但消息在故障网络中传送的概率最大。现己提出了许多基于图搜索路由算法 的方案。下面给出了一种基于深度优先搜索的容错路由算法描述。 a l g o h t h m 2 8 基于深度优先搜索的容错路由 输入：消息( r ，7 d ，m e s s a g e ) ，r = ( ，= l l ，：l - 2 ，r j ，r o ) 产。代表二进制向量间的异或操作；e 表示n 位向量第i 位黄1 ，其它 重庆大学硕十学位论文2 基础知识 位都为o ；& 表示列表级联操作 过程： 若r = o ，则已到达目的。 对于户0 到以一l ：若r ，= 1 且链路_ ，无故障，并且维，上的邻接节点以前没被 访问过，则消息( r o e i , t d & ，m e s s a g e ) 沿维，传送并停止。 严消息必须绕道或返回 若可能，则选择最小维_ i l ，使此维上的链路无故障，且此维上的节点以前 没访问过，消息( r o e 6 ，t d & ，m e s s a g e ) 沿维h 传送并停止。 严消息回退到路径上的前一个节点 若该中间节点接收到来自维g 上节点的消息，则把消息 俾o e g ) t d & g ，m e s s a g e ) 送回到此路径上的先前节点，即回溯到先前节点。 0 0 1 0 o l 图2 4 基于深度优先搜索的容错路由 f i g2 4d e p t h - f i r s ts e a r c ha p p r o a c hf o rf a u l t - t o l e r a n tr o u t i n g 考虑图2 4 内一个从节点0 0 1 0 路由到节点1 1 0 1 的消息所经过的路径。消息所 经过的节点序列为( 0 0 1 0 ，0 0 1 l ，0 0 0 1 ，0 0 0 0 ，0 0 0 1 ，0 0 1 1 ，0 1 1 1 ，0 1 0 1 ，1 1 0 1 ) 。 消息首先通过维0 ，然后通过维1 到达节点0 0 0 1 。在这一点，最小路径维上的故 障迫使消息绕道路由，消息路由到节点0 0 0 0 。在节点0 0 0 0 检测出两条输出链路存 在故障，消息已通过的维列表被保存在消息头中。这个列表可以用来重新建造消 息要访问的所有节点。在节点0 0 0 0 ，通过此列表可以知道节点0 0 1 0 已经被访问过， 这使得消息回退到节点0 0 0 1 。在节点0 0 0 1 ，由于所有的输出通道都已经被搜索过， 因此消息回退到节点0 0 1 1 ，消息的内容为：( 1 1 1 0 ，【o ，l ，0 ，0 ，1 ，m e s s a g e ) 。在节点 0 0 1 l ，路由算法会选择通往目的节点的最低维前进，这便是维2 。所以消，皂,