Costly circuits, submodular schedules and approximate carathéodory theorems

Shaileshh Bojja Venkatakrishnan, Mohammad Alizadeh, Pramod Viswanath

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 towards a constructive version of Carathfieodory's Theorem for the Birkhof 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)
Title of host publicationSIGMETRICS/ Performance 2016 - Proceedings of the SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Science
PublisherAssociation for Computing Machinery, Inc
Pages75-88
Number of pages14
ISBN (Electronic)9781450342667
DOIs
StatePublished - Jun 14 2016
Event13th Joint International Conference on Measurement and Modeling of Computer Systems, ACM SIGMETRICS / IFIP Performance 2016 - Antibes Juan-les-Pins, France
Duration: Jun 14 2016Jun 18 2016

Publication series

NameSIGMETRICS/ Performance 2016 - Proceedings of the SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Science

Other

Other13th Joint International Conference on Measurement and Modeling of Computer Systems, ACM SIGMETRICS / IFIP Performance 2016
Country/TerritoryFrance
CityAntibes Juan-les-Pins
Period6/14/166/18/16

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Hardware and Architecture

Fingerprint

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

Cite this