PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotically Tight Steady-State Queue Length Bounds Implied By Drift Conditions

Atilla Eryilmaz, R. Srikant

arXiv:1104.0327v3math.PRcs.NI

TL;DR

Simple steady-state drift bounds can be too loose because they miss resource pooling in complex queueing systems. This paper adds steady-state state-space collapse to Lyapunov-drift analysis and obtains heavy-traffic-tight queue-length bounds, including first-moment optimality for JSQ routing and MaxWeight scheduling.

  • Problem

    Standard Lyapunov-drift moment bounds for queueing systems can be extremely loose because they do not exploit heavy-traffic resource pooling effects.

  • Method

    The paper derives steady-state state-space collapse for weighted queue-length differences and incorporates it into Lyapunov-drift moment-bound derivations.

  • Results

    The resulting bounds are tight in heavy traffic and establish first-moment heavy-traffic optimality for JSQ routing and MaxWeight scheduling.

  • Takeaways & Limitations

    Steady-state drift analysis can capture resource pooling when queue-length differences have bounded moments and the state collapses toward a single dimension.

  • Takeaways & Limitations

    The presented results apply to systems whose state collapses to a single dimension and include a finite-state, i.i.d. channel-fading model.

Abstract

from arXiv · show

The Foster-Lyapunov theorem and its variants serve as the primary tools for studying the stability of queueing systems. In addition, it is well known that setting the drift of the Lyapunov function equal to zero in steady-state provides bounds on the expected queue lengths. However, such bounds are often very loose due to the fact that they fail to capture resource pooling effects. The main contribution of this paper is to show that the approach of "setting the drift of a Lyapunov function equal to zero" can be used to obtain bounds on the steady-state queue lengths which are tight in the heavy-traffic limit. The key is to establish an appropriate notion of state-space collapse in terms of steady-state moments of weighted queue length differences, and use this state-space collapse result when setting the Lyapunov drift equal to zero. As an application of the methodology, we prove the steady-state equivalent of the heavy-traffic optimality result of Stolyar for wireless networks operating under the MaxWeight scheduling policy.

1 Introduction

The paper develops a Lyapunov-drift approach that incorporates steady-state state-space collapse to obtain queue-length bounds tight in heavy traffic. It applies the methodology to JSQ routing and MaxWeight scheduling.

  • Motivation: Heavy-traffic queueing analysis often establishes scaled sample-path optimality, while proving convergence to the steady-state distribution is an additional step not often undertaken.
  • Motivation: Simple steady-state drift bounds are easy to derive but may be loose because they do not exploit resource pooling effects.
  • Applications: The methodology is illustrated for parallel servers with JSQ routing and wireless networks operating under MaxWeight scheduling.
  • Contribution: The main contribution is a Lyapunov-drift approach for obtaining steady-state queue-length bounds that are tight in heavy traffic.
  • Methodology: The method first derives lower bounds, then proves steady-state moment state-space collapse, and finally uses a resource-pooling Lyapunov function for an asymptotically tight upper bound.

2 Notation, System Models and Other Preliminaries

The paper establishes queueing notation and models for parallel-queue routing and constrained scheduling, then states a drift-based moment bound used to prove state-space collapse. It also records stability and finite-steady-state-moment properties for JSQ and MW policies within their capacity regions.

  • Notation and queue evolution: Queue lengths evolve synchronously in L time-slotted queues as Q_l[t+1] = Q_l[t] + A_l[t] − S_l[t] + U_l[t], with unused service U_l[t].Arrivals and offered services are nonnegative integer-valued, and boldface vectors represent L-dimensional queue, arrival, service, and unused-service quantities.
  • Drift-based moment bound: Under the stated drift conditions and positive recurrence, Hajek’s lemma implies that the limiting Lyapunov variable has all moments finite.The result applies to an irreducible, aperiodic Markov chain with a nonnegative Lyapunov function and is used to prove state collapse.
  • Routing model and JSQ: JSQ routes each slot’s arrivals to a shortest queue, breaking ties uniformly, to equalize queue lengths and emulate pooled server resources.The routing model uses L parallel servers, and its arrival and service processes are independent, i.i.d., bounded, and nonnegative integer-valued.
  • Routing stability: For λΣ > µΣ, no feasible routing policy can stabilize the parallel-queue network.Here µΣ is the maximum achievable aggregate service rate, defined as the sum of the individual mean service rates.
  • Routing stability: For λΣ < µΣ, JSQ stabilizes the network with a steady-state queue-length vector whose all moments are bounded.The queue-length process converges in distribution to a random vector with finite bounds on every moment.
  • Scheduling model and MW: For scheduling, arrival rates outside the capacity region cannot be stabilized, whereas MW stabilizes rates in the interior of that region.The scheduling model selects instantaneous service-rate vectors subject to feasibility constraints on simultaneous service.

