超立方网络上的平行路径

• 作者: 刘长河 童明生 范天佑
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 图论 互连网络 容错 寻径算法 超立方
• 年，卷（期）: 1999,（2）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 120-125
• 页数: 6页
• 分类号: TP301
• 字数: 5213字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.1999.02.002

摘要

超立方是分布存储系中最常用的结构.在以往的工作中,人们已经提出了不少容错寻径算法.然而,还没有考虑Hn中|F|≥2n-2的情形.在一个含有故障结点集F的n维超立方网络Hn中,|F|≤4n-24,(s0,d0),(s1,d1)是其中任意两对非故障结点,如果,(1)对于Av∈V(Hn),有|A(v,Hn-F)|≥6.(2)沿着某一维k(0≤k≤n-1),可将Hn分割成两部分:(d0∈)Hn-1,0和(d1∈)Hn-1,1,且|F∩Hn-1,i|≤2n-12(i=0,1),则一定存在两条互不相交的路径P(si,di),使得|P(si,di)|≤H(si,di)+12(i=0,1).并且,这两条路径可以并行地求得.我们给出了相应的容错寻径算法,其时间复杂性为t=O(n·|F|).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	范天佑	北京理工大学材料中心	59	306	11.0	14.0
2	童明生	北京理工大学计算中心	7	17	2.0	4.0
3	刘长河	北京建工学院基础部	3	17	2.0	3.0