k元n立方体网络的容错路由

开篇：润墨网以专业的文秘视角，为您筛选了一篇k元n立方体网络的容错路由范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：本文提出了k元n立方的m子立方体连通图的定义，讨论了该图的连通性。利用k元n立方的m子立方体连通图的概念提出了可容纳大量错误结点的容错路由算法，并对算法的时间复杂度做了分析。

关键词：k元n立方体网络 容错路由 k元n立方的m子立方体连通图 连通图

中图分类号：TP302.8 文献标识码：A 文章编号：1007-9416（2012）09-0024-01

1、引言

k元n立方是 Duato等人在1997年提出并行系统网络拓扑模型。k元n立方具有优良的拓扑性能，比如：正则性、对称性、易用性、可嵌入性、Hmailton性、低延迟等，使得k元n立方在一些大规模并行系统受到青睐。很多人对k元n立方拓扑模型做了研究[1]，有的并行系统采用它作为网络拓扑，例如Cray T3D、J-machine、iWarp、Blue Gene等。这些大型系统结点众多，容易出错，k元n立方网络拓扑容错成为重要的研究内容。本文主要是把王国军等人在超立方体网络中提出的算法[2]推广到了k元n立方，并把前提条件做了弱化，使得结点容错能力更强。

2、连通性及容错路由算法

2.1 基本概念及性质

k元n立方[1]：是这样的一个无向图G（V，E），令={0，1，2，…，k-1}，V={x|x=xnxn-1…x2x1，xi∈，i=1，2，…，n}，E={（x，y）|x，y∈V，x=xnxn-1…x2x1，y=ynyn-1…y2y1，存在一个j，1≤j≤k，yj=xj±1（modk），yi=xi（当i≠j）}。k元n立方有kn个结点。

k元n立方的基础m子立方：是由结点集V1={x|x=knkn-1…km+1xm…x2x1，xi∈，i=1，2，…，m，而kn，kn-1，…，km+1是属于的常数}生成的k元n立方的子图。k元n立方的基础m子立方记为knkn-1…km+1*。

显然，所有的k元n立方的基础m子立方的结点刚好构成了k元n立方的一个划分。

两个k元n立方的基础m子立方unun-1…um+1*和vnvn-1…vm+1*是相邻的，如果这两个基础m子立方对应前m位中有一位uj≠vj，且ujvj±1（modk），其余的相同。

k元n立方的m子立方体连通图：k元n立方的基础m子立方无错误结点构成连通图，且任两个相邻k元n立方的基础m子立方至少有一对相邻的无错误结点。

定理：k元n立方的m子立方体连通图是连通图。

证明：在k元n立方的m子立方体图中任取两个无错误结点U、V，设U所在的k元n立方的基础m子立方为unun-1…um+1*，U所在的k元n立方的基础m子立方为vnvn-1…vm+1*，按从下标从大到小找出unun-1…um+1和vnvn-1…vm+1的第一个ui≠vi，不妨设ui-vi=s，且s>0。在vnvn-1…uiui-1…um+1*和vnvn-1…（ui+1）ui-1…um+1*这两个相邻k元n立方的基础m子立方之间寻找两个相邻无错误结点U1i、U1（i+1），因vnvn-1…uiui-1…um+1*为连图图，有U到U1i的一条通路，又U1i、U1（i+1）是相邻无错误结点，故有U到U1（i+1）的一条通路。接着在vnvn-1…（ui+1）ui-1…um+1*和vnvn-1…（ui+2）ui-1…um+1*这两个相邻k元n立方的基础m子立方之间寻找两个相邻无错误结点U2i、U2（i+2），又vnvn-1…（ui+1）ui-1…um+1*为连图图，有U1（i+1）到U2i的一条通路，又U2i、U2（i+2）是相邻无错误结点，故有U到U2（i+2）的一条通路。此过程一直继续，直到第i个位相同。接下来按从下标从大到小找出ui-1ui-2…um+1和vi-1vi-2…vm+1的第一个uj≠vj，与上述同样的原因，有U到vnvn-1…（uj+1）uj-1…um+1*中一个无错误结点Uj的一条通路。此过程一直继续，直到U能找到一条到vnvn-1…vm+1*中某个结点W的一条通路。又vnvn-1…vm+1*是连通图，有W到V的一条通路。知有U到V的一条通路。故k元n立方的m子立方体图是连通图。

2.2 容错路由路由算法

在v这两个相邻k元n立方的基础m子立方之间寻找两个相邻无错误结点时间复杂度是O（km），利用广度优先搜索在有错误结点的k元n立方的基础m子立方找一条连接两个无错误结点的通路时间复杂度为（km），故算法的时间复杂度是O（nkm+1）。

3、结语

在实际系统中，随着系统的增大，元器件的故障在所难免。k元n立方由于具有正则性、对称性、易用性、低延迟等诸多优秀特性，成为并行体系结构青睐拓扑网络。本文在k元n立方的m子立方体连通图的概念基础上提出了可容纳大量错误结点的容错单播路由，容错结点数能达到一半以上。

参考文献

[1]胡凯，王哲等.k-元n-立方体网络局部通信模式下的性能模型[J].计算机研究与发展，2011，48（11）：2083-2093.

[2]王国军，陈建二，陈松乔.具有大量错误结点的超立方体网络中的高效路由算法的设计与讨论[J].计算机学报，2001，24（9）：909-916.