Heavy-Traffic Analysis of Queueing Systems with no Complete Resource Pooling
Preprint
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.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Optimal heavy-traffic queue length scaling in an incompletely saturated switchQueueing Systems, 2017
- On the Performance of Largest-Deficit-First for Scheduling Real-Time Traffic in Wireless NetworksIEEE/ACM Transactions on Networking, 2014
- Brownian Models of Performance and Control2013
- Asymptotically tight steady-state queue length bounds implied by drift conditionsQueueing Systems, 2012
- Optimal scaling of average queue sizes in an input-queued switch: an open problemQueueing Systems, 2011
- Delay Analysis for Wireless Networks With Single Hop Traffic and General Interference ConstraintsIEEE/ACM Transactions on Networking, 2009
- Stability and Asymptotic Optimality of Generalized MaxWeight PoliciesSIAM Journal on Control and Optimization, 2009
- Heavy traffic resource pooling in parallel‐server systemsQueueing Systems, 1999
- Performance bounds for queueing networks and scheduling policiesIEEE Transactions on Automatic Control, 1994
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networksIEEE Transactions on Automatic Control, 1992