A New Fault-Tolerant Routing Scheme for N-dimesional Mesh

Fault tolerance is one of the most important issues for the design of cost-effective and high performance interconnection networks. In this paper, a new fault tolerance routing algorithm for n-dimensional meshes is presented. The presented algorithm is based on a planer fault model which only disables minimum fault-free nodes to form rectangular fault regions. The algorithm uses three virtual channels per physical channel and only employs a very simple deadlock avoidance scheme. In spit the variety fault regions in n-dimensional mesh, the presented algorithm is always connected as long as fault regions do not disconnect the network. The result of simulation shows that the proposed routing algorithm is of feasibility of gracefully degraded operation.