Compact Oblivious Routing in Weighted Graphs

Abstract

The space-requirement for routing-tables is an important characteristic of routing schemes. For the cost-measure of minimizing the total network load there exist a variety of results that show tradeoffs between stretch and required size for the routing tables. This paper designs compact routing schemes for the cost-measure congestion, where the goal is to minimize the maximum relative load of a link in the network (the relative load of a link is its traffic divided by its bandwidth). We show that for arbitrary undirected graphs we can obtain oblivious routing strategies with competitive ratio $\tilde{\mathcal{O}}(1)$ that have header length $\tilde{\mathcal{O}}(1)$, label size $\tilde{\mathcal{O}}(1)$, and require routing-tables of size $\tilde{\mathcal{O}}(\mathrm{deg}(v))$ at each vertex $v$ in the graph. This improves a result of Räcke and Schmid who proved a similar result in unweighted graphs.

To be published in the Proceedings of the 28th European Symposium on Algorithms (ESA), 2020