Costly circuits, submodular schedules and approximate Carathéodory Theorems

Shaileshh Bojja Venkatakrishnan, Mohammad Alizadeh, Pramod Viswanath

Research output: Contribution to journalArticle

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 reconfiguration costs with the benefits of reconfiguration that match the traffic demands. Seen alternatively, the algorithm provides a fast and approximate solution toward a constructive version of Carathéodory’s Theorem for the Birkhoff polytope. The algorithm also has strong connections to submodular optimization, achieves a performance at least half that of the optimal schedule and strictly outperforms the 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.

Original languageEnglish (US)
Pages (from-to)311-347
Number of pages37
JournalQueueing Systems
Volume88
Issue number3-4
DOIs
StatePublished - Apr 1 2018

Keywords

  • Approximation algorithms
  • Bridges and switches
  • Circuit networks
  • Data center networks
  • Network flows
  • Submodular optimization

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Management Science and Operations Research
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Costly circuits, submodular schedules and approximate Carathéodory Theorems'. Together they form a unique fingerprint.

  • Cite this