This paper presents a fault-tolerant multicast scheme for hypercube multicomputers. The method is based on the routing capability information that is stored in each node. In comparison with the previous schemes, this information is able to capture the fault status more precisely. Two multicast algorithms are presented in the paper. These algorithms multicast messages in an attempt to minimize derouting so that time optimality can be achieved. Moreover, the routing capability information is used to guide derouting in an efficient manner when such needs arise. The amount of traffic incurred is addressed in the paper. The hardware design for the algorithms is also discussed. Extensive simulation has been conducted to evaluate the performance of the scheme. The results show the effectiveness of the proposed algorithms.

The concept of routing capability is proposed to assist fault-tolerant routing in hypercubes. Routing capability is defined with respect to the entire spectrum of distance. As a result, the amount of information that is useful for message routing is increased. An algorithm is presented to facilitate efficient fault-tolerant routing of messages. The algorithm routes a message in an attempt to minimize derouting. Furthermore, the concept of directed routing capability which contains more useful information for fault-tolerant routing is introduced. Simulation results demonstrate the usefulness of our approach.

This paper addresses fault-tolerant routing which is concerned with finding feasible minimum paths in a faulty hypercube. The concept of routing capability, which is defined with respect to the entire spectrum of distance, is proposed to assist routing function. The amount of information that is useful for message routing is increased with our scheme. The proposed algorithm routes a message in an attempt to minimize derouting. In particular, it makes use of the information embedded in routing capabilities to establish a path for a message for which an upper bound on its length may be determined at the source. We then propose the notion of directed routing capability which captures more useful information for shortest path routing in comparison with undirected counterpart. Routing in hypercubes with link failures is also addressed.