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

Fingerprint

Bandwidth
Optical switches
Networks (circuits)
Scheduling algorithms
Resource allocation
Servers
Scheduling
Switches
Costs
Schedule
Reconfiguration
Routing
Trade-offs
Data center
Connectivity
Load balancing

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

Cite this

Costly circuits, submodular schedules and approximate Carathéodory Theorems. / Bojja Venkatakrishnan, Shaileshh; Alizadeh, Mohammad; Viswanath, Pramod.

In: Queueing Systems, Vol. 88, No. 3-4, 01.04.2018, p. 311-347.

Research output: Contribution to journalArticle

Bojja Venkatakrishnan, Shaileshh ; Alizadeh, Mohammad ; Viswanath, Pramod. / Costly circuits, submodular schedules and approximate Carathéodory Theorems. In: Queueing Systems. 2018 ; Vol. 88, No. 3-4. pp. 311-347.
@article{c4487e24447a47f68a5cca3344244362,
title = "Costly circuits, submodular schedules and approximate Carath{\'e}odory Theorems",
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{\'e}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 = "Approximation algorithms, Bridges and switches, Circuit networks, Data center networks, Network flows, Submodular optimization",
author = "{Bojja Venkatakrishnan}, Shaileshh and Mohammad Alizadeh and Pramod Viswanath",
year = "2018",
month = "4",
day = "1",
doi = "10.1007/s11134-017-9546-x",
language = "English (US)",
volume = "88",
pages = "311--347",
journal = "Queueing Systems",
issn = "0257-0130",
publisher = "Springer Netherlands",
number = "3-4",

}

TY - JOUR

T1 - Costly circuits, submodular schedules and approximate Carathéodory Theorems

AU - Bojja Venkatakrishnan, Shaileshh

AU - Alizadeh, Mohammad

AU - Viswanath, Pramod

PY - 2018/4/1

Y1 - 2018/4/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Bridges and switches

KW - Circuit networks

KW - Data center networks

KW - Network flows

KW - Submodular optimization

UR - http://www.scopus.com/inward/record.url?scp=85029694487&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029694487&partnerID=8YFLogxK

U2 - 10.1007/s11134-017-9546-x

DO - 10.1007/s11134-017-9546-x

M3 - Article

AN - SCOPUS:85029694487

VL - 88

SP - 311

EP - 347

JO - Queueing Systems

JF - Queueing Systems

SN - 0257-0130

IS - 3-4

ER -