具有大量错误结点的超立方体网络中并行路由算法

本文讨论具有大量错误结点的超立方体网络中的并行路由算法。假定Hn是一个局部k-维子立方体连通用的n-维超立方体网络，本文提出的并行路由算法能够找出至少K=min（Dk(u),Dk(v）条并行路径，其中每一条路径的长度不超过（dH(Uk,Vk）＋3）2^k。该算法的时间复杂度为O（Kn2^k）。这里，Dk(u）和Dk(v）分别代表源结点u和目的结点v的正确的邻结点个数（不考虑u和v所在的k－维子立方体内部的邻结点），dH(Uk,Vk）代表源结点u和目的结点v所在的两个k－维子立方体Uk和Vk之间的海明距离。本文还考察了了k=3的特殊情况，在k=3并且有分别不超过12．5％和25％的错误结点的情况下，该算法的时间复杂度为O（Kn），并且每一条路径的路径长度分别在大约1．5和2倍源结点和目的结点之间的海明距离之内。该算法只要求结点知道其邻结点的状态，而无需知道整个网络信息，也就是说，该算法是基于局部信息的，因而该算法具有很强的实际意义。

Parallel Routing Algorithms for Hypercube Networks with a Large Number of Faulty Nodes

In this paper, we consider the parallel routing problem in hypercube networks with a large number of faulty nodes. Under the assumption that H n is a locally k-subcube-connected hypercube network, we propose a par allel routing a lgor ithm and prove that at least -K=-min-(D k(u),D k(v)) -parallel paths can b e found by t he algorithm in time O-(Kn2 k), -each of which has the length bounded by - (d H(U k,V k) +3)2 k. -Here,- u -is the source node;- v -is the destination node;- D k(u) -and- D k(v) -re present the numbers of non-faulty neighbors of the source node- u -and the de stina tion node- v -respectively, without considering the neighbors within the corr esponding- k--subcubes;- U k -and- V k -are the two basic- k--subcub es containing the sour ce node- u- and the destination node- v -respectively; and- d H(U k,V k) -stands for the Hamming distance between the two basic -k--subcubes- U k -and- V k. -In particular, we p oint out that when -k- is 3 and on the condition that there are up to 12 5% a nd 25 % respectively, our parallel routing algorithm takes O-(Kn)- time and that each path found has the length bounded by about 1 5 and 2 times the Hamming dis tance between the two nodes. Moreover, our parallel routing algorithm is distributed and local-information-based in the sense that each node in the network knows o nl y its neighbors' status and no global information of the network is required by the algorithm.-