License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.75
URN: urn:nbn:de:0030-drops-111968
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11196/
Go to the corresponding LIPIcs Volume Portal

Räcke, Harald ; Schmid, Stefan

Compact Oblivious Routing

pdf-format:
LIPIcs-ESA-2019-75.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{rcke_et_al:LIPIcs:2019:11196,
  author =	{Harald R{\"a}cke and Stefan Schmid},
  title =	{{Compact Oblivious Routing}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{75:1--75:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11196},
  URN =		{urn:nbn:de:0030-drops-111968},
  doi =		{10.4230/LIPIcs.ESA.2019.75},
  annote =	{Keywords: Oblivious Routing, Compact Routing, Competitive Analysis}
}

Keywords: Oblivious Routing, Compact Routing, Competitive Analysis
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI