Sparse Semi-Oblivious Routing: Few Random Paths Suffice

DOI10.1145/3583668.3594585arXiv2301.06647OpenAlexW4380880017MaRDI 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)

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.

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)

Cites Work

• Negative association of random variables, with applications
• The probabilistic method
• Routing, merging, and sorting on parallel models of computation
• Efficient dispersal of information for security, load balancing, and fault tolerance
• Title not available (Why is that?)
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Title not available (Why is that?)
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Oblivious network design
• Packet routing in fixed-connection networks: A survey
• Efficient Schemes for Parallel Communication
• Tight bounds for oblivious routing in the hypercube
• On-line routing in all-optical networks
• Survey on oblivious routing strategies
• Oblivious Routing for the Lp-norm
• Title not available (Why is that?)
• Hop-constrained oblivious routing
• Title not available (Why is that?)
• Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
• Optimal Oblivious Path Selection on the Mesh
• Computing Cut-Based Hierarchical Decompositions in Almost Linear Time
• Title not available (Why is that?)

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)