摘要
给定一个广义超立方网络以Ｇ（ｍ，ｒ）：Ｎ＝ｍｒ（ｍ≥２，ｒ≥１），其上有若干条连线发生故障，Ｆ为其故障连线集合，且 Ｇ（ｍ，ｒ）－Ｆ是连通的，Ｓ和 Ｄ是 Ｇ（ｍ，ｒ）中任意两个结点（处理器），其汉明距离 Ｈ（Ｓ， Ｄ）＝ｈ．得出如下结论：（１）当｜ｆ｜＜ｄ时，存在一条非故障路径Ｐ（Ｓ，Ｄ），且｜Ｐ（Ｓ，Ｄ）｜≤ｈ＋２； （２）当ｄ≤｜Ｆ｜＜ｍ（ｄ－ｍ＋１）时，存在一条非故障路径Ｐ（Ｓ，Ｄ），且｜Ｐ（Ｓ，Ｄ）｜≤ ｈ＋４ｍ－２．这里，ｄ是Ｇ（ｍ，ｒ）的度，｜Ｐ（Ｓ，Ｄ）｜ 是路径Ｐ（Ｓ，Ｄ）的长度，Ｐ（Ｓ，Ｄ）是非故障的是指在其上的所有连线均非故障．给出了寻径算法．
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.
出处
《北京工业大学学报》
CAS
CSCD
北大核心
2001年第3期273-281,共9页
Journal of Beijing University of Technology
基金
北京建筑工程学院青年科研基金资助项目.
