摘要:
给定一个广义超立方网络以G(m,r):N=mr(m≥2,r≥1),其上有若干条连线发生故障,F为其故障连线集合,且 G(m,r)-F是连通的,S和 D是 G(m,r)中任意两个结点(处理器),其汉明距离 H(S, D)=h.得出如下结论:(1)当|F|<d时,存在一条非故障路径P(S,D),且|P(S,D)|≤h+2; (2)当d≤|F|<m(d-m+1)时,存在一条非故障路径P(S,D),且|P(S,D)|≤ h+4m-2.这里,d是G(m,r)的度,|P(S,D)|是路径P(S,D)的长度,P(S,D)是非故障的是指在其上的所有连线均非故障.给出了寻径算法.
Abstract:
The fault-tolerance routing algorithms on generalized hypercube networks with the set of faulty links are studied. Let G(m, r): N= mr (m ≥ 2, r ≥ 1), be a generalized hypercube networks with the set of faulty links F, |F| denotes the number of elements in F and the graph G(m, r) - F is connected. S and D are two nodes, between which the Hamming distance is H(S, D) = h. Then, there are conclusions as following:(1) If |F| < d, there is a fault-free path P(S, D), such that |P(S, D)| ≤h+2; (2) If d≤ |F| <m(d-m+ 1), there is a fault-free path P(S, D), such that |P(S, D)| ≤ h + 4m - 2. where, | P(S, D) | is the length of Path P(S, D) and d is the degree of G(m, r). Path P(S, D) is fault-free means that there is no faulty links on it. The corresponding routing algorithms are proposed in this paper.
下载:
