Fault-tolerant routing in hypercube multicomputers using local safety information

Abstract

This paper studies fault-tolerant routing for injured hypercubes using local safety information. It is shown that a minimum feasible path is always available if the spanning subcube that contains both source and destination is safe. The safety information outside the spanning subcube is applied only when derouting is needed. A routing scheme based on local safety information is proposed and the extra cost to obtain local safety information is comparable to the one based on global safety information. The proposed algorithm guarantees to find a minimum feasible path if the spanning subcube is contained in a maximal safe subcube and the source is locally safe in the maximal safe subcube. A new technique to set up a partial path is proposed based on local safety information when the above conditions are not met. Sufficient simulation results are provided to demonstrate the effectiveness of the method by comparing with the previous methods.