具有扩展局部连通性超立方体中的容错路由

《具有扩展局部连通性超立方体中的容错路由》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、具有扩展局部连通性超立方体中的容错路由摘要:在局部连通性的基础上,提出了针对超立方体X络Hn的扩展的局部k—维子立方体连通性概念;证明了具有扩展的局部k—维子立方体连通性的Hn中正确结点间是连通的;提出了超立方体X络Hn中基于扩展局部k—维子立方体连通性的路由算法。　　关键词:容错路由超立方体X络扩展的局部k—维子立方体的连通性算法　　:TP302.8:A:1007-9416(2010)08-0057-02　　　　Fault-TolerantRoutinginHypercubeNetentofputer,TaiyuanNormalUniversity,T

2、aiyuan030012,China)　　　　Abstract:Basedontheconceptsoflocalk-subcube-connectivityforhypercubesfromagivennon-faultysourcenodetoagivennon-faultydestinationnode　　　　引言　　随着并行计算机、互联X络和VLSI技术的迅速发展,系统中的并行处理越来越多,结点故障和链路故障日益增大,随之,X络的容错路由问题成为X络研究的重要课题[1]。由于超立方体理想的特性,如正则性、对称性、直径小、可扩展性强、最大容错性等[

3、2],使它成为X络中最常用的拓扑结构。在考虑超立方体X络故障时,结点故障模型和链路故障模型是两种最常见的故障模型,国内外对此作了大量的研究。文献[3,4]利用概率的方法对超立方体X络的容错路由进行了研究。文献[5、6]分别提出了不安全结点、安全向量等概念并给出了相应的容错路由算法,这些算法主要关注最优通路,而容错能力与n—维超立方体中的结点总数2n相距甚远。2001年王国军等在文献[7]、[8]中提出了基于局部连通性的容错路由算法,结点的容错能力大大提高,但错误结点数也不到超立方体结点数的一半。本文在局部子立方体连通性基础上进一步提出了扩展的局部k—维子

4、立方体连通性和扩展局部子立方体连通性概念,使得容错模型降低了对k—维子立方体的要求,提高了通用性和错误结点数,同时容错模型也适用链路故障。　　　　1扩展的局部k—维子立方体连通性　　1.1基本概念　　基本的k—维子立方体:对于任意给定的t、k(0≤t

5、子立方体也记作b1b2…bt**bt+k+1bt+k+2…bn。b1b2…btbt+k+1bt+k+2…bn称为此基本k—维子立方体的标记。本文仅讨论这种形式的子立方体,并在下文中把“基本”二字去掉。　　两个k—维子立方体之间的海明距离:指的是这两个k—维子立方体的二进制标记中的不同的二进制位的位数。海明距离为1的两个k—维子立方体称为邻接的,也即:设b1b2…bt**bt+k+1bt+k+2…bn、a1a2…at**at+k+1at+k+2…an为两个k—维子立方体,若b1b2…btbt+k+1bt+k+2…bn和a1a2…atat+k+1at+k+2

6、…an只有一位不同时,称这两个k—维子立方体邻接。　　1.2扩展的局部k—维子立方体连通性　　本节给出扩展的局部k—维子立方体连通性的概念及其与全局连通性的关系。　　定义1(扩展的局部k—维子立方体的连通性):如果n—维超立方体X络Hn中每一个k—维子立方体中由正确结点构成的每个连通子图中存在正确结点与邻接的k—维子立方体中正确结点相邻接,且至少有一个k—维子立方体正确结点是连通的,则称Hn是扩展局部k—维子立方体连通的。　　根据这一定义,在一个扩展局部k—维子立方体连通的n维超立方体Hn中,一个k—维子立方体Hk中可有2k-1个错误结点,因此,扩展局部

7、k—维子立方体连通的n—维超立方体Hn中可能有总计多达2n-k(2k-1)=2n-2n-k个错误结点。又因k—维子立方体有n-k个邻接的的k—维子立方体,而基本的k—维子立方体的个数为2n/2k=2n-k,故有故障的链路条数可以为n2n-1-2n-k-1(n-k)。　　下面证明扩展的局部k—维子立方体连通的Hn中的正确结点构成一个连通图。　　定理1:扩展的局部k—维子立方体连通的n—维超立方体X络Hn中的正确结点构成一个连通图。　　证明:对Hn中的任意一对正确结点U和V,记U所在的k-维子立方体为a1a2…at**at+k+1at+k+2…an,记V所在

8、的k-维子立方体为c1c2…ct**ct+k+1ct+k+2…。先找到正确结点是