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.2020.36
URN: urn:nbn:de:0030-drops-129024
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12902/
Go to the corresponding LIPIcs Volume Portal

Czerner, Philipp ; Räcke, Harald

Compact Oblivious Routing in Weighted Graphs

pdf-format:
LIPIcs-ESA-2020-36.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{czerner_et_al:LIPIcs:2020:12902,
  author =	{Philipp Czerner and Harald R{\"a}cke},
  title =	{{Compact Oblivious Routing in Weighted Graphs}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{36:1--36:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12902},
  URN =		{urn:nbn:de:0030-drops-129024},
  doi =		{10.4230/LIPIcs.ESA.2020.36},
  annote =	{Keywords: Oblivious Routing, Compact Routing, Competitive Analysis}
}

Keywords: Oblivious Routing, Compact Routing, Competitive Analysis
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

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