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

摘要

本文讨论具有大量错误结点的超立方体网络中的并行路由算法.假定Hn是一个局部 k-维子立方体连通的n-维超立方体网络,本文提出的并行路由算法能够找出至少K=min (Dk( u),Dk(v))条并行路径, 其中每一条路径的长度不超过(dH(Uk,Vk)+3)2k.该算法的时间复杂度为O(Kn2k).这里, 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倍源结点和目的结点之间的海明距离之内.该算法只要求结点知道其邻结点的状态,而无需知道整个网络信息,也就是说,该算法是基于局部信息的,因而该算法具有很强的实际意义.