Compact oblivious routing in weighted graphs

Philipp Czerner, Harald Räcke

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

1 Zitat (Scopus)

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 Õ(1) that have header length Õ(1), label size Õ(1), and require routing-tables of size Õ(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.

OriginalspracheEnglisch
Titel28th Annual European Symposium on Algorithms, ESA 2020
Redakteure/-innenFabrizio Grandoni, Grzegorz Herman, Peter Sanders
Herausgeber (Verlag)Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elektronisch)9783959771627
DOIs
PublikationsstatusVeröffentlicht - 1 Aug. 2020
Veranstaltung28th Annual European Symposium on Algorithms, ESA 2020 - Virtual, Pisa, Italien
Dauer: 7 Sept. 20209 Sept. 2020

Publikationsreihe

NameLeibniz International Proceedings in Informatics, LIPIcs
Band173
ISSN (Print)1868-8969

Konferenz

Konferenz28th Annual European Symposium on Algorithms, ESA 2020
Land/GebietItalien
OrtVirtual, Pisa
Zeitraum7/09/209/09/20

Fingerprint

Untersuchen Sie die Forschungsthemen von „Compact oblivious routing in weighted graphs“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren