超立方体网络并行容错路由算法  

Parallel fault tolerant routing algorithms in hypercube networks

作　　者：王国军[1] 陈松乔[1] 陈建二[1] 齐芳[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《中南工业大学学报》2002年第4期424-427,共4页Journal of Central South University of Technology(Natural Science)

基　　金：国家海外杰出青年自然科学基金资助项目 ( 6 992 82 0 1);长江学者奖励计划项目 ( 1999~ 2 0 0 4 );教育部高等学校骨干教师计划基金项目 ( 2 0 0 0~ 2 0 0 2年 ) .

摘　　要：研究了具有大量错误结点的超立方体网络中的并行容错路由算法 .其步骤是 :首先 ,通过实验分析基于局部k维子立方体连通性容错模型中并行容错路由算法的容错性和效率 ,然后分析k =3且有多达 2 5 .0 %的错误结点时并行容错路由算法的容错性和效率 .研究结果表明 :并行路由算法所能找到的并行路径的数目最多可达到min(D(u) ,D(v) ) ,至少可达到min(Dk(u) ,Dk(v) ) ;如果只考虑k比较小 (如 3 ,4,5等 )而n比较大 (如 1 0 ,1 5 ,2 0等 )的情况 ,则min(D(u) ,D(v) )与min(Dk(u) ,Dk(v) )非常接近 ,说明并行路由算法所能找到的尽可能多的并行路径的能力是接近最优的 ;并行容错路由算法容错性强 。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 locally k 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 (D k(u),D k(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 (D k(u),D k(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 not only parallel routing algorithms are strong fault tolerant and highly effective and efficient, but also local connectivity fault tolerant model is applicable.

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

分 类 号：TP393.4[自动化与计算机技术—计算机应用技术] TP302.8[自动化与计算机技术—计算机科学与技术]