Heavy Traffic Optimal Resource Allocation Algorithms for Cloud Computing Clusters

Siva Theja Maguluri, R Srikant, Lei Ying

TL;DR

This paper proves that two popular load-balancing and scheduling strategies—Join-the-Shortest-Queue (JSQ) and Power-of-Two-Choices combined with MaxWeight scheduling—are queue-length optimal in the "heavy traffic" limit. This means that as a cloud cluster approaches its maximum capacity, these algorithms minimize the total backlog (and thus delay) across the system.

What Problem Does This Paper Address?

Managing resources in a cloud computing cluster is a multi-dimensional headache. A single job might require specific amounts of CPU, RAM, and storage, and a physical server can only host a combination of jobs that fit within its total resource envelope.

Researchers typically split this into two sub-problems:

  1. Routing (Load Balancing): When a job arrives at the cluster, which server should it go to?
  2. Scheduling: Once a server has a queue of jobs, which ones should it run right now to maximize efficiency?

Previous research had already established that combining JSQ routing with MaxWeight scheduling was throughput optimal—meaning it can keep the system stable as long as the arrival rate is within the cluster's capacity. However, "stable" doesn't necessarily mean "fast." The gap addressed here is delay optimality: do these algorithms minimize the number of jobs waiting in line when the system is pushed to its limits (the "heavy traffic" regime)?

Methods

The authors use a stochastic model of a discrete-time cloud system with $M$ servers and $J$ job types. They analyze two main algorithmic pairings:

  • JSQ + MaxWeight: Jobs are routed to the server with the shortest queue for that specific job type. Servers then use the MaxWeight algorithm to pick a "configuration" (a set of jobs) that maximizes the weighted sum of their queue lengths.
  • Power-of-Two-Choices + MaxWeight: To reduce communication overhead, the router picks two servers at random and sends the job to the one with the shorter queue.

To prove optimality, the authors move away from traditional, complex Brownian motion limits. Instead, they employ a three-step Lyapunov drift method:

  1. Lower Bound: They establish a theoretical minimum for expected queue lengths by comparing the system to a single-server queue (similar to the Kingman bound).
  2. State-Space Collapse: They prove that in heavy traffic, the multi-dimensional state of the system (all the different queues) effectively "collapses" and behaves like a one-dimensional system.
  3. Upper Bound: They use Lyapunov functions to show that the actual queue lengths of their algorithms don't exceed the lower bound in the limit.

Datasets

Not discussed in the paper. This is a theoretical performance analysis paper. It relies on rigorous mathematical proofs and stochastic modeling rather than empirical testing on specific datasets or benchmarks.

Key Insights and Ideas

  • The "Aha" of State-Space Collapse: The most critical insight is that as the system nears capacity, the queues don't just grow randomly. They grow primarily along a specific "normal vector" relative to the capacity region. The "perpendicular" components of the queue lengths remain bounded, effectively simplifying a complex multi-server problem into a simpler one.
  • Communication vs. Performance: The paper shows that you don't need perfect information to be optimal. The "Power-of-Two-Choices" algorithm, which requires significantly less communication between the router and servers than JSQ, achieves the same heavy-traffic optimality.
  • Steady-State Focus: Unlike previous methods that proved optimality over finite time intervals, this Lyapunov-based approach proves that the system remains optimal in a permanent, steady state.

Key Results

  • JSQ + MaxWeight Optimality: For clusters with identical servers, the authors proved that JSQ + MaxWeight is queue-length optimal. Specifically, the limit of the expected weighted queue length matches the theoretical lower bound as the arrival rate approaches the boundary of the capacity region.
  • Power-of-Two-Choices Success: They successfully extended this proof to the Power-of-Two-Choices routing algorithm, confirming it is also heavy-traffic optimal.
  • Tight Bounds: The paper demonstrates that the upper and lower bounds for these algorithms coincide in the heavy traffic limit, providing a "tight" result that leaves no room for a more optimal policy in that regime.

Limitations and Future Work

  • Identical Servers: A significant limitation is that the proof for state-space collapse currently requires all servers in the cluster to be identical (same CPU, RAM, etc.). The authors explicitly note that establishing this for non-identical servers remains an open problem.
  • Heavy Traffic Limit: The results are asymptotic. While they prove optimality as the load approaches 100%, they don't necessarily characterize the best possible performance for a lightly loaded system (e.g., at 50% capacity).
  • Preemptive Assumptions: The model assumes jobs can be preempted (paused and resumed), which is common in some cloud environments (like containers) but not all. Analyzing non-preemptive scheduling would be a natural next step.

Summary updated

Abstract

Cloud computing is emerging as an important platform for business, personal and mobile computing applications. In this paper, we study a stochastic model of cloud computing, where jobs arrive according to a stochastic process and request resources like CPU, memory and storage space. We consider a model where the resource allocation problem can be separated into a routing or load balancing problem and a scheduling problem. We study the join-the-shortest-queue routing and power-of-two-choices routing algorithms with MaxWeight scheduling algorithm. It was known that these algorithms are throughput optimal. In this paper, we show that these algorithms are queue length optimal in the heavy traffic limit.
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