A unified fault-tolerant routing scheme for a class of cluster networks

Large cluster systems with thousands of nodes have become a cost-effective alternative to traditional supercomputers. In these systems cluster nodes are interconnected using high-degree switches. Regular direct interconnection network topologies including tori (k-ary n-cubes) and meshes are among adapted choices for interconnecting these high-degree switches. We propose a generalized fault-tolerant routing scheme for highly connected regular interconnection networks and derive conditions for its applicability. The scheme is based on the availability of efficiently identifiable disjoint routes between network nodes. When routing paths become faulty, alternative disjoint routes are identified and taken. The methods used to identify the routing paths, to propagate failure information, and to switch from a routing path to another incur little communication and computation overhead. If the faults occur reasonably apart in time, then packets are efficiently routed along paths of minimal or near-minimal lengths. In the unlikely case where several faults occur in a short period of time, the scheme still delivers packets but possibly along longer paths. The proposed scheme and its properties are first presented in general terms for any interconnection topology satisfying certain derived connectivity conditions. The applicability of the general scheme is then illustrated on examples of well known regular topologies satisfying the derived connectivity conditions including the binary hypercube, the k-ary n-cube and the star graph networks.