DEADLOCK-FREE FAULT-TOLERANT ROUTING IN INJURED HYPERCUBES

Abstract

Wormhole routing with the e-cube algorithm is an excellent solution for deadlock-free interprocess communication in healthy hypercubes. However, it does not work for injured hypercubes where some nodes and/or links are faulty. In this paper, we propose a new deadlock-free routing scheme in an injured hypercube with the wormhole routing capability. All previously proposed schemes suggest the use of virtual channels to avoid the cycle of resource dependency. By contrast, our scheme is based on the re-establishment of a routing path to the destination, but it does not always yield a shortest path between the source and destination. The proposed routing scheme uses either wormhole routing or staged routing, depending on the availability of one or more healthy (n - 2)-cubes within an injured n-cube, Q(n). Every node decides the availability of a healthy Q(n-2) independent of others based on the information of faulty components broadcast to the node. To establish a deadlock-free path between every pair of nodes in an injured Q(n) using wormhole routing alone, there must exist at least one healthy Q(n-2) within the Q(n). Clearly, when the number of faults increases, it is less likely a healthy Q(n-2) will exist in the injured Q(n). In case no healthy Q(n-2) exists within an injured Q(n), our scheme switches to staged routing. The proposed scheme is analyzed in terms of robustness and average number of message hops, and is compared with a previously proposed virtual channel scheme. Our analytical results show that one can find at least one healthy Q(n-2) until approximately 2n (n < 10) nodes become faulty, and the increase in average message distance is at most one hop. Our simulation results show that the proposed scheme yields a smaller message latency and a higher percentage of successful message delivery than the virtual channel scheme.