A new fault-tolerant routing scheme for 2-dimensional mesh networks

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 nonfaulty nodes. We focus on fault-tolerant routing algorithm for 2D mesh. We propose a novel and simple fault tolerant routing algorithm based on the concept of k-submesh - connected without virtual channels and not sacrificed nonfaulty 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.