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

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

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

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.-