Costly circuits, submodular schedules and approximate Carathéodory Theorems

Shaileshh Bojja Venkatakrishnan (), Mohammad Alizadeh () and Pramod Viswanath ()
Additional contact information
Shaileshh Bojja Venkatakrishnan: University of Illinois Urbana-Champaign
Mohammad Alizadeh: Massachusetts Institute of Technology
Pramod Viswanath: University of Illinois Urbana-Champaign

Queueing Systems: Theory and Applications, 2018, vol. 88, issue 3, No 5, 347 pages

Abstract: 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.

Keywords: Data center networks; Bridges and switches; Circuit networks; Network flows; Submodular optimization; Approximation algorithms; 68W25; 68M12; 68M20 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-017-9546-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:88:y:2018:i:3:d:10.1007_s11134-017-9546-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-017-9546-x

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().