DEADLOCK-FREE FAULT-TOLERANT ROUTING IN INJURED HYPERCUBES

Wormhole routing with the e-cube algorithm is an excellent solution fo r deadlock-free interprocess communication in healthy hypercubes. Howe ver, it does not work for injured hypercubes where some nodes and/or l inks 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 ba sed on the re-establishment of a routing path to the destination, but it does not always yield a shortest path between the source and destin ation. The proposed routing scheme uses either wormhole routing or sta ged routing, depending on the availability of one or more healthy (n - 2)-cubes within an injured n-cube, Q(n). Every node decides the avail ability of a healthy Q(n-2) independent of others based on the informa tion of faulty components broadcast to the node. To establish a deadlo ck-free path between every pair of nodes in an injured Q(n) using worm hole routing alone, there must exist at least one healthy Q(n-2) withi n the Q(n). Clearly, when the number of faults increases, it is less l ikely a healthy Q(n-2) will exist in the injured Q(n). In case no heal thy Q(n-2) exists within an injured Q(n), our scheme switches to stage d routing. The proposed scheme is analyzed in terms of robustness and average number of message hops, and is compared with a previously prop osed 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 mos t one hop. Our simulation results show that the proposed scheme yields a smaller message latency and a higher percentage of successful messa ge delivery than the virtual channel scheme.