Proceedings of the 3rd Intl. Conference on Parallel Processing - Euro-Par’97
(EN)
We examine the reliability properties of ideal fat-trees, a general model used to capture both distance and bandwidth constraints of various classes of fat-tree networks. We allow the edges and the vertices of the network to fail independently with probability f, and show that: (1) Any fat-tree G can always be partitioned into an upper (G H) and a lower (G L) part. After the faults, the remaining part of G L guarantees that a linear fraction of the leaves of the fat-tree still connect to the upper part, with high probability. (2) G H is robust, in the sense that, after the faults, at least half of the edge-disjoint paths between any set of “leaves” of G H are preserved with probability tending to 1, even in the case of failure probabilities as high as f < 0.25. The robust properties of G H hold for the case that fat-nodes do not have internal edges and also for the case that fat-nodes are random regular graphs. (3) For the special case of a pruned butterfly, there is a critical probability p c for the existence of a linear sized component surviving the failures and including a large fraction of terminal nodes. We show that p c ≥ 0.42.
(EN)
