Hop-Constrained Oblivious Routing
Mohsen Ghaffari, Bernhard Haeupler, Goran Žužić · SIAM Journal on Computing · 2023
Abstract. We prove the existence of an oblivious routing scheme that is [Formula: see text]-competitive in terms of [Formula: see text], 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 [Formula: see text], 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 [Formula: see text] within a [Formula: see text] factor of the best possible value. More precisely, for any integer hop constraint [Formula: see text], this oblivious routing scheme selects paths of length at most [Formula: see text] and is [Formula: see text]-competitive in terms of congestion in comparison to the best possible congestion achievable via paths of length at most [Formula: see text] 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äcke [ Proceedings of the 43 rd Annual IEEE Symposium on Foundations of Computer Science, 2002; Proceedings of the 40 th Annual ACM Symposium on Theory of Computing, 2008], which are [Formula: see text]-competitive in terms of congestion but are not competitive in terms of dilation.