A New Fault- Tolerant Routing Scheme for 2-Dimesnsioal 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 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.
mesh networks fault tolerance k-submesh-connected routing algorithm
Gaocai Wang Jianer Chen
College of Information Science and Engineering Central South University, Changsha, 410083, China
国际会议
成都
英文
95-98
2003-08-27（万方平台首次上网日期，不代表论文的发表时间）