A GENERAL FRAMEWORK FOR DEVELOPING ADAPTIVE FAULT-TOLERANT ROUTING ALGORITHMS

Cartesian-product (CP) graphs have begun to receive attention because they-include many popular topologies such as cubes, meshes, and tori; enjoy many interesting topological and synthesizing properties; provid e a theoretical framework for general design and analysis of fixed int erconnection networks. General, fault-free algorithms for routing & em bedding on general CP-networks have been designed, but no work has add ressed the fault-tolerance and reliability of CP-networks. This work d emonstrates that CP-network methods provide a useful framework for the design of reliable parallel-computer systems. Given component network s with prespecified connectivity, more complex networks with known con nectivity and terminal reliability (Pr {at least 1 path exists between any pair of nodes}) can be developed. CP-networks provide systematic techniques for developing reliable fault-tolerant routing schemes, eve n for very complex topological structures. The paper-establishes the t heoretical foundations that relate the connectivity of a CP-network, t he connectivity of the component networks, and the number of faulty co mponents presents an adaptive generic algorithm which can perform succ essful point-to-point routing, in the presence of faults. synthesizes, using the theoretical results, this adaptive fault-tolerant algorithm s from algorithms written for the component networks. proves the corre ctness of the algorithm shows that the algorithm ensures following an optimal path, in the presence of many faults, with high probability. T he algorithm directly applies to most of the commonly used, fixed inte rconnection networks.