Fault-tolerant orthogonal fat-trees as interconnection networks

Orthogonal fat-trees are a type of interconnection network with several desirable characteristics: short distance between processors, constant degree of the switching elements, uniform traffic load, symmetry, and recursive scalability. We first show how to build two-level orthogonal fat-trees, where each node has a fixed degree and there is a maximum distance of two between any two leaves. We then show how to provide fault tolerance by including redundant paths at the cost of reducing the number of leaves. Finally, we show how to construct large orthogonal fat-trees from two-level fat-trees recursively