A practical algorithm for constructing oblivious routing schemes
M. Bienkowski, M. Korzeniowski, H. Räcke, in: Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA ’03, 2003.
Download
No fulltext has been uploaded.
Conference Paper
| Published
| English
Author
Bienkowski, Marcin;
Korzeniowski, Miroslaw;
Räcke, Harald
Abstract
In a (randomized) oblivious routing scheme the path chosen for a request <br>between a source $s$ and a target $t$ is independent from the current traffic <br>in the network. Hence, such a scheme consists of probability distributions<br>over $s-t$ paths for every source-target pair $s,t$ in the network.<br><br>In a recent result citeR02 it was shown that for any undirected network <br>there is an oblivious routing scheme that achieves a polylogarithmic<br>competitive ratio with respect to congestion. Subsequently, Azar et <br>al. citeACF+03 gave a polynomial time algorithm that for a given network <br>constructs the best oblivious routing scheme, i.e. the scheme that guarantees<br>the best possible competitive ratio. <br>Unfortunately, the latter result is based on the Ellipsoid algorithm; hence <br>it is unpractical for large networks. <br><br>In this paper we present a combinatorial algorithm for constructing an<br>oblivious routing scheme that guarantees a competitive ratio of $O(log^4n)$<br>for undirected networks. Furthermore, our approach yields a proof <br>for the existence of an oblivious routing scheme with competitive ratio<br>$O(log^3n)$, which is much simpler than the original proof from citeR02.
Publishing Year
Proceedings Title
Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '03
ISBN
LibreCat-ID
Cite this
Bienkowski M, Korzeniowski M, Räcke H. A practical algorithm for constructing oblivious routing schemes. In: Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA ’03. ; 2003. doi:10.1145/777412.777418
Bienkowski, M., Korzeniowski, M., & Räcke, H. (2003). A practical algorithm for constructing oblivious routing schemes. In Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA ’03. https://doi.org/10.1145/777412.777418
@inproceedings{Bienkowski_Korzeniowski_Räcke_2003, title={A practical algorithm for constructing oblivious routing schemes}, DOI={10.1145/777412.777418}, booktitle={Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA ’03}, author={Bienkowski, Marcin and Korzeniowski, Miroslaw and Räcke, Harald}, year={2003} }
Bienkowski, Marcin, Miroslaw Korzeniowski, and Harald Räcke. “A Practical Algorithm for Constructing Oblivious Routing Schemes.” In Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA ’03, 2003. https://doi.org/10.1145/777412.777418.
M. Bienkowski, M. Korzeniowski, and H. Räcke, “A practical algorithm for constructing oblivious routing schemes,” in Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA ’03, 2003.
Bienkowski, Marcin, et al. “A Practical Algorithm for Constructing Oblivious Routing Schemes.” Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA ’03, 2003, doi:10.1145/777412.777418.
Google Scholar
ISBN Search