Detailed Information

Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

Universal wormhole routing

Authors
Greenberg, RIOh, 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

Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher Oh, Hyeong Cheol photo

Oh, Hyeong Cheol
과학기술대학 (전자및정보공학과)
Read more

Altmetrics

Total Views & Downloads

BROWSE