Fault-Tolerant de Bruijn and Shuffle-Exchange Networks

This paper addresses the problem of creating a fault- tolerant interconnection network for a parallel computer. Three topolo-gies, namely, the base-2 de Bruijn graph, the base-m de Brutin graph, and the shuffle-exchange, are studied. For each topology an N + k node fault-tolerant graph is defined. These fault-tolerant graphs have the property that given any set of k node faults, the remaining N nodes contain the desired topology as a subgraph. All of the constructions given here are the best known in terms of the degree of the fault-tolerant graph. We also investigate the use of buses to reduce the degrees of the fault-tolerant graphs still further. © 1994 IEEE