"Universal Wormhole Routing" by Ronald I. Greenberg and Hyeong-Cheol Oh
 

Document Type

Conference Proceeding

Publication Date

12-1993

Publication Title

Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing

Pages

56-63

Abstract

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ηlog P) time, 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, but that performance superior to our provable bound is attainable in practice

Identifier

0-8186-4222-X

Comments

Author Posting. © IEEE, 1993. This is the author's IEEE for personal use, not for redistribution. The definitive version was published in Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing, pages 56-63, http://dx.doi.org/10.1109/SPDP.1993.395550.

A revised version can be found at http://ecommons.luc.edu/cs_facpubs/162

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.

GreenbergO1993U_slides.pdf (8062 kB)
Presentation slides from Fifth IEEE Symposium on Parallel and Distributed Processing

Plum Print visual indicator of research metrics
PlumX Metrics
  • Citations
    • Citation Indexes: 2
  • Usage
    • Downloads: 188
    • Abstract Views: 12
  • Captures
    • Readers: 3
see details

Share

COinS