AuthorsM. E. Gómez, J. Duato, J. Flich, P. Lopez, A. Robles, N. A. Nordbotten, T. Skeie, and O. Lysne
TitleA New Adaptive Fault-Tolerant Routing Methodology for Direct Networks
AfilliationNetworks, Communication Systems
StatusPublished
Publication TypeProceedings, refereed
Year of Publication2004
Conference NameProceedings of the International Conference on High Performance Computing
Pagination462-473
Date PublishedDecember 19-22
PublisherSpringer-Verlag
Abstract

Interconnection networks play a key role in the fault tolerance of massively parallel computers, since faults may isolate a large fraction of the machine containing many healthy nodes. In this paper, we present a methodology to design fully adaptive fault-tolerant routing algorithms for direct interconnection networks that can be applied to different regular topologies. The methodology is mainly based on the selection of an intermediate node (if needed) for each source-destination pair. Packets are adaptively routed to the intermediate node and, from this node, they are adaptively forwarded to their destination. This methodology requires only one additional virtual channel, even for tori. Evaluation results show that the methodology is 7-fault tolerant, and for up to 14 faults, more than 99% of the combinations are tolerated, also without significantly degrading performance in the presence of faults.

Citation KeyND.5.Gomez.2004.b