2026-07-23T22:19:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17228 2024-03-06T10:59:16Z ddc:004 open_access

Space-Stretch Tradeoff in Routing Revisited Zinovyev, Anatoliy Compact routing labeled network routing lower bounds 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anatoliy Zinovyev 2022 Is Part Of LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2022.37 urn:nbn:de:0030-drops-172281 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.37 eng https://creativecommons.org/licenses/by/4.0/legalcode