Source-linked AI summary
Heavy Traffic Optimal Resource Allocation Algorithms for Cloud Computing Clusters
Siva Theja Maguluri, R Srikant, Lei Ying
TL;DR
Cloud resource allocation must route incoming jobs to servers and schedule them under resource constraints, while queue-length performance is difficult to characterize exactly. The paper studies JSQ and power-of-two-choices routing with MaxWeight scheduling using heavy-traffic analysis. It reports heavy-traffic optimality for identical-server systems and a steady-state result for the routing-only, single-job-type case.
Problem
The paper focuses on queue length, or equivalently delay, because characterizing exact performance is difficult and the algorithms’ throughput optimality does not settle their heavy-traffic queue-length performance.
Source: §I · p. 1Method
The paper applies a three-step heavy-traffic procedure—lower bounding, approximate state-space collapse, and an upper bound—to routing and scheduling policies.
Source: §I · p. 2Results
JSQ with MaxWeight and power-of-two-choices routing with MaxWeight are heavy-traffic optimal for identical servers; power-of-two-choices is also heavy-traffic optimal in the single-job-type routing-only case.
Source: §V · p. 11Takeaways & Limitations
The paper establishes queue-length optimality in heavy traffic for the stated identical-server policies and presents a steady-state version of the routing-only result.
Source: §V · p. 11The JSQ-with-MaxWeight heavy-traffic result is established for identical servers; extending the state-space-collapse argument to non-identical servers remains open.
Source: B. State Space Collapse · p. 7
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper studies cloud resource allocation as routing jobs to servers and scheduling them under resource constraints, focusing on queue length in heavy traffic. It extends a three-step heavy-traffic analysis to JSQ and power-of-two-choices routing with MaxWeight scheduling, and also considers a single-job-type routing-only case.
II. SYSTEM MODEL AND ALGORITHM
- A server configuration specifies the numbers of jobs of each type served simultaneously, while the cloud capacity region combines the servers’ capacity regions.Feasible configurations depend on resource availability; the per-server region is formed from maximal configurations, and the total region is their Minkowski sum.Source: §I · p. 1, §II · pp. 2–3
I. INTRODUCTION
- The analysis uses a lower bound, approximate state-space collapse, and an upper bound that coincides with the lower bound in heavy traffic.The collapse is approximate: queue length grows along one direction near the capacity boundary, while perpendicular components remain bounded.Source: §I · pp. 1–2
II. SYSTEM MODEL AND ALGORITHM
- The model routes arrivals to servers, maintains type-specific queues, and schedules jobs subject to each server’s resource constraints.Jobs may be preempted and later resumed; the stated setting is applicable when job sizes are typically large.Source: §I · p. 2, §II · pp. 2–3
I. INTRODUCTION
- For identical servers, JSQ with MaxWeight is queue-length optimal in heavy traffic; power-of-two-choices routing with MaxWeight is also heavy-traffic optimal.The single-job-type case is treated separately because the results for the multi-type setting do not apply to its one-dimensional capacity region.Source: §I · p. 2
- For the routing-only case with identical jobs, power-of-two-choices is heavy-traffic optimal, complementing earlier results based on Brownian-motion limits.The paper’s contribution in this case is a distinct state-space-collapse argument and a steady-state result.Source: §I · p. 2
III. JSQ ROUTING AND MAXWEIGHT
The section specifies JSQ routing with MaxWeight scheduling and establishes its queue-length optimality in heavy traffic for identical servers. The proof follows a lower-bound, state-space-collapse, and upper-bound procedure.
III. JSQ ROUTING AND MAXWEIGHT
- JSQ routes each job type to the server with the shortest queue for that type, while each server selects a configuration to schedule jobs preemptively.Ties in routing are broken uniformly at random.Source: §III · p. 3
- The analysis considers arrival rates inside the capacity region approaching its boundary, with ε(k) denoting distance from hyperplane H(k).The proposition’s result applies to each k in Kᵒ_λ(ε).Source: §III · p. 4
- Under identical servers, JSQ routing with MaxWeight scheduling is heavy-traffic optimal, with the stated queue-length bound becoming tight as ε(k) ↓ 0.The proof obtains a lower bound, establishes state-space collapse, and then derives an upper bound.Source: §III · p. 4
A. Lower Bound
The lower-bound argument compares a weighted sum of expected queue lengths with a single-server queue. A single-server lower bound then yields a lower bound for the original system.
A. Lower Bound
- A single-server queue provides a lower bound on the original system’s weighted sum of expected queue lengths.The argument uses a single-server queue with the specified arrival and service processes, then applies a Lyapunov-function bound in steady state.Source: A. Lower Bound · p. 4
- The resulting lower bound remains informative in heavy traffic as ε(k) ↓ 0.The passage states this limiting conclusion after the single-server bound.Source: A. Lower Bound · p. 4
B. State Space Collapse
The proof establishes approximate state-space collapse along c(k): queue length in the perpendicular directions is bounded while the component along the critical direction grows near the capacity boundary. This collapse supports an upper bound, with the main result requiring identical servers.
B. State Space Collapse
- As ε(k) → 0, the queue component along c(k) grows while components perpendicular to c(k) remain bounded.The bounded perpendicular component does not contribute to the first-order term in 1/ε(k).Source: B. State Space Collapse · pp. 4–5
- The proof uses a drift argument for the perpendicular component, then applies a Lyapunov drift result to obtain finite moments.The drift bounds lead to Proposition 2.Source: B. State Space Collapse · pp. 5, 7
- The argument’s use of identical servers begins in the drift analysis after Equation (16); the upper bound would extend to non-identical servers if state-space collapse were established for that case.The paper identifies non-identical-server state-space collapse as an open problem.Source: B. State Space Collapse · pp. 6–7
- For identical servers, the proposition establishes finite steady-state queue-length moments under JSQ routing and MaxWeight scheduling.The result is stated for each k in Kᵒ_λ(ε), with finite constants for every positive integer moment order.Source: B. State Space Collapse · p. 7
- When the arrival rate approaches a capacity-region corner, the face-interior margin δ(k) can depend on ε(k), making the resulting bound ε(k)-dependent.In this case, there is no constant δ(k) with the stated face-interior property.Source: B. State Space Collapse · p. 7
C. Upper Bound
The upper-bound argument uses a Lyapunov function motivated by resource pooling; matching the upper bound to the lower bound establishes first-moment heavy-traffic optimality for JSQ routing with MaxWeight scheduling.
C. Upper Bound
- The argument bounds the steady-state terms using definitions and results for the MaxWeight schedule and its relation to the capacity region.The supplied passages state that the MaxWeight schedule lies inside the capacity region.Source: C. Upper Bound · pp. 7–8
- The upper bound coincides with the lower bound in the heavy-traffic limit, establishing first-moment heavy-traffic optimality for JSQ routing with MaxWeight scheduling.The proof concludes by bounding the weighted queue length in steady state.Source: C. Upper Bound · pp. 7, 9
D. Power-of-Two-Choices Routing and MaxWeight Scheduling
Because JSQ requires complete queue-length information, the paper considers power-of-two-choices routing, which samples two servers and routes each arrival to the shorter queue. With MaxWeight scheduling, its heavy-traffic proof follows the JSQ proof once a matching state-space-collapse relation is established.
D. Power-of-Two-Choices Routing and MaxWeight Scheduling
- JSQ requires complete queue-length information at the router, which can create considerable communication overhead when there are many servers.Source: D. Power-of-Two-Choices Routing and… · p. 9
- Power-of-two-choices routing samples two servers uniformly at random and sends each job to the one with the shorter queue.Ties are not specified in the supplied passage.Source: D. Power-of-Two-Choices Routing and… · p. 9
- Once the power-of-two-choices inequality matches the JSQ state-space-collapse relation, the remaining proof steps establish heavy-traffic optimality.The lower-bound proof and the upper-bound and state-space-collapse arguments carry over from JSQ.Source: D. Power-of-Two-Choices Routing and… · p. 9
IV. POWER-OF-TWO-CHOICES ROUTING
The section treats power-of-two-choices routing without scheduling as a single-queue-per-server special case. It defines the sampled-pair arrival process and queue notation, and notes that the prior face-based result does not apply at a capacity-region corner.
IV. POWER-OF-TWO-CHOICES ROUTING
- In the single-job-type special case, there is one queue per server and no scheduling is needed.Source: §IV · p. 9
Note on Notation
- The earlier result does not apply when arrival rates approach a capacity-region corner, where no common face normal exists for the state-space-collapse argument.The proof cannot define the ball B(k) at a corner point.Source: Note on Notation · pp. 9–10
- Each arriving job is restricted to a uniformly selected pair of servers and is routed to the shorter queue in that pair.The sampled-pair arrivals form correlated processes because only one pair receives a nonzero arrival at a time.Source: Note on Notation · p. 10
- The notation separates each queue vector into a component along the expected collapse direction and a perpendicular component.The perpendicular component is the queue vector minus its projection along that direction.Source: Note on Notation · p. 10
A. Lower Bound
The lower-bound argument compares the aggregate queue length with a single queue length as the arrival rate approaches capacity.
A. Lower Bound
- The lower bound is obtained by bounding the aggregate queue length below using a single queue length.The passage applies this comparison to the steady-state queue vector in heavy traffic.Source: A. Lower Bound · p. 10
B. State Space Collapse
The section bounds Lyapunov drift to establish state-space collapse. Negative drift for sufficiently large W⊥(q) supports the resulting finite-constant bounds.
B. State Space Collapse
- Bounding the drift of W⊥(Q) and applying Lemma 2 is the stated route to state-space collapse.Source: B. State Space Collapse · p. 10
- The derivation bounds terms in the drift, including sm(t) and um(t) by smax to obtain K3.Source: B. State Space Collapse · p. 11
- Negative drift for sufficiently large W⊥(q), together with finite drift with probability 1, yields finite constants via Lemma 2.Source: B. State Space Collapse · p. 11
C. Upper Bound
The upper bound for power-of-two-choices routing matches the heavy-traffic lower bound, establishing first-moment heavy-traffic optimality.
C. Upper Bound
- The upper bound is obtained by bounding each term in (24), as in the JSQ-routing case.The cited proof is identified as Proposition 3 in [8], and is not repeated here.Source: C. Upper Bound · p. 11
- The stated upper bound is then used to establish the heavy-traffic comparison with the lower bound.Source: C. Upper Bound · p. 11
- Matching the heavy-traffic lower bound establishes first-moment heavy-traffic optimality for power-of-two-choices routing.Source: C. Upper Bound · p. 11
V. CONCLUSIONS
The conclusions establish heavy-traffic optimality for JSQ with MaxWeight scheduling when servers are identical, and also for power-of-two-choices routing. For same-type jobs, the paper gives a steady-state Lyapunov-drift version of an established heavy-traffic result.
V. CONCLUSIONS
- JSQ routing with MaxWeight scheduling is heavy-traffic optimal when all servers are identical.The paper studies a stochastic model of load balancing and scheduling in cloud computing clusters.Source: §V · p. 11
- Power-of-two-choices routing instead of JSQ is also heavy-traffic optimal in the studied model.Source: §V · p. 11
- For same-type jobs, the paper presents a steady-state Lyapunov-drift proof of power-of-two-choices heavy-traffic optimality, previously established using diffusion limits.Source: §V · p. 11