3 Lower Bounds

Section 3 derives steady-state queue-length lower bounds by comparing routing and scheduling systems with appropriately constructed single-server queues. These bounds become informative in heavy traffic as the arrival rate approaches service capacity from below.

  • Single-server lower bound: A single-server queue with bounded-support i.i.d. arrivals and services provides the foundational lower bound for routing and scheduling systems.The queue evolves as Φ[t + 1] = (Φ[t] + α[t] − β[t])^+, with arrival and service processes independent over time.
  • Single-server lower bound: For any ǫ > 0, the parameterized single-server queue is positive Harris recurrent, converges in distribution, and has all bounded moments.Its mean queue length is lower-bounded using a quadratic Lyapunov drift argument, with ǫ = β − α(ǫ).
  • Single-server lower bound: In heavy traffic, the single-server lower bound is asymptotically characterized as ǫ ↓0 when the mean arrival rate approaches the mean service rate from below.The limiting expression depends on the arrival and service variances through ζ ≜ σ2_α + ν2_β.
  • Routing lower bounds: For routing, a hypothetical pooled server with aggregate arrivals and aggregate service is stochastically smaller than the original system’s total queue length under any feasible policy.Applying the single-server bound therefore yields lower bounds for every routing policy, including JSQ, for all arrival rates.
  • Scheduling lower bounds: For scheduling, each capacity-region face yields a distinct lower bound on the weighted queue length ⟨c(k), Q[t]⟩.The associated single-server queue uses projected arrivals α(k)[t] = ⟨c(k), A[t]⟩ and service β(k)[t] = b(k), and is stochastically smaller under any feasible scheduling policy.

4 State-Space Collapse

The section establishes state-space collapse through steady-state moment bounds on queue-length deviations from an appropriate line. These bounds remain independent of heavy-traffic proximity, making deviations negligible relative to the growing total queue length and supporting heavy-traffic optimality.

  • Core state-space collapse: Steady-state queue lengths concentrate around a line, with deviations bounded independently of the heavy-traffic parameter ǫ.This moment-based formulation is presented as equivalent to state-space collapse in prior fluid and diffusion analyses.
  • Core state-space collapse: All moments of the perpendicular component ∥Q⊥∥ are bounded by constants independent of proximity to the capacity-region boundary.The proof uses a Lyapunov function V⊥(Q) = ∥Q⊥∥ whose drift is bounded and strictly negative when the perpendicular component is sufficiently large.
  • JSQ Routing: As ǫ approaches zero, queue-length differences remain bounded in moments while the lower bound on total queue length diverges, making deviations negligible comparatively.This contrast is used to support the heavy-traffic analysis in Section 5.
  • MW Scheduling: For MW Scheduling, the attraction line depends on the arrival-rate face, and Proposition 2 asserts finite constants for each fixed face F(k) and λ(k) ∈ Relint(F(k)).The relevant line is associated with a hyperplane enclosing the capacity region.

5 Upper Bounds and Heavy-Traffic Optimality

