Universal wormhole routing
- Authors
- Greenberg, RI; Oh, HC
- Issue Date
- 3월-1997
- Publisher
- IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
- Keywords
- wormhole routing; packet routing; randomized routing; greedy routing; area-universal networks; fat-tree interconnection network
- Citation
- IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, v.8, no.3, pp.254 - 262
- Indexed
- SCIE
SCOPUS
- Journal Title
- IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
- Volume
- 8
- Number
- 3
- Start Page
- 254
- End Page
- 262
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/126167
- DOI
- 10.1109/71.584091
- ISSN
- 1045-9219
- Abstract
- In this paper, we examine the wormhole routing problem in terms of the ''congestion'' c and ''dilation'' d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cd eta+cL eta log P) time with high probability, where L is the number of flits in a packet, and eta=min(d, L); only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area O(A) can simulate wormhole routing on any network of comparable area with O(log(3) A) slowdown, when all worms have the same length. Variable-length worms are also considered. We run some simulations on the fat-tree which show that not only does wormhole routing tend to perform better than the more heavily studied store-and-forward routing in this context, but that performance superior to our provable bound is attainable in practice.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - College of Science and Technology > Department of Electronics and Information Engineering > 1. Journal Articles
![qrcode](https://api.qrserver.com/v1/create-qr-code/?size=55x55&data=https://scholar.korea.ac.kr/handle/2021.sw.korea/126167)
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.