Heavy-Traffic queue length behavior in a switch under Markovian arrivals

Shancong Mou, Siva Theja Maguluri

Research output: Contribution to journalArticlepeer-review

Abstract

This paper studies the input-queued switch operating under the MaxWeight algorithm when the arrivals are according to a Markovian process. We exactly characterize the heavy-Traffic scaled mean sum queue length in the heavy-Traffic limit, and show that it is within a factor of less than 2 from a universal lower bound. Moreover, we obtain lower and upper bounds that are applicable in all traffic regimes and become tight in the heavy-Traffic regime. We obtain these results by generalizing the drift method recently developed for the case of independent and identically distributed arrivals to the case of Markovian arrivals. We illustrate this generalization by first obtaining the heavy-Traffic mean queue length and its distribution in a single-server queue under Markovian arrivals and then applying it to the case of an input-queued switch. The key idea is to exploit the geometric mixing of finite-state Markov chains, and to work with a time horizon that is chosen so that the error due to mixing depends on the heavy-Traffic parameter.

Original languageEnglish (US)
Pages (from-to)1106-1152
Number of pages47
JournalAdvances in Applied Probability
Volume56
Issue number3
DOIs
StatePublished - Sep 1 2024
Externally publishedYes

Bibliographical note

Publisher Copyright:
© The Author(s), 2024.

Keywords

  • Input-queued switch
  • Markov chain mixing
  • drift method
  • heavy-Traffic limit
  • single-server queue

Fingerprint

Dive into the research topics of 'Heavy-Traffic queue length behavior in a switch under Markovian arrivals'. Together they form a unique fingerprint.

Cite this