On the cluster admission problem for cloud computing

Ludwig Dierks, Ian A. Kash, Sven SeukenNetEcon@SIGMETRICS 2019 · DOI

Introduction

Cloud computing providers operate at a massive scale, where even marginal improvements in hardware utilization translate into significant economic gains. A central challenge in this domain is the Cluster Admission Problem: determining whether to accept a new tenant's "deployment" (a set of virtual machines) without knowing its future resource demands. Because modern cloud workloads often "scale out"—requesting additional resources as demand grows—providers must balance high current utilization against the risk of failing to meet future scale-out requests, which would violate Service Level Agreements (SLAs).

The Limitations of Static Thresholds

The industry standard for cluster management relies on conservative threshold policies. For example, a provider might stop admitting new jobs once a cluster reaches 50% capacity, leaving the remaining half as a buffer for potential scale-out. While this ensures high reliability, it results in chronic underutilization and wasted capital expenditure.

The core issue is that utilization is a poor proxy for risk. A cluster that is 60% full with stable, predictable jobs may be safer than one that is 40% full with highly volatile, "bursty" workloads.

Methodology: A Probabilistic Approach

To address these inefficiencies, researchers formulated the admission challenge as a Constrained Partially Observable Markov Decision Process (POMDP). Given the computational complexity of solving a POMDP for thousands of cores, the authors developed three heuristic policies based on statistical moments:

  1. Zeroth Moment (Baseline): Admits jobs based on a fixed utilization threshold.
  2. First Moment (Expectation-Based): Utilizes Markov’s Inequality. It estimates the expected future resource usage of all active jobs and admits a new job only if the total expected usage remains below a safety limit.
  3. Second Moment (Variance-Aware): Utilizes Cantelli’s Inequality. This policy accounts for both the expected usage and the variance (risk) of workloads. It recognizes that high-variance jobs pose a greater threat to cluster stability than stable jobs with the same average footprint.

The Marginal Heuristic and Incentive Design

The researchers also introduced a Marginal Heuristic, allowing the admission of small or short-lived jobs even in "full" clusters, based on the probability that they will terminate before a capacity crunch occurs.

Furthermore, to improve the accuracy of the admission controller's "priors," the authors proposed a variance-based pricing mechanism. By charging a small fee tied to the reported variance of a job category, providers can incentivize users to accurately label their workloads (e.g., distinguishing between a stable web server and a volatile development environment).

Data and Simulation

The study's findings are grounded in real-world data from a one-month trace of Microsoft Azure internal job data. To overcome the limitations of a short trace, the authors fitted Gamma distributions to the data to create a generative model, enabling a three-year simulation of cluster dynamics.

Key Results and Economic Impact

The transition from rigid thresholds to probabilistic admission yielded substantial improvements:

  • Utilization Gains: While the baseline threshold policy achieved approximately 50% utilization, the First Moment policy increased this to 66%, and the Second Moment policy reached 67%.
  • Information Advantage: When the system had high-quality information about arriving jobs (simulating 50 prior observations of a job type), utilization reached as high as 83.8%.
  • Financial Implications: For a major cloud provider, a 30% relative increase in utilization (moving from 50% to 65%) represents hundreds of millions of dollars in annual savings by deferring the need for new physical infrastructure.

Conclusion

By moving away from "fill-to-X%" rules and toward policies that explicitly quantify tail risk through statistical inequalities, cloud providers can significantly boost efficiency without compromising reliability. Future research may look into non-stationary workloads and the complexities of multi-cluster migration to further refine these admission strategies.

Based on: Dierks, L., Kash, I. A., & Seuken, S. (2021). On the Cluster Admission Problem for Cloud Computing. Journal of Artificial Intelligence Research.

Summary updated

BibTeX
@inproceedings{dierks2019cluster,
  author = {Ludwig Dierks and Ian A. Kash and Sven Seuken},
  title = {{On the cluster admission problem for cloud computing}},
  booktitle = {NetEcon@SIGMETRICS},
  year = {2019},
  doi = {10.1145/3338506.3340274},
}
Figure