New Bounds for Oblivious Mesh Routing

Authors

  • Kazuo Iwama
  • Yahiko Kambayashi
  • Eiji Miyano

DOI:

https://doi.org/10.7155/jgaa.00038

Abstract

We give two, new upper bounds for oblivious permutation routing on the mesh networks: Let N be the total number of processors in each mesh. One is an $O( N^{0.75})$ algorithm on the two-dimensional, $\sqrt{N} \times \sqrt{N}$ mesh with constant queue-size. This is the first algorithm which improves substantially the trivial $O(N)$ bound for oblivious routing in the mesh networks with constant queue-size. The other is a $1.16 \sqrt{N} + o(\sqrt{N})$ algorithm on the three-dimensional, $N^{1/3} \times N^{1/3} \times N^{1/3}$ mesh with unlimited queue-size. This algorithm allows at most three bends in the path of each packet. If the number of bends is restricted to minimal, i.e., at most two, then the bound jumps to $\Omega( N^{2/3})$ as was shown in ESA'97.

Downloads

Download data is not yet available.

Downloads

Published

2001-01-01

How to Cite

Iwama, K., Kambayashi, Y., & Miyano, E. (2001). New Bounds for Oblivious Mesh Routing. Journal of Graph Algorithms and Applications, 5(5), 17–38. https://doi.org/10.7155/jgaa.00038