Queue Stability and Probability 1 Convergence via Lyapunov Optimization

Abstract

Lyapunov drift and Lyapunov optimization are powerful techniques for optimizing time averages in stochastic queueing networks subject to stability. However, there are various definitions of queue stability in the literature, and the most convenient Lyapunov drift conditions often provide stability and performance bounds only in terms of a time average expectation, rather than a pure time average. We extend the theory to show that for quadratic Lyapunov functions, the basic drift condition, together with a mild bounded fourth moment condition, implies all major forms of stability. Further, we show that the basic drift-plus-penalty condition implies that the same bounds for queue backlog and penalty expenditure that are known to hold for time average expectations also hold for pure time averages with probability 1. Our analysis combines Lyapunov drift theory with the Kolmogorov law of large numbers for martingale differences with finite variance.

This version 2 of the paper contains a new and useful theorem (Theorem 3) on rate stability if the quadratic Lyapunov drift is less than or equal to a constant and if second moments of queue changes are bounded

References in corpus (4)

• Stability and Capacity Regions or Discrete Time Queueing Networks
• Delay Reduction via Lagrange Multipliers in Stochastic Network Optimization
• Max Weight Learning Algorithms with Application to Scheduling in Unknown Environments
• Scheduling in Wireless Networks under Uncertainties: A Greedy Primal-Dual Approach

Cited by in corpus (6)

• Joint Sampling and Transmission Policies for Minimizing Cost under AoI Constraints
• Dynamic Power Control for Time-Critical Networking with Heterogeneous Traffic
• Dynamic Optimization and Learning for Renewal Systems
• Dynamic Index Coding for Wireless Broadcast Networks
• Network Control without CSI using Rateless Codes for Downlink Cellular Systems
• Optimal Dynamic Cloud Network Control