Heavy-Traffic Analysis of Queueing Systems with No Complete Resource Pooling

Daniela Andrea Hurtado Lange*, Siva Theja Maguluri

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We study the heavy-traffic limit of the generalized switch operating under MaxWeight, without assuming that the complete resource pooling 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. Whereas these 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.

Original languageEnglish (US)
Pages (from-to)3129-3155
Number of pages27
JournalMathematics of Operations Research
Volume47
Issue number4
DOIs
StatePublished - Nov 2022

Keywords

  • drift method
  • generalized switch
  • input-queued switch
  • N-system
  • state space collapse

ASJC Scopus subject areas

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Heavy-Traffic Analysis of Queueing Systems with No Complete Resource Pooling'. Together they form a unique fingerprint.

Cite this