MaxWeight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic

Rahul Singh, Alexander Stolyar

Research output: Contribution to journalConference articlepeer-review


The model is a "generalized switch", serving multiple traffic flows in discrete time. The switch uses MaxWeight algorithm to make a service decision (scheduling choice) at each time step, which determines the probability distribution of the amount of service that will be provided. We are primarily motivated by the following question: in the heavy traffic regime, when the switch load approaches critical level, will the service processes provided to each flow remain "smooth" (i.e., without large gaps in service)? Addressing this question reduces to the analysis of the asymptotic behavior of the unscaled queue-differential process in heavy traffic. We prove that the stationary regime of this process converges to that of a positive recurrent Markov chain, whose structure we explicitly describe. This in turn implies asymptotic "smoothness" of the service processes.

Original languageEnglish (US)
Pages (from-to)431-432
Number of pages2
JournalPerformance Evaluation Review
Issue number1
StatePublished - Jun 24 2015
Externally publishedYes
EventACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2015 - Portland, United States
Duration: Jun 15 2015Jun 19 2015


  • Dynamic scheduling
  • Heavy traffic asymptotic regime
  • Markov chain
  • MaxWeight algorithm
  • Queue length differentials
  • Smooth service process

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'MaxWeight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic'. Together they form a unique fingerprint.

Cite this