超立方体网络下的自适应容错路由研究

Research of adaptive fault tolerant routing algorithm in hypercube networks

针对超立方体结构的多处理机系统出现故障的问题,对容错超立方体网络的局部连通性进行了研究。根据局部连通性的特点定义了相邻节点集合类的概念,提出并证明了求解两类相邻节点集合的公式。给出了满足任意子连通性条件的超立方体网络的自适应容错路由算法。该算法是分布式和基于局部信息的,可以预防死锁。仿真实验的结果表明算法是高效的,且构建的路径长度接近于最优路径长度。

In order to deal with the fault possibility of computers and links in hypercube multi-computer system, this paper studied local connectivity of fault tolerant hypercube networks. The concept of the neighbor sets of present node had been defined in accordance with the characteristics of local connectivity. The formula which could solve two kinds of sets of neighbor nodes was proposed and proved. This paper developed an adaptive fault tolerant routing algorithm for arbitrary subcube-connetted hypereube networks. This algorithm was distributed and based on local information, and it could prevent deadlock. Simulation results show that this algorithm is efficient and the length of the routing path constructed by this algorithm is close to the optimal length.