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

• 作者: 王国军 陈建二 陈松乔
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 容错性 超立方体网络 局部连通性 并行路由算法
• 年，卷（期）: 2001,（5）
• 所属期刊栏目: 容错体系结构
• 页码范围: 5-12
• 页数: 8页
• 分类号: TP30
• 字数: 11863字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2001.05.002

摘要

本文讨论具有大量错误结点的超立方体网络中的并行路由算法.假定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倍源结点和目的结点之间的海明距离之内.该算法只要求结点知道其邻结点的状态,而无需知道整个网络信息,也就是说,该算法是基于局部信息的,因而该算法具有很强的实际意义.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王国军	中南大学信息科学与工程学院	123	760	12.0	19.0
2	陈建二	中南大学信息科学与工程学院	167	1535	20.0	30.0
3	陈松乔	中南大学信息科学与工程学院	316	3775	27.0	45.0