Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 356-362 |
| Number of pages | 7 |
| Journal | IEEE Transactions on Parallel and Distributed Systems |
| Volume | 7 |
| Issue number | 4 |
| DOIs | |
| State | Published - 1996 |
| Externally published | Yes |
Keywords
- 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
Fingerprint
Dive into the research topics of 'Randomized routing with shorter paths'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS