Optimal oblivious path selection on the mesh

Costas Busch, Malik Magdon-lsmail, Jing Xi

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


In the oblivious path selection problem, each packet in the network independently chooses a path, which is an important property if the routing algorithm is to be independent of the traffic distribution. The quality of the paths is determined by the congestion, C, the maximum number of paths crossing an edge, and the dilation, D, the maximum path length. So far, the oblivious algorithms studied in the literature have focused on minimizing the congestion while ignoring the dilation. An open problem is to give algorithms for networks in which C and D can be controlled simultaneously. Here, we solve this problem for the d-dimensional mesh. We present an oblivious algorithm for which C and D are both within O(d2) of the optimal. The algorithm uses randomization and we show that the number of random bits required per packet is within O(d) of the minimum number of random bits required by any algorithm that obtains the same congestion. For a fixed d, our algorithm is asymptotically optimal.

Original languageEnglish (US)
Pages (from-to)660-671
Number of pages12
JournalIEEE Transactions on Computers
Issue number5
StatePublished - 2008
Externally publishedYes


  • Algorithm randomization
  • Mesh topology
  • Network congestion
  • Oblivious routing
  • Path stretch

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Optimal oblivious path selection on the mesh'. Together they form a unique fingerprint.

Cite this