Fault-tolerant routing strategy in hypercube systems

We investigate fault-tolerant routing which aims at finding feasible minimal paths in a faulty hypercube. The concept of an unsafe node is adopted to identify nodes that may cause routing difficulties. We propose a set of stringent criteria to reduce the number of fault free nodes that are labeled unsafe. Routing efficiency can thus be improved. An algorithm is presented to facilitate the routing of messages. It only requires each node to maintain information about its local state, whereby each node is in one of four states. The issue of deadlock freeness is also addressed. Furthermore, an alternative deadlock-free routing algorithm, which requires a constant of five virtual networks in wormhole routing, is presented.<>