超立方网络上的平行路径

PARALLEL PATHS ON HYPERCUBE NETWORKS

超立方是分布存储系中最常用的结构．在以往的工作中，人们已经提出了不少容错寻径算法．然而，还没有考虑Ｈｎ中｜Ｆ｜２ｎ－２的情形．在一个含有故障结点集Ｆ的ｎ维超立方网络Ｈｎ中，｜Ｆ｜４ｎ－２４，（ｓ０，ｄ０），（ｓ１，ｄ１）是其中任意两对非故障结点，如果，（１）对于ｖ∈Ｖ（Ｈｎ），有｜Ａ（ｖ，Ｈｎ－Ｆ）｜６．（２）沿着某一维ｋ（０ｋｎ－１），可将Ｈｎ分割成两部分：（ｄ０∈）Ｈｎ－１，０和（ｄ１∈）Ｈｎ－１，１，且｜Ｆ∩Ｈｎ－１，ｉ｜２ｎ－１２（ｉ＝０，１），则一定存在两条互不相交的路径Ｐ（ｓｉ，ｄｉ），使得｜Ｐ（ｓｉ，ｄｉ）｜Ｈ（ｓｉ，ｄｉ）＋１２（ｉ＝０，１）．并且，这两条路径可以并行地求得．我们给出了相应的容错寻径算法，其时间复杂性为ｔ＝Ｏ（ｎ·｜Ｆ｜）．

Hypercube is one of the most commonly used topological structures for distributed memory systems. There have been a number of fault tolerant routing algorithm proposed in previous work. While, none of these previous schemes can work when there are more than 2 n -2 processors failed in a system of multiprocessors connected with n dimensional hypercube network. In this paper, this problem is deeply studied.Let H n be a n dimensional Hypercube network with fault node set F,|F|4n-24,(n>10),(s 0,d 0) and ( s 1,d 1 ) be two pairs of nodes in H n-F . If they satisfy, (1) |A(v, H n-F)|6 for arbitrary v∈V(H n) .(2) H n can be parted into two subgraphs, ( d 0∈)H n-1,0 and (d 1∈)H n-1,1 , and |F∩H n-1,i |2n-12, for i=0,1. Then,there are two disjoint fault free paths P(s i,d i) ,such that, |P(s i,d i)|H(s i,d i)+12,(i=0,1), and the two paths can be parallel constructed.The corresponding fault tolerant routing algorithm which its time complexity is t=O(n· |F|) is given in this paper.