Exploiting the Fat-tree Topology for Routing and Fault-Tolerance

This book focus on the fat-tree topology which is one of the most-commonly used topologies for clusters. Our aim is to exploit its characteristics to provide fault-tolerance; and a load-balanced routing algorithm that provides a good cost/performance tradeoff. First we focus on the fault-tolerance of the fat-tree topology. Most of the works in the literature provide fault-tolerance at the cost of adding resources to the network either switches links or virtual channels. On the contrary to these works we provide the same degree of fault-tolerance without increasing the resources of the network by taking advantage of the abundant plurality of equivalent paths in the fat-tree. Next we take the challenge of designing a deterministic routing algorithm that can compete in terms of performance with the adaptive routing algorithms that are used for the fat-tree topology. Finally we take advantage of the particular characteristics of the proposed deterministic routing algorithm to simplify the fat-tree topology.