• 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.

  Postscript Compressed Postscript
  Back to other publications

  Back to my home page