Clyde P. Kruskal, Larry Rudolph, et al.
Theoretical Computer Science
We study in this paper the use of randomized routing in multistage networks. While log N additional randomizing stages are needed to break "spatial localitywithin 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. ©1996 IEEE.
Clyde P. Kruskal, Larry Rudolph, et al.
Theoretical Computer Science
Andrei Z. Broder, Alan M. Frieze, et al.
Random Structures and Algorithms
Don Coppersmith, Peter Doyle, et al.
Journal of the ACM (JACM)
Prabhakar Raghavan, Eli Upfal
STOC 1994