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

来源期刊：中南大学学报(自然科学版)2002年第4期

论文作者：王国军 陈松乔 陈建二 齐芳

文章页码：424 - 427

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

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

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

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(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 notonly parallel routing algorithms are strong fault tolerant and highly effective and efficient, but also local-connectivity fault tolerant model is applicable.