logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Randomized routing with shorter paths

delete1996-04-01
delete2
PRE
AI
E
Eli Upfal *
M
Marc Snir
DOI：10.1109/71.494630delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
We study in this paper the use of randomized routing in multistage networks. While log N additional randomizing stages are needed to break ''spatial locality,'' within 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
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

IEEE Transactions on Parallel and Distributed Systems cover
IEEE Transactions on Parallel and Distributed Systems
IF:
6
Papers:
5.2K
Citations:
1.1W

Organization

No organization information available