Overcommitment in Cloud Services: Bin Packing with Chance Constraints

Maxime C. Cohen (), Philipp W. Keller (), Vahab Mirrokni () and Morteza Zadimoghaddam ()
Additional contact information
Maxime C. Cohen: NYU Stern School of Business, New York, New York 10012
Philipp W. Keller: Facebook, Menlo Park, California 94043
Vahab Mirrokni: Google Research, New York, New York 10011
Morteza Zadimoghaddam: Google Research, New York, New York 10011

Management Science, 2019, vol. 65, issue 7, 3255-3271

Abstract: This paper considers a traditional problem of resource allocation: scheduling jobs on machines. One such recent application is cloud computing; jobs arrive in an online fashion with capacity requirements and need to be immediately scheduled on physical machines in data centers. It is often observed that the requested capacities are not fully utilized, hence offering an opportunity to employ an overcommitment policy , that is, selling resources beyond capacity. Setting the right overcommitment level can yield a significant cost reduction for the cloud provider while only inducing a very low risk of violating capacity constraints. We introduce and study a model that quantifies the value of overcommitment by modeling the problem as bin packing with chance constraints. We then propose an alternative formulation that transforms each chance constraint to a submodular function. We show that our model captures the risk pooling effect and can guide scheduling and overcommitment decisions. We also develop a family of online algorithms that are intuitive, easy to implement, and provide a constant factor guarantee from optimal. Finally, we calibrate our model using realistic workload data and test our approach in a practical setting. Our analysis and experiments illustrate the benefit of overcommitment in cloud services and suggest a cost reduction of 1.5% to 17%, depending on the provider’s risk tolerance.

Keywords: bin packing; approximation algorithms; cloud computing; overcommitment (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
https://doi.org/10.1287/mnsc.2018.3091 (application/pdf)

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:inm:ormnsc:v:65:y:2019:i:7:p:3255-3271

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().