Randomized routing with shorter paths
Eli Upfal, S. Felperin, Marc Snir · IEEE Transactions on Parallel and Distributed Systems · 1996
Studies the use of randomized routing in multistage networks. While log N additional randomizing stages are needed to break "spatial locality", within each permutation, only log log N additional randomizing stages are needed to break "temporal locality" among successive permutations. Thus, log N bits of initial randomization per input, followed by log log N bits of randomization per packet are sufficient to ensure that t permutations are delivered in time t+log N. We present simulation results that validate this analysis.