故障k元n立方体网络中的多播容错路由算法

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

摘要：本文在k元n立方的m子立方体连通的k元n立方体网络中，讨论了多播容错路由算法，使得k元n立方体网络中多播路由不止适合结点故障、也适合链路故障，同时讨论了算法的时间复杂度。

关键词：k元n立方体网络 多播路由 k元n立方的m子立方体连通的

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

1 引言

由于大规模集成电路的使用，使得网络的故障越来越多。k元n立方体网络因其结构简单，具有很多优美的特性，使其成为一种较实用的并行拓扑结构。本文在文献[2]中提出的k元n立方的m子立方体连通的的概念的基础上，讨论了多播容错路由算法。k元n立方的m子立方体连通的k元n立方体网络极大提高了网络的结点、链路的容错能力。

2 连通性及容错路由算法

2.1 基本概念

k元n立方：指无向图G（V，E），结点集V={u1 u2…un-1 un| ui∈{0，1，…，k-1}，i=1，2，…，n}， 两个结点u= u1 u2…un-1 un，v=v1 v2…vn-1 vn相邻当且仅当它们有且仅有一个位置的坐标不同。

k元n立方的m子立方：是由V’={ u1 u2…un-m vn-m+1 vn-m+2…vn | vi∈{0，1，…，k-1}，i=n-m+1，n-m+2，…，n，且 u1，u2，…，un-m是0到k-1的常数}生成的k元n立方的子图。为方便，记其为u1 u2…un-m **。u1 u2…un-m为u1 u2…un-m **的标记。

两个k元n立方的m子立方x1 x2…xn-m **、y1 y2…yn-m**是相邻的，如果这两个k元n立方的m子立方前m位中有且仅有一位的值不同。

k元n立方的m子立方体连通的：k元n立方的m子立方可达结点是连通的，同时任两个相邻k元n立方的m子立方至少有一对可达结点相邻。

2.2 容错多播路由算法

为实现k元n立方体里的多播理由算法，我们首先引入两个算法。

算法1实现k元n立方的m子立方体连通的图中一个可达结点到给定的一个k元n立方的m子立方体某个结点的路由算法。

算法1：输入：k元n立方的m子立方体连通图的可达结点U= x1 x2…xn-m xm-m+1…xn-1 xn，k元n立方的m子立方体y1 y2…yn-m **。

输出：U到k元n立方的m子立方体 y1 y2…yn-m **某个结点的路径。

（1）FOR i=1 TO n-m

t=0；Wt= x1 x2…xn-m；

IF xi≠xi THEN Wt=y1 y2…yi xi+！…xn-m；t=t+1；

（2）FOR i=1 TO t

V0=U；寻找以Wi-1到Wi的一对可达结点到Ui-1，Vi（称为Wi的通路结点）；

在以Wi-1为标记的k元n立方的m子立方中找Vi-1到Ui-1的路径；（注：此时有U到Vi的路径）

（3）到此，已找到一条从U到k元n立方的m子立方体y1 y2…yn-m **结点Vt路径。如此过程不能继续，则不是k元n立方的m子立方体连通的。

算法时间复杂度分析：在相邻k元n立方m子立方间找一对可达结点需O（km），在k元n立方的m子立方找两个可达结点的需（km），由此可知算法时间复杂度是O（nkm）。

算法2在一个k元n立方的m子立方体建立根结点到它内目标结点根树的过程。

算法2：

（1）从k元n立方的m子立方一个结点作为根结点，从此根结点的邻接结点中寻找目标结点，并加入此根树。若没有目标结点是根结点的邻接点，则在此k元n立方的m子立方寻找到根结点距离最近目标结点连同相应的路径加入根结点。

（2）从根子树的结点的邻接结点中寻找目标结点，并加入此根树。若没有目标结点是根子树结点的邻接点，则在此k元n立方的m子立方寻找到根子树结点距离最近目标结点连同相应的路径加入此根子树。

（3）若还有此k元n立方的m子立方中的目标结点，继续第2步。

k元n立方的m子立方体连通的多播路由算法：

输入：源结点U及目标结点U1，U2，…，Us。

输出：源结点U及到目标结点U1，U2，…，Us的路径。

（1）确定所有的目标结点U1，U2，…，Us所在的k元n立方的m子立方{O1，O2，…，Ow}；

（2）按照结点U所在的k元n立方的m子立方到O1，O2，…，Ow海明距离从小到大建立以O1，O2，…，Ow标志的动态数据结构destcubesign{D1，D2，…，D }；

（3）对destcubesign中每个元Di到已到达且海明距离最小的k元n立方的m子立方里的通路结点建立动态数据结构Nearst[Di]，初始时取U所在的k元n立方的m子立方的标号；

（4）FOR i=1 TO s

IF i=1且 O1到U所在的k元n立方的m子立方海明距离为0 TNEN

调用算法2：输入U和O1中的目标结点；

调用算法1：（输入 Nearst[Di]，Oi）；

调用算法2：输入Oi中的通路结点及Oi中的目标结点；

比较新到达k元n立方的m子立方和O1，O2，…，Ow海明距离的远近更新Nearst[Di]中的数据（到此构造了U到目标结点U1，U2，…，Us的路径。如果上述过程不能继续说明不是k元n立方的m子立方体连通的。）。

算法经过的k元n立方的m子立方个数不超过O1，O2，…，Ow到U所在的k元n立方的m子立方的海明距离之和，设此和为g，则算法的时间复杂度为O（s2gmk）。

3 结语

算法1讨论了任一个结点到给定k元n立方的m子立方体某个结点的容错路由。算法2讨论了如何在k元n立方的m子立方体中建立根到目标结点的多播树。k元n立方的m子立方体连通的多播路由算法中通过调用算法1、算法2实现了多播路由，且算法时间复杂度为O（s2gmk）。

参考文献

[1]齐芳等.超立方体网络中高可扩展和强容错多播路由算法的设计与分析[J].计算机科学，2002，z1：166-168.

[2]张涌逸.k元n立方体网络的容错路由[J].数字技术与应用，2012，09：24.