A New Fault-Tolerant Routing Scheme for 2-Dimesnsioal Mesh Networks
Conference Paper
Overview
Additional Document Info
View All
Overview
abstract
Previous methods of making fault tolerant routing algorithm for mesh-connected multicomputers have been based on adding virtual channels to these networks or sacrificed some non-faulty nodes. In this paper, we focus on fault-tolerant routing algorithm for 2-D mesh. This paper proposes a novel and simple fault tolerant routing algorithm based on the concept of k-submesh-connected without virtual channels and not sacrificed non-faulty nodes on mesh networks. On the one hand, the proposed algorithm is local information based in the sense, because each node knows only its neighbors' status and no global information of the networks is required by the algorithm in the course of routing, on the other hand, for a given pair of source node and destination node, when the routing path extends in each k-submesh, this k-submesh can independently finish routing operations and the algorithm does not consider the status of operations in other k-submeshes, so the algorithm is highly distributed. The running time of the routing algorithm is optimal. Simulation results show that the length of the routing path constructed by this algorithm is very close to the optimal length.
