Efficient randomized routing on Clos networks
A. Youssef · 2002
Clos networks are well-known universal multistage networks that realize all permutations. However, the routing algorithms to realize permutations on these networks are so slow that their usefulness is severely limited. This paper gives a simple, efficient randomized algorithm that routes any given permutation on Clos networks. Randomization takes place in the first column of the network, while self-routing is used in the remaining columns. Probabilistic analysis of the algorithm is conducted and the queueing delay of any permutation is shown to be bounded by a small constant (>