@inproceedings{18907, abstract = {{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 = {{Bienkowski, Marcin and Korzeniowski, Miroslaw and Räcke, Harald}}, booktitle = {{Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '03}}, isbn = {{1581136617}}, title = {{{A practical algorithm for constructing oblivious routing schemes}}}, doi = {{10.1145/777412.777418}}, year = {{2003}}, } @inproceedings{18960, abstract = {{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 = {{Schindelhauer, Christian and Lukovszki, Tamás and Rührup, Stefan and Volbert, Klaus}}, booktitle = {{Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03)}}, isbn = {{1581136617}}, title = {{{Worst case mobility in ad hoc networks}}}, doi = {{10.1145/777412.777448}}, year = {{2003}}, } @proceedings{16484, editor = {{Rosenberg, Arnold L. and Meyer auf der Heide, Friedhelm}}, isbn = {{1581136617}}, title = {{{Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '03}}}, doi = {{10.1145/777412}}, year = {{2003}}, }