License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2022.37
URN: urn:nbn:de:0030-drops-172281
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17228/
Go to the corresponding LIPIcs Volume Portal

Zinovyev, Anatoliy

Space-Stretch Tradeoff in Routing Revisited

pdf-format:
LIPIcs-DISC-2022-37.pdf (0.6 MB)

Abstract

We present several new proofs of lower bounds for the space-stretch tradeoff in labeled network routing.
First, we give a new proof of an important result of Cyril Gavoille and Marc Gengler that any routing scheme with stretch < 3 must use Ω(n) bits of space at some node on some network with n vertices, even if port numbers can be changed. Compared to the original proof, our proof is significantly shorter and, we believe, conceptually and technically simpler. A small extension of the proof can show that, in fact, any constant fraction of the n nodes must use Ω(n) bits of space on some graph.
Our main contribution is a new result that if port numbers are chosen adversarially, then stretch < 2k+1 implies some node must use Ω(n^(1/k) log n) bits of space on some graph, assuming a girth conjecture by Erdős.
We conclude by showing that all known methods of proving a space lower bound in the labeled setting, in fact, require the girth conjecture.

BibTeX - Entry

@InProceedings{zinovyev:LIPIcs.DISC.2022.37,
  author =	{Zinovyev, Anatoliy},
  title =	{{Space-Stretch Tradeoff in Routing Revisited}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17228},
  URN =		{urn:nbn:de:0030-drops-172281},
  doi =		{10.4230/LIPIcs.DISC.2022.37},
  annote =	{Keywords: Compact routing, labeled network routing, lower bounds}
}

Keywords: Compact routing, labeled network routing, lower bounds
Collection: 36th International Symposium on Distributed Computing (DISC 2022)
Issue Date: 2022
Date of publication: 17.10.2022

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