Asymptotically tight steady-state queue length bounds implied by drift conditions
From MaRDI portal
Publication:373455
DOI10.1007/S11134-012-9305-YzbMATH Open1273.90054arXiv1104.0327OpenAlexW1995643834MaRDI QIDQ373455FDOQ373455
Authors: Atilla Eryilmaz, R. Srikant 
Publication date: 22 October 2013
Published in: Queueing Systems (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1104.0327
Recommendations
- Stability and probability. I: Convergence for queueing networks via Lyapunov optimization
- Logarithmic heavy traffic error bounds in generalized switch and load balancing systems
- Heavy-Traffic Analysis of Queueing Systems with No Complete Resource Pooling
- Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions
- Stability and moment bounds under utility-maximising service allocations: finite and infinite networks
Queues and service in operations research (90B22) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Communication networks in operations research (90B18) Lyapunov and other classical stabilities (Lagrange, Poisson, (L^p, l^p), etc.) in control theory (93D05)
Cites Work
- Applied Probability and Queues
- Markov chains and stochastic stability
- Title not available (Why is that?)
- MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
- Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies
- Dynamic server allocation to parallel queues with randomly varying connectivity
- Weak convergence theorems for priority queues: preemptive-resume discipline
- Hitting-time and occupation-time bounds implied by drift analysis with applications
- Control Techniques for Complex Networks
- Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling
- Stability of queueing networks and scheduling policies
- Heavy traffic resource pooling in parallel-server systems
- Some inequalities for the queue GI/G/1
- Optimization of multiclass queueing networks: Polyhedral and nonlinear characterizations of achievable performance
- Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions
- A Basic Dynamic Routing Problem and Diffusion
- Performance bounds for queueing networks and scheduling policies
- State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy
- Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse
- State space collapse with application to heavy traffic limits for multiclass queueing networks
- Title not available (Why is that?)
- Resource pooling in queueing networks with dynamic routing
- Dynamic scheduling of a parallel server system in heavy traffic with complete resource pooling: asymptotic optimality of a threshold policy
- Bounding blocking probabilities and throughput in queueing networks with buffer capacity constraints
- Dynamic scheduling for minimum delay in tandem and parallel constrained queueing models
- Asymptotic optimality of maximum pressure policies in stochastic processing networks
- Validity of heavy traffic steady-state approximations in generalized Jackson networks
- Equivalent Models for Queueing Analysis of Deterministic Service Time Tree Networks
- Bounding Stationary Expectations of Markov Processes
- Stability and Asymptotic Optimality of Generalized MaxWeight Policies
- Systems with large flexible server pools: instability of ``natural load balancing
- Optimal dynamic scheduling of a general class of parallel-processing queueing systems
- Optimal Control of a Multiclass, Flexible Queueing System
- Pathwise optimality of the exponential scheduling rule for wireless channels
- On the Queue-Overflow Probability of Wireless Systems: A New Approach Combining Large Deviations With Lyapunov Functions
- Practical scheduling schemes with throughput guarantees for multi-hop wireless networks
Cited In (19)
- Distributed dispatching in the parallel server model
- Qualitative properties of \(\alpha\)-fair policies in bandwidth-sharing networks
- Steady-state analysis of the join-the-shortest-queue model in the Halfin-Whitt regime
- Heavy-Traffic Analysis of Queueing Systems with No Complete Resource Pooling
- Logarithmic heavy traffic error bounds in generalized switch and load balancing systems
- An algorithm for improved delay-scaling in input-queued switches
- Fluctuation Bounds for the Max-Weight Policy with Applications to State Space Collapse
- The capacity of QoE for wireless networks with unreliable transmissions
- Optimal heavy-traffic queue length scaling in an incompletely saturated switch
- Tail bounds on hitting times of randomized search heuristics using variable drift analysis
- <scp>Steady‐state</scp> analysis of load balancing with Coxian‐2 distributed service times
- Process flexibility for multiperiod production systems
- A load balancing system in the many-server heavy-traffic asymptotics
- Diffusion limit of fair resource control -- stationarity and interchange of limits
- Heavy traffic queue length scaling in switches with reconfiguration delay
- Stationary distribution convergence of the offered waiting processes in heavy traffic under general patience time scaling
- Transform methods for heavy-traffic analysis
- Throughput and delay optimality of power-of-\(d\) choices in inhomogeneous load balancing systems
- Heavy-Traffic Insensitive Bounds for Weighted Proportionally Fair Bandwidth Sharing Policies
This page was built for publication: Asymptotically tight steady-state queue length bounds implied by drift conditions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q373455)
