Large deviations of queues sharing a randomly time-varying server

Research output: Contribution to journalArticle

Abstract

We consider a discrete-time model where multiple queues, each with its own exogenous arrival process, are served by a server whose capacity varies randomly and asynchronously with respect to different queues. This model is primarily motivated by the problem of efficient scheduling of transmissions of multiple data flows sharing a wireless channel. We address the following problem of controlling large deviations of the queues: find a scheduling rule, which is optimal in the sense of maximizing (Equation Presented), where Qi is the length of the i-th queue in a stationary regime, and ai >0 are parameters. Thus, we seek to maximize the minimum of the exponential decay rates of the tails of distributions of weighted queue lengths a iQi. We give a characterization of the upper bound on (0.1) under any scheduling rule, and of the lower bound on (0.1) under the exponential (EXP) rule. We prove that the two bounds match, thus proving optimality of the EXP rule. The EXP rule is very parsimonious in that it does not require any "pre-computation" of its parameters, and uses only current state of the queues and of the server. The EXP rule is not invariant with respect to scaling of the queues, which complicates its analysis in the large deviations regime. To overcome this, we introduce and prove a refined sample path large deviations principle, or refined Mogulskii theorem, which is of independent interest.

Original languageEnglish (US)
Pages (from-to)1-35
Number of pages35
JournalQueueing Systems
Volume59
Issue number1
DOIs
StatePublished - May 1 2008
Externally publishedYes

Fingerprint

Servers
Scheduling
Time-varying
Queue
Large deviations
Scheduling rules

Keywords

  • Dynamic scheduling
  • Exponential (EXP) rule
  • Local fluid limit
  • Quality of service
  • Queueing networks
  • Refined Mogulskii theorem
  • Sample path large deviations principle
  • Time-varying server

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research
  • Computational Theory and Mathematics

Cite this

Large deviations of queues sharing a randomly time-varying server. / Stolyar, Aleksandr.

In: Queueing Systems, Vol. 59, No. 1, 01.05.2008, p. 1-35.

Research output: Contribution to journalArticle

@article{3204838f306549d4a24de6a07d572fb1,
title = "Large deviations of queues sharing a randomly time-varying server",
abstract = "We consider a discrete-time model where multiple queues, each with its own exogenous arrival process, are served by a server whose capacity varies randomly and asynchronously with respect to different queues. This model is primarily motivated by the problem of efficient scheduling of transmissions of multiple data flows sharing a wireless channel. We address the following problem of controlling large deviations of the queues: find a scheduling rule, which is optimal in the sense of maximizing (Equation Presented), where Qi is the length of the i-th queue in a stationary regime, and ai >0 are parameters. Thus, we seek to maximize the minimum of the exponential decay rates of the tails of distributions of weighted queue lengths a iQi. We give a characterization of the upper bound on (0.1) under any scheduling rule, and of the lower bound on (0.1) under the exponential (EXP) rule. We prove that the two bounds match, thus proving optimality of the EXP rule. The EXP rule is very parsimonious in that it does not require any {"}pre-computation{"} of its parameters, and uses only current state of the queues and of the server. The EXP rule is not invariant with respect to scaling of the queues, which complicates its analysis in the large deviations regime. To overcome this, we introduce and prove a refined sample path large deviations principle, or refined Mogulskii theorem, which is of independent interest.",
keywords = "Dynamic scheduling, Exponential (EXP) rule, Local fluid limit, Quality of service, Queueing networks, Refined Mogulskii theorem, Sample path large deviations principle, Time-varying server",
author = "Aleksandr Stolyar",
year = "2008",
month = "5",
day = "1",
doi = "10.1007/s11134-008-9072-y",
language = "English (US)",
volume = "59",
pages = "1--35",
journal = "Queueing Systems",
issn = "0257-0130",
publisher = "Springer Netherlands",
number = "1",

}

TY - JOUR

T1 - Large deviations of queues sharing a randomly time-varying server

AU - Stolyar, Aleksandr

PY - 2008/5/1

Y1 - 2008/5/1

N2 - We consider a discrete-time model where multiple queues, each with its own exogenous arrival process, are served by a server whose capacity varies randomly and asynchronously with respect to different queues. This model is primarily motivated by the problem of efficient scheduling of transmissions of multiple data flows sharing a wireless channel. We address the following problem of controlling large deviations of the queues: find a scheduling rule, which is optimal in the sense of maximizing (Equation Presented), where Qi is the length of the i-th queue in a stationary regime, and ai >0 are parameters. Thus, we seek to maximize the minimum of the exponential decay rates of the tails of distributions of weighted queue lengths a iQi. We give a characterization of the upper bound on (0.1) under any scheduling rule, and of the lower bound on (0.1) under the exponential (EXP) rule. We prove that the two bounds match, thus proving optimality of the EXP rule. The EXP rule is very parsimonious in that it does not require any "pre-computation" of its parameters, and uses only current state of the queues and of the server. The EXP rule is not invariant with respect to scaling of the queues, which complicates its analysis in the large deviations regime. To overcome this, we introduce and prove a refined sample path large deviations principle, or refined Mogulskii theorem, which is of independent interest.

AB - We consider a discrete-time model where multiple queues, each with its own exogenous arrival process, are served by a server whose capacity varies randomly and asynchronously with respect to different queues. This model is primarily motivated by the problem of efficient scheduling of transmissions of multiple data flows sharing a wireless channel. We address the following problem of controlling large deviations of the queues: find a scheduling rule, which is optimal in the sense of maximizing (Equation Presented), where Qi is the length of the i-th queue in a stationary regime, and ai >0 are parameters. Thus, we seek to maximize the minimum of the exponential decay rates of the tails of distributions of weighted queue lengths a iQi. We give a characterization of the upper bound on (0.1) under any scheduling rule, and of the lower bound on (0.1) under the exponential (EXP) rule. We prove that the two bounds match, thus proving optimality of the EXP rule. The EXP rule is very parsimonious in that it does not require any "pre-computation" of its parameters, and uses only current state of the queues and of the server. The EXP rule is not invariant with respect to scaling of the queues, which complicates its analysis in the large deviations regime. To overcome this, we introduce and prove a refined sample path large deviations principle, or refined Mogulskii theorem, which is of independent interest.

KW - Dynamic scheduling

KW - Exponential (EXP) rule

KW - Local fluid limit

KW - Quality of service

KW - Queueing networks

KW - Refined Mogulskii theorem

KW - Sample path large deviations principle

KW - Time-varying server

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

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

U2 - 10.1007/s11134-008-9072-y

DO - 10.1007/s11134-008-9072-y

M3 - Article

AN - SCOPUS:45249119343

VL - 59

SP - 1

EP - 35

JO - Queueing Systems

JF - Queueing Systems

SN - 0257-0130

IS - 1

ER -