UNIVERSAL WORMHOLE ROUTING

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 sho w, 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 w ith O(log(3) A) slowdown, when all worms have the same length. Variabl e-length worms are also considered. We run some simulations on the fat -tree which show that not only does wormhole routing tend to perform b etter than the more heavily studied store-and-forward routing in this context, but that performance superior to our provable bound is attain able in practice.