--- _id: '18907' abstract: - lang: eng text: In a (randomized) oblivious routing scheme the path chosen for a request
between a source $s$ and a target $t$ is independent from the current traffic
in the network. Hence, such a scheme consists of probability distributions
over $s-t$ paths for every source-target pair $s,t$ in the network.

In a recent result citeR02 it was shown that for any undirected network
there is an oblivious routing scheme that achieves a polylogarithmic
competitive ratio with respect to congestion. Subsequently, Azar et
al. citeACF+03 gave a polynomial time algorithm that for a given network
constructs the best oblivious routing scheme, i.e. the scheme that guarantees
the best possible competitive ratio.
Unfortunately, the latter result is based on the Ellipsoid algorithm; hence
it is unpractical for large networks.

In this paper we present a combinatorial algorithm for constructing an
oblivious routing scheme that guarantees a competitive ratio of $O(log^4n)$
for undirected networks. Furthermore, our approach yields a proof
for the existence of an oblivious routing scheme with competitive ratio
$O(log^3n)$, which is much simpler than the original proof from citeR02. author: - first_name: Marcin full_name: Bienkowski, Marcin last_name: Bienkowski - first_name: Miroslaw full_name: Korzeniowski, Miroslaw last_name: Korzeniowski - first_name: Harald full_name: Räcke, Harald last_name: Räcke citation: ama: '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' apa: 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 bibtex: '@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} }' chicago: 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. ieee: 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. mla: 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. short: 'M. Bienkowski, M. Korzeniowski, H. Räcke, in: Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures  - SPAA ’03, 2003.' date_created: 2020-09-03T07:44:01Z date_updated: 2022-01-06T06:53:54Z department: - _id: '63' doi: 10.1145/777412.777418 language: - iso: eng publication: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '03 publication_identifier: isbn: - '1581136617' publication_status: published status: public title: A practical algorithm for constructing oblivious routing schemes type: conference user_id: '15415' year: '2003' ... --- _id: '18960' abstract: - lang: eng text: We investigate distributed algorithms for mobile ad hoc networks for moving radio stations with adjustable transmission power in a worst case scenario. We consider two models to find a reasonable restriction on the worst-case mobility. In the pedestrian model we assume a maximum speed $v_max$ of the radio stations, while in the vehicular model we assume a maximum acceleration $a_max$ of the points. Our goal is to maintain persistent routes with nice communication network properties like hop-distance, energy-consumption, congestion and number of interferences. A route is persistent, if we can guarantee that all edges of this route can be uphold for a given time span $Delta$, which is a parameter denoting the minimum time the mobile network needs to adopt changes, i.e. update routing tables, change directory entries, etc. This $Delta$ can be used as the length of an update interval for a proactive routing scheme. We extend some known notions such as transmission range, interferences, spanner, power spanner and congestion to both mobility models and introduce a new parameter called crowdedness that states a lower bound on the number of radio interferences. Then we prove that a mobile spanner hosts a path system that polylogarithmically approximates the optimal congestion. We present distributed algorithms based on a grid clustering technique and a high-dimensional representation of the dynamical start situation which construct mobile spanners with low congestion, low interference number, low energy-consumption, and low degree. We measure the optimality of the output of our algorithm by comparing it with the optimal choice of persistent routes under the same circumstances with respect to pedestrian or vehicular worst-case movements. Finally, we present solutions for dynamic position information management under our mobility models. author: - first_name: Christian full_name: Schindelhauer, Christian last_name: Schindelhauer - first_name: Tamás full_name: Lukovszki, Tamás last_name: Lukovszki - first_name: Stefan full_name: Rührup, Stefan last_name: Rührup - first_name: Klaus full_name: Volbert, Klaus last_name: Volbert citation: ama: 'Schindelhauer C, Lukovszki T, Rührup S, Volbert K. Worst case mobility in ad hoc networks. In: Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03). ; 2003. doi:10.1145/777412.777448' apa: Schindelhauer, C., Lukovszki, T., Rührup, S., & Volbert, K. (2003). Worst case mobility in ad hoc networks. In Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03). https://doi.org/10.1145/777412.777448 bibtex: '@inproceedings{Schindelhauer_Lukovszki_Rührup_Volbert_2003, title={Worst case mobility in ad hoc networks}, DOI={10.1145/777412.777448}, booktitle={Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03)}, author={Schindelhauer, Christian and Lukovszki, Tamás and Rührup, Stefan and Volbert, Klaus}, year={2003} }' chicago: Schindelhauer, Christian, Tamás Lukovszki, Stefan Rührup, and Klaus Volbert. “Worst Case Mobility in Ad Hoc Networks.” In Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03), 2003. https://doi.org/10.1145/777412.777448. ieee: C. Schindelhauer, T. Lukovszki, S. Rührup, and K. Volbert, “Worst case mobility in ad hoc networks,” in Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03), 2003. mla: Schindelhauer, Christian, et al. “Worst Case Mobility in Ad Hoc Networks.” Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03), 2003, doi:10.1145/777412.777448. short: 'C. Schindelhauer, T. Lukovszki, S. Rührup, K. Volbert, in: Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03), 2003.' date_created: 2020-09-03T13:10:50Z date_updated: 2022-01-06T06:53:55Z department: - _id: '63' doi: 10.1145/777412.777448 language: - iso: eng publication: Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03) publication_identifier: isbn: - '1581136617' publication_status: published status: public title: Worst case mobility in ad hoc networks type: conference user_id: '15415' year: '2003' ... --- _id: '16484' citation: ama: Rosenberg AL, Meyer auf der Heide F, eds. Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures  - SPAA ’03.; 2003. doi:10.1145/777412 apa: Rosenberg, A. L., & Meyer auf der Heide, F. (Eds.). (2003). Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures  - SPAA ’03. https://doi.org/10.1145/777412 bibtex: '@book{Rosenberg_Meyer auf der Heide_2003, title={Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures  - SPAA ’03}, DOI={10.1145/777412}, year={2003} }' chicago: Rosenberg, Arnold L., and Friedhelm Meyer auf der Heide, eds. Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures  - SPAA ’03, 2003. https://doi.org/10.1145/777412. ieee: A. L. Rosenberg and F. Meyer auf der Heide, Eds., Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures  - SPAA ’03. 2003. mla: Rosenberg, Arnold L., and Friedhelm Meyer auf der Heide, editors. Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures  - SPAA ’03. 2003, doi:10.1145/777412. short: A.L. Rosenberg, F. Meyer auf der Heide, eds., Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures  - SPAA ’03, 2003. date_created: 2020-04-09T07:41:53Z date_updated: 2022-01-06T06:52:50Z department: - _id: '63' doi: 10.1145/777412 editor: - first_name: Arnold L. full_name: Rosenberg, Arnold L. last_name: Rosenberg - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide language: - iso: eng publication_identifier: isbn: - '1581136617' publication_status: published status: public title: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '03 type: conference_editor user_id: '15415' year: '2003' ...