Low-Memory Techniques for Routing and Fault-Tolerance on the Fat-Tree Topology
Crispín Gómez Requena · 2010
Currently, clusters of PCs are considered a cost-effective alternative to large parallel computers.In these systems, thousands of computing nodes are connected through a high-performance interconnection network.The interconnection network must be carefully designed, since it heavily impacts the performance of the whole system.Two of the main design parameters of the interconnection networks are topology and routing.Topology defines the interconnection of the elements of the network among themselves, and between them and the computing nodes.Routing defines the paths followed by the packets through the interconnection network.Performance has traditionally been the main metric to evaluate the interconnection network.However, we have to consider two additional metrics nowadays: cost and fault-tolerance.Interconnection networks have to scale in terms of cost, in addition to scale in performance.That is, they not only need to maintain their performance as the system size is increased, but also without heavily increasing their cost.On the other hand, as the number of nodes increases in cluster-based machines, the interconnection network grows accordingly.This increase in the number of elements of the interconnection network raises the probability of faults, and thus, fault-tolerance has become mandatory for current interconnection networks.This dissertation focus on the fat-tree topology, which is one of the mostcommonly 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 xvii xviii