Heavy traffic optimal resource allocation algorithms for cloud computing clusters

Siva Theja Maguluri, R. Srikant, Lei Ying

Published in 2012, this research provides a rigorous mathematical foundation for why certain popular resource allocation strategies in cloud computing are theoretically "perfect" when a system is pushed to its limits. By analyzing the "heavy traffic" regime—where demand nearly matches the system's maximum capacity—the authors demonstrate that specific routing and scheduling combinations achieve optimal performance, effectively minimizing job backlogs and user-perceived delays.

The Challenge: Routing and Scheduling

Cloud computing clusters face a complex, two-part resource allocation challenge:

  1. Routing: Deciding which physical server should receive an incoming Virtual Machine (VM) request.
  2. Scheduling: Deciding which queued jobs to execute on a server, given that different jobs have varying requirements for CPU, RAM, and storage.

While many existing algorithms are "throughput optimal"—meaning they can eventually process any load the hardware is physically capable of handling—throughput alone does not guarantee low latency. In high-pressure scenarios where the arrival rate of jobs is very close to the system's maximum capacity, the goal shifts to minimizing the total number of jobs waiting in line (the queue length). Minimizing queue length is a direct proxy for reducing user-perceived delay.

Methodology: The Lyapunov Drift Framework

The paper employs a stochastic model of a cloud cluster and introduces a sophisticated three-step Lyapunov drift framework to prove optimality in the steady-state. Unlike previous proofs that relied on complex Brownian motion limits (often restricted to finite time intervals), this method proves optimality for the long-term operations of the system.

1. Establishing the Lower Bound

The authors first establish a theoretical "best-case" floor for queue lengths. They achieve this by comparing the complex, multi-server cluster to a simplified, single-server queue model, utilizing a variation of the Kingman bound.

2. State-Space Collapse

As the system approaches maximum capacity, the authors prove that the multi-dimensional state of all individual queues "collapses" toward a single dimension. In this state, the entire cluster begins to behave as one unified, ideal resource pool rather than a collection of fragmented servers.

3. Upper Bound and Optimality

Using Lyapunov functions—a tool from control theory—the authors demonstrate that specific policies (JSQ/Po2C combined with MaxWeight) stay extremely close to the theoretical lower bound, confirming their optimality in heavy traffic.

Key Insights and Algorithmic Findings

The Power of Two Choices (Po2C)

One of the most significant practical insights is that Power-of-Two-Choices (Po2C) routing is as optimal in heavy traffic as Join-the-Shortest-Queue (JSQ). This is vital for system architecture: while JSQ requires a central router to monitor the state of every server (creating high overhead), Po2C only requires checking two random servers. This research proves that this minimal information is sufficient to achieve peak efficiency.

Resource Pooling

The paper mathematically demonstrates the phenomenon of "resource pooling." In heavy traffic, the specific constraints of individual servers become less relevant than the aggregate capacity of the entire cluster, provided the right algorithms are used to balance the load effectively.

MaxWeight Scheduling

The MaxWeight scheduling algorithm, originally designed for wireless networks, is shown to be perfectly suited for the multi-resource constraints (CPU, RAM, and Disk) of cloud environments. When paired with JSQ or Po2C, it ensures that the cluster operates at the theoretical limit of efficiency.

Results and Implications

  • JSQ + MaxWeight Optimality: For clusters with identical servers, the authors proved this combination achieves the minimum possible expected queue length as the load approaches 100% capacity.
  • Po2C + MaxWeight Optimality: The proof extends to Po2C, showing it achieves the same heavy-traffic optimality despite having significantly less information about the system state.
  • Steady-State Guarantee: Because the results hold for the actual steady-state distribution of the system, they provide a robust guarantee for cloud providers managing long-term workloads.

Limitations and Future Directions

While the paper provides a landmark theoretical proof, it acknowledges several real-world constraints that warrant further study:

  • Server Heterogeneity: The current proof for state-space collapse assumes all servers in the cluster are identical. Real-world data centers often mix hardware generations; extending these proofs to heterogeneous environments remains an open challenge.
  • Communication Delays: The model assumes queue length information is updated instantly. In massive, geographically distributed clusters, the delay in reporting could impact the optimality of routing decisions.
  • Preemption Assumptions: The model assumes jobs can be preempted (paused and resumed). While common in many VM environments, the impact of non-preemptive scheduling on these optimality results is a potential area for future research.

Summary updated

BibTeX
@article{maguluri2014heavy,
  author = {Siva Theja Maguluri and R. Srikant and Lei Ying},
  title = {{Heavy traffic optimal resource allocation algorithms for cloud computing clusters}},
  journal = {Perform. Evaluation},
  year = {2014},
  doi = {10.1016/j.peva.2014.08.002},
}
Figure