A new routing method to tolerate both convex and concave faulty regions in mesh/torus networks

To make the exiting fault routing algorithms tolerate concave fault regions without disabling any healthy nodes, the concept of hole is proposed in this paper. A hole consists of healthy nodes in the concave parts and neighborhood of a given concave fault region. By guiding the packet routing inside and outside the hole, the new routing method empowers the convex fault tolerant routing algorithm to tolerate concave shape regions without disabling any healthy nodes. The proposed modification method is simple and does not add new virtual channels. Moreover, it doesn't change the rules of the previous algorithms. Finally, the performance of the modified routing algorithm is simulated under various concave fault patterns.