Costly circuits, submodular schedules and approximate Carathéodory theorems

DOI10.1007/S11134-017-9546-XMaRDI QIDQ1649974zbMATH OpenOpenAlexFDO

Authors Shaileshh Venkatakrishnan, Mohammad Alizadeh, P. Viswanath

Publication date 29 June 2018

Published in Queueing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.01271, http://hdl.handle.net/1721.1/116926

zbMATH Keywords

approximation algorithmsbridges and switchescircuit networksdata center networksnetwork flowssubmodular optimization

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Abstract: Hybrid switching - in which a high bandwidth circuit switch (optical or wireless) is used in conjunction with a low bandwidth packet switch - is a promising alternative to interconnect servers in today's large scale data-centers. Circuit switches offer a very high link rate, but incur a non-trivial reconfiguration delay which makes their scheduling challenging. In this paper, we demonstrate a lightweight, simple and nearly-optimal scheduling algorithm that trades-off configuration costs with the benefits of reconfiguration that match the traffic demands. The algorithm has strong connections to submodular optimization, has performance at least half that of the optimal schedule and strictly outperforms state of the art in a variety of traffic demand settings. These ideas naturally generalize: we see that indirect routing leads to exponential connectivity; this is another phenomenon of the power of multi hop routing, distinct from the well-known load balancing effects.

Recommendations

• Data Center Scheduling, Generalized Flows, and Submodularity
• scientific article; zbMATH DE number 1775423
• Dynamic scheduling with reconfiguration delays
• Scheduled Hot-Potato Routing
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps

Cites work

• A Network-Based Primal-Dual Heuristic for the Solution of Multicommodity Network Flow Problems
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• Approximating fractional multicommodity flow independent of the number of commodities
• Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
• Birkhoff-von Neumann input-buffered crossbar switches for guaranteed-rate services
• Capacity and flow assignment of data networks by generalized Benders decomposition
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Communication networks. An optimization, control and stochastic networks perspective
• Efficient dispersal of information for security, load balancing, and fault tolerance
• Efficient Submodular Function Maximization under Linear Packing Constraints
• Expander graphs and their applications
• Fast approximation algorithms for multicommodity flow problems
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• Geometric algorithms and combinatorial optimization.
• Linear-time approximation for maximum weight matching
• Minimum cost capacity installation for multicommodity network flows
• Network flows. Theory, algorithms, and applications.
• On the speedup required for combined input- and output-queued switching
• The ellipsoid method and its consequences in combinatorial optimization
• The multiplicative weights update method: a meta-algorithm and applications

Cited in

(1)

• Heavy traffic queue length scaling in switches with reconfiguration delay

This page was built for publication: Costly circuits, submodular schedules and approximate Carathéodory theorems

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