FAULT-TOLERANT WORMHOLE ROUTING ALGORITHMS FOR MESH NETWORKS

We present simple methods to enhance the current minimal wormhole rout ing algorithms developed for high-radix, low-dimensional mesh networks for fault-tolerant routing, We consider arbitrarily-located faulty bl ocks and assume only local knowledge of faults, Messages are routed mi nimally when not blocked by faults and this constraint is relaxed to r oute around faults, The key concept we use is a fault ring consisting of fault-free nodes and links can be formed around each fault region, Our fault-tolerant techniques use these fault rings to route messages around fault regions, We show that, using just one extra virtual chann el per physical channel, the well-known e-cube algorithm can be used t o provide deadlock-free routing in networks with nonoverlapping fault rings; there is no restriction on the number of faults, For the more c omplex faults with overlapping fault rings, four virtual channels are used, We also prove that at most four additional virtual channels are sufficient to make fully-adaptive algorithms tolerant to multiple faul ty blocks in n-dimensional meshes, All these algorithms are deadlock- and livelock-free. Further, we present simulation results for the e-cu be and a fully-adaptive algorithm fortified with our fault-tolerant ro uting techniques and show that good performance may be obtained with a s many as 10% links faulty.