The Two-Level-Turn-Model Fault-tolerant Routing Scheme in Tori with Convex Faults

In this paper, we would present a fault-tolerant wormhole routing scheme, called two-level-turn-model scheme, in the tori with convex faults. The reason why we choose the convex faults is that the shape of the convex faults is instrumental to design an effective fault-tolerant routing algorithm. Compared with many other solutions, which mainly focus on providing extra virtual channels to tolerate the faults, one of the advantages of our solution is that it is based on the turn model, which itself could tolerate some faults for some messages. At the same time, our solution could work effectively no matter where the fault region locates and no matter whether the fault regions are connected. In our solution, two patterns of the turn model are complementary to tolerate the faults. With a few limits to the shape of the convex faults, at most five virtual channels per physical channel are required to avoid the deadlock.