|Authors||F. O. Sem-Jacobsen, T. Skeie and O. Lysne|
|Editors||H. R. Arabnia|
|Title||A Dynamic Fault-Torlerant Routing Algorithm for Fat-Trees|
|Afilliation||Networks, Communication Systems|
|Publication Type||Proceedings, refereed|
|Year of Publication||2005|
|Conference Name||International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, Nevada, USA, June 27-30|
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.