Skip to main content
Journal cover image

On the benefit of supporting virtual channels in wormhole routers

Publication ,  Journal Article
Cole, RJ; Maggs, BM; Sitaraman, RK
Published in: Journal of Computer and System Sciences
January 1, 2001

This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We study wormhole routing on network in which each physical channel, i.e., communication link, can support up to B virtual channels. We show that it is possible to route any set of messages with L flits each, whose paths have congestion C and dilation D in O((L+ D) C(D log D)1/B/B) flit steps, where a flit step is the time taken to transmit B flits, i.e., one flit per virtual channel, across a physical channel. We also prove a nearly matching lower bound; i.e., for any values of C, D, B, and L, where C, D≥B+1 and L=(1+Ω(1))D, we show how to construct a network and a set of L-flit messages whose paths have congestion C and dilation D that require Ω(LCD1/B/B) flit steps to route. These upper and lower bounds imply that increasing the buffering capacity and the bandwidth of each physical channel by a factor of B can speed up a wormhole routing algorithm by a superlinear factor, i.e., a factor significantly larger than B. We also present a simple randomized wormhole routing algorithm for the butterfly network. The algorithm routes any q-relation on the inputs and outputs of an n-input butterfly in O(L(q + log n) log1/B n log log(qn)/B) flit steps. We present a nearly-matching lower bound that holds for a broad class of algorithms. © 2001 Academic Press.

Duke Scholars

Published In

Journal of Computer and System Sciences

DOI

ISSN

0022-0000

Publication Date

January 1, 2001

Volume

62

Issue

1

Start / End Page

152 / 177

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 0806 Information Systems
  • 0805 Distributed Computing
  • 0802 Computation Theory and Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Cole, R. J., Maggs, B. M., & Sitaraman, R. K. (2001). On the benefit of supporting virtual channels in wormhole routers. Journal of Computer and System Sciences, 62(1), 152–177. https://doi.org/10.1006/jcss.2000.1701
Cole, R. J., B. M. Maggs, and R. K. Sitaraman. “On the benefit of supporting virtual channels in wormhole routers.” Journal of Computer and System Sciences 62, no. 1 (January 1, 2001): 152–77. https://doi.org/10.1006/jcss.2000.1701.
Cole RJ, Maggs BM, Sitaraman RK. On the benefit of supporting virtual channels in wormhole routers. Journal of Computer and System Sciences. 2001 Jan 1;62(1):152–77.
Cole, R. J., et al. “On the benefit of supporting virtual channels in wormhole routers.” Journal of Computer and System Sciences, vol. 62, no. 1, Jan. 2001, pp. 152–77. Scopus, doi:10.1006/jcss.2000.1701.
Cole RJ, Maggs BM, Sitaraman RK. On the benefit of supporting virtual channels in wormhole routers. Journal of Computer and System Sciences. 2001 Jan 1;62(1):152–177.
Journal cover image

Published In

Journal of Computer and System Sciences

DOI

ISSN

0022-0000

Publication Date

January 1, 2001

Volume

62

Issue

1

Start / End Page

152 / 177

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 0806 Information Systems
  • 0805 Distributed Computing
  • 0802 Computation Theory and Mathematics