Document Type
Article
Publication Date
3-1997
Publication Title
IEEE Transactions on Parallel and Distributed Systems
Volume
8
Issue
3
Pages
254--262
Publisher Name
IEEE Computer Society
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η+cLηlogP) time with high probability, where L is the number of flits in a packet, and η=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 Θ(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.
Recommended Citation
Ronald I. Greenberg and Hyeong-Cheol Oh. Universal wormhole routing. IEEE Trans. Parallel and Distributed Systems, 8(3):254--262, March 1997.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
Comments
© 1997 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
This is a revised version of the conference paper that can be found at http://ecommons.luc.edu/cs_facpubs/113 (along with presentation slides).