Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 660-671 |
Number of pages | 12 |
Journal | IEEE Transactions on Computers |
Volume | 57 |
Issue number | 5 |
DOIs | |
State | Published - 2008 |
Externally published | Yes |
Keywords
- 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