Randomized routing with shorter paths

Eli Upfal, Sergio Felperin, Marc Snir

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)356-362
Number of pages7
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number4
StatePublished - 1996
Externally publishedYes


  • Butterfly networks
  • Interconnection networks
  • Multistage networks
  • Packet-switching
  • Parallel communication
  • Randomized routing

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this