Universal wormhole routing
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Greenberg, RI | - |
dc.contributor.author | Oh, HC | - |
dc.date.accessioned | 2021-09-09T18:35:19Z | - |
dc.date.available | 2021-09-09T18:35:19Z | - |
dc.date.created | 2021-06-18 | - |
dc.date.issued | 1997-03 | - |
dc.identifier.issn | 1045-9219 | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/126167 | - |
dc.description.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. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC | - |
dc.subject | INTERCONNECTION NETWORKS | - |
dc.subject | PARALLEL COMPUTATION | - |
dc.subject | COMPUTER | - |
dc.subject | MODEL | - |
dc.title | Universal wormhole routing | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Oh, HC | - |
dc.identifier.doi | 10.1109/71.584091 | - |
dc.identifier.scopusid | 2-s2.0-0031099512 | - |
dc.identifier.wosid | A1997WQ48000003 | - |
dc.identifier.bibliographicCitation | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, v.8, no.3, pp.254 - 262 | - |
dc.relation.isPartOf | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | - |
dc.citation.title | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | - |
dc.citation.volume | 8 | - |
dc.citation.number | 3 | - |
dc.citation.startPage | 254 | - |
dc.citation.endPage | 262 | - |
dc.type.rims | ART | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalResearchArea | Engineering | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Theory & Methods | - |
dc.relation.journalWebOfScienceCategory | Engineering, Electrical & Electronic | - |
dc.subject.keywordPlus | INTERCONNECTION NETWORKS | - |
dc.subject.keywordPlus | PARALLEL COMPUTATION | - |
dc.subject.keywordPlus | COMPUTER | - |
dc.subject.keywordPlus | MODEL | - |
dc.subject.keywordAuthor | wormhole routing | - |
dc.subject.keywordAuthor | packet routing | - |
dc.subject.keywordAuthor | randomized routing | - |
dc.subject.keywordAuthor | greedy routing | - |
dc.subject.keywordAuthor | area-universal networks | - |
dc.subject.keywordAuthor | fat-tree interconnection network | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
145 Anam-ro, Seongbuk-gu, Seoul, 02841, Korea+82-2-3290-2963
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.