Compact oblivious routing

Harald Räcke, Stefan Schmid

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

5 Zitate (Scopus)

Abstract

Oblivious routing is an attractive paradigm for large distributed systems in which centralized control and frequent reconfigurations are infeasible or undesired (e.g., costly). Over the last almost 20 years, much progress has been made in devising oblivious routing schemes that guarantee close to optimal load and also algorithms for constructing such schemes efficiently have been designed. However, a common drawback of existing oblivious routing schemes is that they are not compact: they require large routing tables (of polynomial size), which does not scale. This paper presents the first oblivious routing scheme which guarantees close to optimal load and is compact at the same time – requiring routing tables of polylogarithmic size. Our algorithm maintains the polylogarithmic competitive ratio of existing algorithms, and is hence particularly well-suited for emerging large-scale networks.

OriginalspracheEnglisch
Titel27th Annual European Symposium on Algorithms, ESA 2019
Redakteure/-innenMichael A. Bender, Ola Svensson, Grzegorz Herman
Herausgeber (Verlag)Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elektronisch)9783959771245
DOIs
PublikationsstatusVeröffentlicht - Sept. 2019
Veranstaltung27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Deutschland
Dauer: 9 Sept. 201911 Sept. 2019

Publikationsreihe

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

Konferenz

Konferenz27th Annual European Symposium on Algorithms, ESA 2019
Land/GebietDeutschland
OrtMunich/Garching
Zeitraum9/09/1911/09/19

Fingerprint

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

Dieses zitieren