Heavy-Traffic Analysis of Queueing Systems with No Complete Resource Pooling
From MaRDI portal
Abstract: We study the heavy-traffic limit of the generalized switch operating under MaxWeight, without assuming that the CRP condition is satisfied and allowing for correlated arrivals. The main contribution of this paper is the steady-state mean of linear combinations of queue lengths in heavy traffic. We showcase the generality of our result by presenting various stochastic networks as corollaries, each of which is a contribution by itself. In particular, we study the input-queued switch with correlated arrivals and we show that if the state space collapses to a full-dimensional subspace, the correlation among the arrival processes does not matter in heavy traffic. We exemplify this last case with a parallel-server system, an N-system, and an ad hoc wireless network. While the above results are obtained using the drift method, we additionally present a negative result showing a limitation of the drift method. We show that it is not possible to obtain the individual queue lengths using the drift method with polynomial test functions. We do this by presenting an alternate view of the drift method in terms of a system of linear equations, and we use this system of equations to obtain bounds on arbitrary linear combinations of the queue lengths.
Recommendations
- Logarithmic heavy traffic error bounds in generalized switch and load balancing systems
- Heavy traffic queue length behavior in a switch under the MaxWeight algorithm
- Transform methods for heavy-traffic analysis
- Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse
- MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
Cites work
- Asymptotic optimality of maximum pressure policies in stochastic processing networks
- Asymptotically tight steady-state queue length bounds implied by drift conditions
- Brownian models of performance and control
- Diffusion approximation for an input-queued switch operating under a maximum weight matching policy
- Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy
- Dynamic scheduling of a two-server parallel server system with complete resource pooling and reneging in heavy traffic: asymptotic optimality of a two-threshold policy
- Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies
- Heavy traffic queue length behavior in a switch under the MaxWeight algorithm
- Heavy traffic resource pooling in parallel-server systems
- Hitting-time and occupation-time bounds implied by drift analysis with applications
- MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
- On dynamic scheduling of a parallel server system with complete resource pooling
- Optimal heavy-traffic queue length scaling in an incompletely saturated switch
- Optimal scaling of average queue sizes in an input-queued switch: an open problem
- Optimization of multiclass queueing networks: Polyhedral and nonlinear characterizations of achievable performance
- Performance bounds for queueing networks and scheduling policies
- Process flexibility for multiperiod production systems
- Some inequalities for the queue GI/G/1
- Stability and Asymptotic Optimality of Generalized MaxWeight Policies
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
- Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits
- The Stability of Longest-Queue-First Scheduling With Variable Packet Sizes
Cited in
(10)- Heavy traffic analysis of open processing networks with complete resource pooling: asymptotic optimality of discrete review policies
- Heavy traffic queue length behavior in a switch under the MaxWeight algorithm
- Asymptotically tight steady-state queue length bounds implied by drift conditions
- A unified method to analyze overtake free queueing systems
- Transform methods for heavy-traffic analysis
- HEAVY-TRAFFIC ANALYSIS OF K-LIMITED POLLING SYSTEMS
- HEAVY-TRAFFIC ANALYSIS OF A NON-PREEMPTIVE MULTI-CLASS QUEUE WITH RELATIVE PRIORITIES
- Heavy traffic analysis of multi-class bipartite queueing systems under FCFS
- Convergence of natural policy gradient for a family of infinite-state queueing MDPs
- Heavy-traffic queue length behavior in a switch under Markovian arrivals
This page was built for publication: Heavy-Traffic Analysis of Queueing Systems with No Complete Resource Pooling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5870370)
