R.J. Cole, B.M. Maggs, and R.K. Sitaraman
Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures , June 1996, pp. 131-141. To appear, Journal of Computer and Systems Sciences.
d>This paper analyzes the effect of virtual channels on the performance of wormhole routing algorithms. We show that in a network in which each edge can emulate up to q virtual channels, it is possible to route any set of b-bit messages whose paths have congestion c and dilation d in (b+d) c (d log d)^(1/q) 2^O(log^* (c/d)) bit-steps. We also prove a nearly matching lower bound, i.e., for any values of c, d, q, and b, where c = d and b > d, we show how to construct a network and a set of b-bit messages whose paths have congestion c and dilation d that require Omega(bcd^(1/q)) bit-steps to route. These bounds imply that increasing the queuing capacity q of each edge can speed up a wormhole routing algorithm by a superlinear factor. We also present a simple randomized wormhole routing algorithm for the butterfly network. The algorithm routes a k-relation on the inputs and outputs of an N-input butterfly in O(bq(k+log N)(log^(1/q) N) log log Nk) bit-steps. We present a nearly matching lower bound that holds for a broad class of algorithms.
postscript of full paper