Sparse Semi-Oblivious Routing: Few Random Paths Suffice

DOI10.1145/3583668.3594585OpenAlexW4380880017MaRDI QIDQ6202250FDOQ6202250

Authors Goran Zuzic, Bernhard Haeupler 

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

oblivious routingpacket routingsemi-oblivious routing

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: The packet routing problem asks to select routing paths that minimize the maximum edge congestion for a set of packets specified by source-destination vertex pairs. We revisit a semi-oblivious approach to this problem: each source-destination pair is assigned a small set of predefined paths before the demand is revealed, while the sending rates along the paths can be optimally adapted to the demand. This approach has been considered in practice in network traffic engineering due to its superior robustness and performance as compared to both oblivious routing and traditional traffic engineering approaches. We show the existence of sparse semi-oblivious routings: only $O(logn)$ paths are selected between each pair of vertices. The routing is $(polylogn)$-competitive for all demands against the offline-optimal congestion objective. Even for the well-studied case of hypercubes, no such result was known: our deterministic and oblivious selection of $O(logn)$ paths is the first simple construction of a deterministic oblivious structure that near-optimally assigns source-destination pairs to few routes. Our results contrast the current solely-negative landscape of results for semi-oblivious routing. We give the sparsity-competitiveness trade-off for lower sparsities and nearly match it with a lower bound. Our construction is extremely simple: Sample the few paths from any competitive oblivious routing. Indeed, this natural construction was used in traffic engineering as an unproven heuristic. We give a satisfactory theoretical justification for their empirical effectiveness: the competitiveness of the construction improves exponentially with the number of paths. Finally, when combined with the recent hop-constrained oblivious routing, we also obtain sparse and competitive structures for the completion-time objective.

Cites work

• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• scientific article; zbMATH DE number 7525512 (Why is no real title available?)
• scientific article; zbMATH DE number 7651175 (Why is no real title available?)
• Computing cut-based hierarchical decompositions in almost linear time
• Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
• Efficient Schemes for Parallel Communication
• Efficient dispersal of information for security, load balancing, and fault tolerance
• Hop-constrained oblivious routing
• Negative association of random variables, with applications
• Oblivious Routing for the Lp-norm
• Oblivious network design
• On-line routing in all-optical networks
• Optimal Oblivious Path Selection on the Mesh
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Packet routing in fixed-connection networks: A survey
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Routing, merging, and sorting on parallel models of computation
• Semi-oblivious routing: lower bounds
• Survey on oblivious routing strategies
• The probabilistic method
• Tight bounds for oblivious routing in the hypercube

This page was built for publication: Sparse Semi-Oblivious Routing: Few Random Paths Suffice

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