A collision model for randomized routing in fat-tree networks

We present a proof that in a model of a fat-tree network with n processing nodes m⩽n messages with randomly chosen, distinct sources and independently and randomly chosen destinations are delivered within O(lgm) delivery rounds with high probability. More succinctly, we establish that m messages are delivered in O(lgm+ln1/ε) delivery rounds with probability 1-ε for any small ε>0. Unlike previously applied proof methods, we use an approximating model for the collision behavior of the network amenable to concise yet simple theoretical analysis. We justify the accuracy of the approximation by means of behavioral simulations based on a gate-level implementation of a fat-tree network.