局部扭曲立方体单播容错路由算法

《局部扭曲立方体单播容错路由算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2006年3月重庆大学学报(自然科学版)Mar．2006第29卷第3期JournalofChongqingUniversity(NttturulScienceEdition)Vo1．29No．3文章编号：1000—582X(2006)03—0069—07局部扭曲立方体单播容错路由算法苏伟，杨小帆，唐荣旺，陈文斌(重庆大学计算机学院，重庆400030)摘要：局部扭曲立方体是一种新型的网络拓扑结构．基于此网络拓扑结构，利用安全级概念以及此种网络拓扑结构自身特有的性质设计了一种单播容错路由算法．通过模拟仿真实验对该算法进行了性能评价与

2、分析．当故障节点的数目达到或超过一半时，仍能保持在一个相3'-高的容错路由成功率上．另外，该算法所选线路在多数情况下是最短距离．关键词：互连网络；局部扭曲立方体；客错路由中图分类号：TP301文献标识码：A现在很多的商用或实验性多处理机系统都采用直节点间的最短通路，这种算法要求每个节点记录系统接互连网络连接系统中的各个处理机节点．由于多处中的所有故障信息，即它是基于全局故障信息的．其中理机系统的规模越来越大，系统中出现处理机故障或Minl2给出的双向搜索算法就属于这一类型．这类算处理机间的链路故障的可能性也随之增加．因此设计法的

3、困难在于存储和维护全局的故障信息需要大量的较好的容错路由策略，尽可能多地记录系统中存在的存储和通信开销。最优通路的信息，使得当系统中存在故障的情况下实还有一类算法则是前两类的折衷，即减弱对所选现更有效的容错路由，达到提高整个系统性能的目的，链路性质的要求，例如仅要求所选通路的长度小于等越发显得重要．对于常用的一种网络拓扑结构，即超立于两节点间的海明距离加2，而并不要求最短．这类算方体，由于它直径小、结构对称、可扩展性强，近年来在法都是基于对故障信息的预处理，通过与邻接节点的针对它的容错路由设计方面，人们做了大量的研究工信息交换计

4、算每一节点的信息情况．而其中的关键就作．而其中网络中的单播容错路由问题又是网络容错是如何保证通过计算在每个节点中记录尽量多的关于路由中的最为基本的问题．单播即是指找出一条从源最优通路的信息．由于它只记录所存在的最优通路中节点“到目的节点f3之间可以传送信息的正确节点组的一部分，因此这类算法的核心问题就是如何减少所成的路径的问题．舍去的最优通路．其中[3-11]属于这一类算法．Min]采在现有算法中，一类最简单的算法是仅要求选择用动态学习的方法，通过记录各邻接节点的故障链路此链路不会形成环路，而节点也仅有它的n条邻接链的数目，给路

5、由算法以启发性的信息，从而提高了消息路(节点)的状态信息．这类算法一般是基于局部故障沿最优通路传递的概率．但它所能找到的最优通路与信息的，其中以Chen⋯的深度优先搜索(ors)算法最系统中实际存在的最优通路还有很大差距．Lee和为典型．它可以保证不论系统中有多少故障，只要消息Hayesf4首先提出了不安全节点的概念，并由此得到了的源、目的节点之间存在通路，它都能把消息传递到目一个简单的路由算法．它在每个节点记录邻接节点的的节点．这种方法的问题在于大量的消息沿大于(在状态，即安全、不安全或故障．在故障节点数小于n／2某些情况下甚

6、至是远远大于)实际存在的最短通路长(n为超立方体的维数)时，可以在任何无故障节点间度的路径传递．传递消息，且路径长度不超过两节点之间的海明距离另一类算法则是要求所选通路是消息的源、目的加2．Wu和Chiu_6修改了不安全节点的概念，使这·收稿日期：2005—11—1O基金项目：重庆市自然科学基金课题资助(CSTC，2005BB2191)作者简介：苏伟(1980一)，男，山西长治人，重庆大学硕士研究生，主要从事并行计算和路由算法研究70重庆大学学报(自然科学版)2006卑一机制的容错能力达到一1个故障节点，在任何无故1)LTQ：由

7、标记为00、0l、l0和ll的4个节点，以障节点间传递消息的路径长度小于等于两节点之间的及4条边(00，O1)、(00，l0)、(01，11)和(10，11)海明距离加4．后来Wu卜和Chiull。分别提出了安组成．全级、安全向量和路由能力的概念，这两个概念都是用2)当≥3时，LTQ由两个相同的LTQ按照来表示系统中各节点沿最优通路传递消息的能力．它如下步骤获得．在其中一个LTQ的每个节点标记前们共同的特点是能以较少的步数把消息传递到目的节添加0，记为0LTQ；在另一个LTQ的每个节点标点，并且所选通路的长度在源节点处即可确定．

8、随后记前添加1，记为1LTQ一1．然后将0LTQ中的每个shih¨基于不安全节点设计的虫孔容错路由算法也节点0x⋯Xn和1LTQ中对应的节点1(+)3只具有故障节点不超过广2]的容错能力．从不安⋯相连，其中‘+’表示模2加．全节点到安全向量，再到路由能力，这类算