The section develops Lyapunov-drift upper bounds for steady-state queue lengths and shows they become asymptotically tight in heavy traffic by incorporating state-space collapse. It establishes first-moment heavy-traffic optimality for both JSQ routing and MaxWeight scheduling.

  • Upper bounds and methodology: The analysis sets steady-state Lyapunov drift to zero and uses state-space collapse to derive queue-length upper bounds that are asymptotically tight as arrival rates approach capacity boundaries.The state-space-collapse results control the unused-service term in the drift bound, which vanishes in heavy traffic.
  • JSQ routing: JSQ routing has a steady-state total queue-length upper bound that matches the heavy-traffic lower bound for every feasible policy, establishing first-moment heavy-traffic optimality.The result applies as network load approaches capacity.
  • MW scheduling: MW scheduling has a steady-state weighted total queue-length upper bound that matches the heavy-traffic lower bound for every feasible policy, establishing first-moment heavy-traffic optimality.The result holds as the network load approaches the boundary of the capacity region.
  • MW scheduling: O(ǫ) bounds the MW Scheduler’s time outside the relevant capacity-region face, so this fraction vanishes as ǫ ↓0.The constant γ(k), determined by the discrete service-set geometry, supports this bound.
  • MW scheduling: When ǫ is small, the MW Scheduler mostly selects service rates on the face F(k), making the average service rate exceed arrivals componentwise to maintain stability.This reflects arrivals approaching the face and the scheduler concentrating service there.

6 Some Extensions of the Results on the Scheduling Problem

The section extends the drift-and-state-space-collapse methodology to nth-moment queue-length bounds and channel fading. It establishes heavy-traffic optimality of MaxWeight scheduling for these extensions, including first-moment optimality under fading.

  • Nth-moment bounds: The nth-moment analysis combines lower bounds for a lower-bounding system with state-space-collapse-based upper bounds whose dominant terms match in heavy traffic.The matching occurs as the arrival-rate vector approaches a face of the capacity region.
  • Nth-moment bounds: In heavy traffic, the dominant nth-moment terms for the lower-bounding system depend only on ζ, determined by arrival and service variances.This agrees with Brownian approximations based on the first two moments of arrivals and service.
  • MaxWeight optimality: State-space collapse makes total unused service under MaxWeight vanish in heavy traffic, allowing the scheduling system to match the lower-bound asymptotics.Comparing the lower and upper bounds establishes nth-moment heavy-traffic optimality of MaxWeight scheduling.
  • MaxWeight optimality: For n = 2, MaxWeight minimizes the heavy-traffic limit of the squared norm of the queue-length projection and achieves the smallest limit attainable by any policy.This establishes second-moment heavy-traffic optimality.
  • Channel fading: Under channel fading, the heavy-traffic bounds include Var(β(k)), which captures the fading distribution’s impact on steady-state mean queue-length levels.The resulting comparison establishes first-moment heavy-traffic optimality of MaxWeight under fading; unused service is O(ǫ) in each channel state.

7 Conclusions

The paper shows that steady-state drift conditions can yield heavy-traffic-tight queue-length moment bounds when sharpened by an appropriate steady-state state-space-collapse result.

  • 7 Conclusions: The main contribution is heavy-traffic-tight bounds on queue-length moments derived from steady-state drift conditions.The approach relies on a new notion of steady-state state-space collapse to sharpen drift-based bounds.
  • 7 Conclusions: The results apply when the system state collapses to a single dimension.Whether the methodology extends to other forms of state-space collapse remains an open research topic.

A Proof of Lemma 2

The proof applies Lemma 1 to the queue-length Markov chain with Lyapunov function V(Q)=∥Q∥. It verifies conditions (C1) and (C2) using concavity, a quadratic-drift expansion, and bounded arrivals and services.

  • Proof setup: Lemma 1 is applied to X[t]:=Q[t] with Lyapunov function V(Q):=∥Q∥.The proof begins by checking conditions (C1) and (C2) for this choice.
  • Condition (C1): Concavity of the square-root function bounds the one-step drift of ∥Q∥ using the corresponding quadratic norm difference.The argument sets y:=∥Q[t+1]∥2 and x:=∥Q[t]∥2, then studies the mean drift of W(Q):=∥Q∥2.
  • Condition (C1): The quadratic drift is expanded after writing the next queue state in terms of Q, arrivals A, services S, and unused service U.The proof uses the queue evolution expansion and the relation Ul(Ql+Al−Sl)=−U^2_l for the relevant inequality.
  • Condition (C2): Bounded arrivals and services verify (C2), completing the proof.The argument uses ∥x∥1≥∥x∥ and the uniform bounds Amax and Smax for all queues and times.
  • Condition (C1): Defining ϵ:=µΣ−λΣ and λl:=µl−ϵ, the proof rewrites the inner product drift term and verifies (C1).The constructed vector λ has total rate matching λΣ, and the subsequent bound uses the JSQ policy and the l1 norm.

