RANDOMIZED ROUTING WITH SHORTER PATHS

Authors
UPFAL E FELPERIN S SNIR M
Citation
E. Upfal et al., RANDOMIZED ROUTING WITH SHORTER PATHS, IEEE transactions on parallel and distributed systems, 7(4), 1996, pp. 356-362
Citations number
17
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
Journal title
IEEE transactions on parallel and distributed systems → ACNP
ISSN journal
10459219
Volume
7
Issue
4
Year of publication
1996
Pages
356 - 362
Database
ISI
SICI code
1045-9219(1996)7:4<356:RRWSP>2.0.ZU;2-F
Abstract
We study in this paper the use of randomized routing in multistage net works. While log N additional randomizing stages are needed to break ' 'spatial locality,'' within each permutation, only log log N additiona l randomizing-stages are needed to break ''temporal locality'' among s uccessive permutations. Thus, log N bits of initial randomization per input, followed by log log N bits of randomization per packet are suff icient to ensure that t permutations are delivered in time t + log N. We present simulation results that validate this analysis.