Hop-constrained oblivious routing

DOI10.1145/3406325.3451098MaRDI QIDQ6065245zbMATH OpenOpenAlexFDO

Authors Mohsen Ghaffari, Bernhard Haeupler, Goran Zuzic

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.10446

zbMATH Keywords

congestiondilationHop constraintsHop-constrained oblivious routingoblivious routingpartial tree embeddings

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We prove the existence of an oblivious routing scheme that is $mathrmpoly(logn)$-competitive in terms of $(congestion+dilation)$, thus resolving a well-known question in oblivious routing. Concretely, consider an undirected network and a set of packets each with its own source and destination. The objective is to choose a path for each packet, from its source to its destination, so as to minimize $(congestion+dilation)$, defined as follows: The dilation is the maximum path hop-length, and the congestion is the maximum number of paths that include any single edge. The routing scheme obliviously and randomly selects a path for each packet independent of (the existence of) the other packets. Despite this obliviousness, the selected paths have $(congestion+dilation)$ within a $mathrmpoly(logn)$ factor of the best possible value. More precisely, for any integer hop-bound $h$, this oblivious routing scheme selects paths of length at most $hcdotmathrmpoly(logn)$ and is $mathrmpoly(logn)$-competitive in terms of $congestion$ in comparison to the best possible $congestion$ achievable via paths of length at most $h$ hops. These paths can be sampled in polynomial time. This result can be viewed as an analogue of the celebrated oblivious routing results of R"{a}cke [FOCS 2002, STOC 2008], which are $O(logn)$-competitive in terms of $congestion$, but are not competitive in terms of $dilation$.

Cited in

(6)

• Oblivious routing with limited buffer capacity
• Sparse Semi-Oblivious Routing: Few Random Paths Suffice
• Optimal electrical oblivious routing on expanders
• Electrical flows for polylogarithmic competitive oblivious routing
• Approximation algorithms for hop constrained and buy-at-bulk network design via hop constrained oblivious routing
• Graph decompositions and length-constrained expanders (invited talk)

This page was built for publication: Hop-constrained oblivious routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065245)