AuthorsN. A. Nordbotten, M. E. Gómez, J. Flich, P. Lopez, A. Robles, T. Skeie, O. Lysne and J. Duato
TitleA Fully Adaptive Fault-Tolerant Routing Methodology Based on Intermediate Nodes
Afilliation, Communication Systems
Publication TypeProceedings, refereed
Year of Publication2004
Conference NameProceedings of IFIP International Conference on Network and Parallel Computing
Date PublishedOctober 18-20

Massively parallel computing systems are being built with thousands of nodes. Because of the high number of components, it is critical to keep these systems running even in the presence of failures. Interconnection networks play a key-role in these systems, and this paper proposes a fault-tolerant routing methodology for use in such networks. The methodology supports any minimal routing function (including fully adaptive routing), does not degrade performance in the absence of faults, does not disable any healthy node, and is easy to implement both in meshes and tori. In order to avoid network failures, the methodology uses a simple mechanism: for some source-destination pairs, packets are forwarded to the destination node through a set of intermediate nodes (without being ejected from the network). The methodology is shown to tolerate a large number of faults (e.g., five/nine faults when using two/three intermediate nodes in a 3D torus). Furthermore, the methodology offers a gracious performance degradation: in an 8 × 8 × 8 torus network with 14 faults the throughput is only decreased by 6.49%.

Citation KeyND.5.Nordbotten.2004