AuthorsF. O. Sem-Jacobsen, T. Skeie and O. Lysne
EditorsH. R. Arabnia
TitleA Dynamic Fault-Torlerant Routing Algorithm for Fat-Trees
Afilliation, Communication Systems
Publication TypeProceedings, refereed
Year of Publication2005
Conference NameInternational Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, Nevada, USA, June 27-30
PublisherCSREA Press
ISBN Number1-932415-58-0

The fat tree is a network topology well suited for use as the interconnection network in systems such as parallel computers. Its large number of paths between every source/destination pair gives the fat tree the ability to provide high throughput. This also gives it a high probability of tolerating network faults statically, but few algorithms to dynamically tolerate faults in fattrees have previously been proposed. In this paper we present a deadlock free routing method for providing dynamic fault tolerance through misrouting downwards in the network. We show that the algorithm is one fault-tolerant, and that it with a certain probability can tolerate a large number of faults.

Citation KeySem-jacobsen.2005.2