- On the benefit of supporting virtual
channels in wormhole routers. R. J. Cole, B. M. Maggs, and R.
K. Sitaraman. Proceedings of the 8th ACM Symposium on
Parallel Algorithms and Architectures (SPAA), June 1996, pp. 131-141.
- 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.
- Back to other
- Back to my home page