On Multidimensional Packet Routing for Meshes with Buses

J. Y.T. Leung, S. M. Shende

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Routing problems on the r-dimensional n × n × · · · × n mesh architecture, enhanced with independent buses along each dimension, are investigated. We analyze several different kinds of routing problems, among them off-line routing, and provide routing algorithms for the one-dimensional, two-dimensional, and r-dimensional meshes. Asymptotically, we show that, queuesize being equal, the bus-equipped mesh architecture outperforms the classical mesh by speeding up the routing time by a factor of 12 7.

Original languageEnglish (US)
Pages (from-to)187-197
Number of pages11
JournalJournal of Parallel and Distributed Computing
Issue number2
StatePublished - Feb 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'On Multidimensional Packet Routing for Meshes with Buses'. Together they form a unique fingerprint.

Cite this