A fault-tolerant routing scheme for meshes with nonconvex faults

In this paper, we propose a fault-tolerant routing scheme for meshes with solid faults. A Rag bit is introduced for guiding misrouted messages. By fully utilizing virtual channels of each class, our algorithm uses only three virtual channels to ensure the property of deadlock freeness. Our scheme is able to handle solid faults whose associated fault rings overlap. In addition, the proposed algorithm can be used to route messages when fault regions touch the boundaries of the mesh