|Authors||I. T. T. Theiss and O. Lysne|
|Title||FRoots, a Fault Tolerant and Topology Agnostic Routing Technique|
|Afilliation||, Communication Systems|
|Publication Type||Journal Article|
|Year of Publication||2006|
|Journal||IEEE Transactions on Parallel and Distributed Systems|
Existing solutions for fault tolerant routing in interconnection networks either work for only one given regular topology, or they require slow and costly network reconfigurations which cannot allow full and continuous network access. In this paper we present FRroots, a routing method for fault tolerance in topology-agnostic network technologies. Our method is based on redundant paths, and it can handle single dynamic faults without the need for sending control messages. In the fault-free networks under non-uniform traffic it performs comparable to, or even better than, topology specific and non-fault tolerant routing algorithms in regular networks like meshes and tori. FRoots does not require any other features in the switches than a flexible routing table, and a modest number of virtual channels. For that reason it can be directly applied to several present day technologies like InfiniBand and Advanced Switching.