AuthorsF. O. Sem-Jacobsen, T. Skeie, O. Lysne and J. Duato
EditorsW. Feng
TitleDynamic Fault Tolerance With Misrouting in Fat Trees
Afilliation, Communication Systems
Publication TypeProceedings, refereed
Year of Publication2006
Conference NameProceedings of the International Conference on Parallel Processing (ICPP)
Date PublishedAugust
PublisherIEEE Computer Society
ISBN Number22

Fault tolerance is critical for efficient utilisation of large computer systems. Dynamic fault tolerance allows the network to remain available through the occurance of faults as opposed to static fault tolerance which requires the network to be halted to reconfigure it. Although dynamic fault tolerance may lead to less efficient solutions than static fault tolerance, it allows for a much higher availability of the system. In this paper we devise a dynamic fault tolerant adaptive routing algorithm for the fat tree, a much used interconnect topology, which relies on misrouting around link faults. We show that we are guaranteed to tolerate any combination of less than (num\_switch\_ports/2) link faults without the need for additional network resources for deadlock freedom. There is also a high probability of tolerating an even larger number of link faults. Simulation results show that network performance degrades very little when faults are dynamically tolerated.

Citation KeySem-jacobsen.2006.1