B Proof of Lemma 7

The proof establishes inequalities (18) and (19) using concavity, Pythagoras’ theorem, norm inequalities, projection non-expansiveness, and bounded arrivals and services.

  • Proof of (18): Inequality (18) follows from concavity of the norm-related function and Pythagoras’ theorem applied to the orthogonal and parallel queue components.The proof sets y := ∥Q⊥[t + 1]∥2 and x := ∥Q⊥[t]∥2, then uses the decomposition into Q∥ and Q⊥.
  • Proof of (19): Inequality (19) is derived by decomposing the queue vector into orthogonal and parallel components and bounding successive norm differences.The displayed term uses Q = Q⊥ + Q∥ and the indicator I(Q[t] = Q).
  • Proof of (19): The bounds rely on the reverse triangle inequality, triangle inequality, non-expansiveness of projection onto the line along c, norm definitions, and bounded Al[t] and Sl[t].The projection argument gives ∥Q∥[t + 1] − Q∥[t]∥ ≤ ∥Q[t + 1] − Q[t]∥, while arrivals and services are bounded by Amax.

C Proof of Lemma 10

The proof analyzes the steady-state drift of W_n(Φ)=∥Φ∥_n and uses induction to show the relevant scaled moment terms vanish as ε↓0. This establishes (57), from which the heavy-traffic result (58) follows by taking limits.

  • Drift calculation: The proof studies the conditional mean drift of W_n(Φ)=∥Φ∥_n using the queue evolution and then takes expectations under the steady-state distribution.The derivation uses the definition of χ, independence of arrivals and services, and E[β−α]=ε.
  • Vanishing terms: For n≥2, the final term in the drift expansion vanishes as ε↓0.This follows from the steady-state identity E[χ]=ε.
  • Inductive argument: An induction shows that the remaining summation terms vanish with ε, starting from the trivial base case and extending from n to n+1.The induction uses bounded moments of α−β and the vanishing of the χ-dependent term.
  • Conclusion: The proof establishes that the scaled moment terms ǫ^(n−2)E[...] vanish for all n≥3 and the required index range, proving (57).The result follows after returning to the drift expansion and restoring the ε dependence.
  • Conclusion: The heavy-traffic result (58) follows immediately by taking both sides to the limit as ε↓0.The preceding vanishing-term results provide the limit needed for this step.

D Proof of Proposition 5

The proof establishes the upper bound by showing that the error terms in the steady-state Lyapunov-drift recursion vanish as ϵ ↓ 0. The claimed heavy-traffic result then follows immediately from the recursively derived upper bound.

  • D Proof of Proposition 5: The proof analyzes the mean drift of an nth-moment Lyapunov function under the steady-state distribution.The arrival and queue-length superscript (ϵ) is temporarily omitted for exposition.
  • D Proof of Proposition 5: The steady-state drift identity yields a recursive relationship whose upper bound follows inductively once expressions (80) and (81) vanish as ϵ ↓ 0.The proof studies both expressions for all n ≥ 2.
  • D Proof of Proposition 5: Expression (80) is shown to be of order O(√ϵ), so it vanishes as ϵ ↓ 0 for every n ≥ 2.The argument uses independence of arrival processes, Proposition 2, and bounded arrivals.
  • D Proof of Proposition 5: Expression (81) also vanishes as ϵ ↓ 0, using separate bounds for i ≤ n/2 and i > n/2 together with Lemma 9 and Cauchy-Schwarz.For i ≤ n/2, the relevant bound is O(√ϵ).
  • D Proof of Proposition 5: The vanishing of (80) + (81) enables induction through (79) to derive upper bound (61), from which heavy-traffic result (62) follows immediately.This completes the proof.
Loading 1104.0327v3…