Randomized routing with shorter paths

Eli Upfal; Sergio Felperin; Marc Snir

doi:10.1109/71.494630

Randomized routing with shorter paths

Eli Upfal, Sergio Felperin, Marc Snir

Research output: Contribution to journal › Article › peer-review

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	https://doi.org/10.1109/71.494630
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

Online availability

10.1109/71.494630

Library availability

Discover UIUC Full Text

Cite this

@article{2239bc308d19437786e1a6ffe8f677ba,

title = "Randomized routing with shorter paths",

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.",

keywords = "Butterfly networks, Interconnection networks, Multistage networks, Packet-switching, Parallel communication, Randomized routing",

author = "Eli Upfal and Sergio Felperin and Marc Snir",

note = "Research at the Weizmann Institute was supported in part by The Norman D. Cohen Professorial Chair of Com- puter Science, by the Minerva Foundation, and by a grant from the Israeli Academy of Science.",

year = "1996",

doi = "10.1109/71.494630",

language = "English (US)",

volume = "7",

pages = "356--362",

journal = "IEEE Transactions on Parallel and Distributed Systems",

issn = "1045-9219",

publisher = "IEEE Computer Society",

number = "4",

}

TY - JOUR

T1 - Randomized routing with shorter paths

AU - Upfal, Eli

AU - Felperin, Sergio

AU - Snir, Marc

N1 - Research at the Weizmann Institute was supported in part by The Norman D. Cohen Professorial Chair of Com- puter Science, by the Minerva Foundation, and by a grant from the Israeli Academy of Science.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

KW - Butterfly networks

KW - Interconnection networks

KW - Multistage networks

KW - Packet-switching

KW - Parallel communication

KW - Randomized routing

UR - http://www.scopus.com/inward/record.url?scp=0030121134&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030121134&partnerID=8YFLogxK

U2 - 10.1109/71.494630

DO - 10.1109/71.494630

M3 - Article

AN - SCOPUS:0030121134

SN - 1045-9219

VL - 7

SP - 356

EP - 362

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 4

ER -

Randomized routing with shorter paths

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this