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

Rahul Singh, Aleksandr Stolyar

Research output: Contribution to journalConference article

Abstract

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
Volume43
Issue number1
DOIs
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

Fingerprint

Scheduling
Switches
Markov processes
Probability distributions

Keywords

  • 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

Cite this

MaxWeight scheduling : Asymptotic behavior of unscaled queue-differentials in heavy traffic. / Singh, Rahul; Stolyar, Aleksandr.

In: Performance Evaluation Review, Vol. 43, No. 1, 24.06.2015, p. 431-432.

Research output: Contribution to journalConference article

@article{8b8108b077ca4bb980f38324c69e52f5,
title = "MaxWeight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic",
abstract = "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.",
keywords = "Dynamic scheduling, Heavy traffic asymptotic regime, Markov chain, MaxWeight algorithm, Queue length differentials, Smooth service process",
author = "Rahul Singh and Aleksandr Stolyar",
year = "2015",
month = "6",
day = "24",
doi = "10.1145/2796314.2745878",
language = "English (US)",
volume = "43",
pages = "431--432",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "1",

}

TY - JOUR

T1 - MaxWeight scheduling

T2 - Asymptotic behavior of unscaled queue-differentials in heavy traffic

AU - Singh, Rahul

AU - Stolyar, Aleksandr

PY - 2015/6/24

Y1 - 2015/6/24

N2 - 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.

AB - 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.

KW - Dynamic scheduling

KW - Heavy traffic asymptotic regime

KW - Markov chain

KW - MaxWeight algorithm

KW - Queue length differentials

KW - Smooth service process

UR - http://www.scopus.com/inward/record.url?scp=84955580734&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84955580734&partnerID=8YFLogxK

U2 - 10.1145/2796314.2745878

DO - 10.1145/2796314.2745878

M3 - Conference article

AN - SCOPUS:84955580734

VL - 43

SP - 431

EP - 432

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 1

ER -