Name
Title | ||
|---|---|---|
sFtree: A fully connected and deadlock-free switch-to-switch routing algorithm for fat-trees |
Abstract | ||
|---|---|---|
Existing fat-tree routing algorithms fully exploit the path diversity of a fat-tree topology in the context of compute node traffic, but they lack support for deadlock-free and fully connected switch-to-switch communication. Such support is crucial for efficient system management, for example, in InfiniBand (IB) systems. With the general increase in system management capabilities found in modern InfiniBand switches, the lack of deadlock-free switch-to-switch communication is a problem for fat-tree-based IB installations because management traffic might cause routing deadlocks that bring the whole system down. This lack of deadlock-free communication affects all system management and diagnostic tools using LID routing. In this paper, we propose the sFtree routing algorithm that guarantees deadlock-free and fully connected switch-to-switch communication in fat-trees while maintaining the properties of the current fat-tree algorithm. We prove that the algorithm is deadlock free and we implement it in OpenSM for evaluation. We evaluate the performance of the sFtree algorithm experimentally on a small cluster and we do a large-scale evaluation through simulations. The results confirm that the sFtree routing algorithm is deadlock-free and show that the impact of switch-to-switch management traffic on the end-node traffic is negligible. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2086696.2086734 | TACO |
Keywords | Field | DocType |
deadlock-free communication,lid routing,switch-to-switch communication,deadlock-free switch-to-switch communication,management traffic,sftree algorithm,fat-tree routing,sftree routing algorithm,current fat-tree algorithm,efficient system management,switches,routing,system management,deadlock | Link-state routing protocol,Equal-cost multi-path routing,Multipath routing,Dynamic Source Routing,Static routing,Computer science,Computer network,Real-time computing,Distributed computing,Policy-based routing,Parallel computing,Destination-Sequenced Distance Vector routing,Distance-vector routing protocol | Journal |
Volume | Issue | ISSN |
8 | 4 | 1544-3566 |
Citations | PageRank | References |
2 | 0.39 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bartosz Bogdanski | 1 | 41 | 4.53 |
| Sven-Arne Reinemo | 2 | 184 | 12.64 |
| Frank Olaf Sem-Jacobsen | 3 | 66 | 7.64 |
| Ernst Gunnar Gran | 4 | 97 | 9.60 |