Adaptive fault-tolerant routing in hypercube multicomputers

Abstract

A connected hypercube with faulty links and/or nodes is called an injured hypercube. To enable any non-faulty node to communicate with any other non-faulty node, information on component failures has to be made available to non-faulty nodes so as to route messages around the faulty components. A distributed adaptive fault tolerant routing scheme is proposed in which each node is required to know only the condition of its own links. This scheme is shown to be capable of routing messages successfully as long as the number of faulty components is less than n (the dimension of the hypercube), and to route messages via shortest paths with a rather high probability. A second routing scheme based on depth-first search is proposed which works in the presence of an arbitrary number of faulty components; however, the paths chosen by this may not always be the shortest. To guarantee shortest paths, every mode must be given information beyond that on its own links; the additional information to be kept at each node for shortest-path routing is determined. Several examples are given to illustrate the results.