Universal wormhole routing

Author

Greenberg, Ronald I. ; Oh, Hyeong-Cheol

Author_Institution

Dept. of Math. & Comput. Sci., Loyola Univ., Chicago, IL, USA

Volume

8

Issue

3

fYear

1997

fDate

3/1/1997 12:00:00 AM

Firstpage

254

Lastpage

262

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η+dη log P) 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³ 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

Keywords

computational complexity; multiprocessor interconnection networks; packet switching; randomised algorithms; trees (mathematics); virtual machines; congestion; dilation; fat tree network; flits; flow control digits; packet paths; packet routing; simple randomized algorithm; simulations; universal wormhole routing; variable length worms; wormhole routing problem; Algorithm design and analysis; Computer networks; Computer worms; Concurrent computing; Context modeling; Iterative algorithms; Large-scale systems; Multiprocessor interconnection networks; Performance analysis; Routing;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.584091

Filename

584091