摘要
本文研究一般化超立方网络（GeneralizedHypercube，简记为GHC）的容错寻径算法．给定一个一般化超立方网络G（m，r）：N=mr（m≥2，r≥1），F为其故障结点集合，且G（m，r）-F是连通的，S和D是G（m，r）中任意两个非故障结点，其汉明距离H（S，D）=h，则当故障结点的个数|F|＜d时，一定存在一条长度≤h＋2的非故障路径P（S，D），而当d≤|F|＜m（d-m＋1）时，一定存在一条长度≤h＋4m-2的非故障路径P（S，D）．这里d是G（m，r）的度，路径P（S，D）是非故障的是指在P（S，D）上的所有结点均非故障．本文还给出其寻径算法．
The generalized hypercube network (GHC) can be considered as the extension of hypercube. It contains many topology structures of interconnection networks such as ring, cube, mesh and so on. Because of its high connectivity, the fault-tolerance is quite good. While, there are few researchers make research on its routing algorithms with fault-tolerance. In this paper, fault-tolerant routing algorithms in GHC are studied in detail. For a generalized hypercube network G(m,r)with faulty nodes set F, G(m,r): N=mr (m≥2,r≥1 ), |F|＜m(d－m＋1), two arbitrary fault-free nodes S and D, if G (m, r) - F is connected, there must be a fault-free path P (S, D) no longer than h + 2 from S to D when |F|<d, or no longer than h+4m-2 when da |F|< m(d-m+ 1), where d is the degree of G(m,r),h =H(S, D) is the Hamming distance between S and D, path P(S, D) is fault-free if all the nodes and links in it are fault-free. The corresponding routing algorithms when |F|< d, or d≤| F |< m (d- m + 1 ) and exists 'good dimension' aregiven in this paper.
出处
《计算机学报》
EI
CSCD
北大核心
1998年第12期1074-1083,共10页
Chinese Journal of Computers
基金
北京建工学院青年科研基金
关键词
互连网络
容错
寻径算法
计算机网络
GHC
Generalized hypercube, interconnection networks, fault-tolerance,routing algorithm
