On the benefit of supporting virtual channels in wormhole routers

Richard J. Cole, Bruce M. Maggs, Ramesh K. Sitaraman

Research output: Contribution to conferencePaperpeer-review

Abstract

This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We show that in any network in which each physical channel can emulate up to Q virtual channels, it is possible to route any set of L-bit messages whose paths have congestion C and dilation D in (L+D)C(D log D)1/Q2O(log*(C/D)) bit steps. We also prove a nearly matching lower bound, i.e., for any values of C, D, Q, and L, where C, D≥Q+1 and L = (1+Ω(1))D, we show how to construct a network and a set of L-bit messages whose paths have congestion C and dilation D that require Ω(LCD1/Q) bit steps to route. These upper and lower bounds imply that increasing the queuing capacity Q of each physical channel can speed up a wormhole routing algorithm by a superlinear factor. The results can be translated to the scenario in which each physical channel can transmit B bits simultaneously, and can queue bits from B different messages. In this case, the bounds are (L+D)C(D log D)1/B2O(log* (C/D))/B and Ω(LCD1/B/B), respectively. We also present a simple randomized wormhole routing algorithm for the butterfly network. The algorithm routes a q-relation on the inputs and outputs of an n-input butterfly in O(LQ(q+log n)(log1/Q n) log log(qn)) bit-steps. We present a nearly-matching lower bound that holds for a broad class of algorithms.

Original languageEnglish (US)
Pages131-141
Number of pages11
DOIs
StatePublished - 1996
EventProceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures - Padua, Italy
Duration: Jun 24 1996Jun 26 1996

Other

OtherProceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures
CityPadua, Italy
Period6/24/966/26/96

ASJC Scopus subject areas

  • Software
  • Safety, Risk, Reliability and Quality

Fingerprint Dive into the research topics of 'On the benefit of supporting virtual channels in wormhole routers'. Together they form a unique fingerprint.

Cite this