Costly Circuits, Submodular Schedules and Approximate Carathéodory Theorems

Shaileshh Bojja Venkatakrishnan, Mohammad Alizadeh, Pramod Viswanath

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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 towards a constructive version of Caratheodory'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 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)75-88
Number of pages14
JournalPerformance Evaluation Review
Issue number1
StatePublished - Jun 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


  • caratheodory theorem
  • circuit switch
  • datacenters
  • hybrid networks
  • packet switch


Dive into the research topics of 'Costly Circuits, Submodular Schedules and Approximate Carathéodory Theorems'. Together they form a unique fingerprint.

Cite this