|
||||||||||||||||
|
Ph.D. ThesesStretch Preserving Oblivious Routing Algorithms
By Jing Xi
We study oblivious routing in which the packet paths are constructed independently of each other. 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 question is whether C and D can be controlled simultaneously. For general networks this is not possible. However, it is possible to obtain near optimal congestion while maintaining small stretch for special networks. We give oblivious routing algorithms for the d-dimensional mesh and geometric networks with small stretch without sacrificing on congestion. For concave geometric networks, in order to route any packet within a subgraph of diameter in the same order of the length of its shortest path, we decompose the network into clusters. We show that routing inside our clusters is within a log^4n factor from the optimal offline performance with respect to congestion. We also show that randomization is essential for obtaining low congestion for oblivious algorithms.
|
||||||||||||||||
Research
