自然科学版 英文版
自然科学版 英文版
自然科学版 英文版

您目前所在的位置:首页 - 期刊简介 - 详细页面

中南大学学报(自然科学版)

Journal of Central South University

第33卷    第4期    总第146期    2002年8月

[PDF全文下载]    [Flash在线阅读]

    

文章编号:1005-9792(2002)04-0424-04
超立方体网络并行容错路由算法
王国军,陈松乔,陈建二,齐 芳

(中南大学信息科学与工程学院,湖南长沙 410083)

摘 要: 研究了具有大量错误结点的超立方体网络中的并行容错路由算法.其步骤是:首先,通过实验分析基于局部k维子立方体连通性容错模型中并行容错路由算法的容错性和效率,然后分析k=3且有多达25.0%的错误结点时并行容错路由算法的容错性和效率.研究结果表明:并行路由算法所能找到的并行路径的数目最多可达到min(D(u),D(v)),至少可达到min(Dk (u),Dk(v));如果只考虑k比较小(如3,4,5等)而n比较大(如10,15,20等)的情况,则min(D(u),D(v))与min(Dk (u),Dk (v))非常接近,说明并行路由算法所能找到的尽可能多的并行路径的能力是接近最优的;并行容错路由算法容错性强,效率高.

 

关键字: 互联网络;超立方体网络;并行容错路由算法;局部连通性

Parallel fault tolerant routing algorithms in hypercube networks
WANG Guo-jun,CHEN Song-qiao,CHEN Jian-er,QI Fang

College of Information Science and Engineering, Central South University, Changsha 410083, China

Abstract:Parallel fault tolerant routing algorithms in hypercube networks with a large number of faulty nodes are studied.Using experimental results, the fault tolerance and effectiveness and efficiency of parallel fault tolerant routing algorithm are analysed, which is based on both locallyk-subcube-connected fault tolerant model and locally 3-subcube-connected fault tolerant model with up to 25.0% faulty nodes. It is well known that the number of parallel paths which can be found by a parallel routing algorithm is at most min(D(u),D(v)), and at least min(Dk(u),Dk(v)). Considering that k is small (such as 3, 4 or 5), and that n is large (such as 10, 15, 20 or 30), then min(D(u),D(v)) is very close to min(Dk(u),Dk(v)). In this way, the capability of finding the parallel routing paths as much as possible is near optimal. The theoretical analysis and the experimental results show that notonly parallel routing algorithms are strong fault tolerant and highly effective and efficient, but also local-connectivity fault tolerant model is applicable.

 

Key words: interconnection network; hypercube network; parallel fault tolerant routing algorithm; local-connectivity

中南大学学报(自然科学版)
  ISSN 1672-7207
CN 43-1426/N
ZDXZAC
中南大学学报(英文版)
  ISSN 2095-2899
CN 43-1516/TB
JCSTFT
版权所有:《中南大学学报(自然科学版、英文版)》编辑部
地 址:湖南省长沙市中南大学 邮编: 410083
电 话: 0731-88879765 传真: 0731-88877727
电子邮箱:zngdxb@csu.edu.cn 湘ICP备09001153号