Large deviations of queues under qos scheduling algorithms

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider a model where multiple queues are served by a server whose capacity varies randomly and asynchronously with respect to different queues. The problem is to optimally control large deviations of the queues in the following sense: find a scheduling rule maximizing min i h lim n!1 1 n log P (aiQi n) i , (1) where Qi is the length of 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 aiQi. We give a characterization of the upper bound on (1) under any scheduling rule, and of the lower bound on (1) under the exponential (EXP) rule. For the case of two queues, we prove that the two bounds match, thus proving optimality of EXP rule in this case. The EXP rule is not asymptotically invariant with respect to scaling of the queues, which complicates its analysis in large deviations regime. To overcome this, we introduce and prove a refined sample path large deviations principle, or refined Mogulsky theorem, which is of independent interest.

Original languageEnglish (US)
Title of host publication44th Annual Allerton Conference on Communication, Control, and Computing 2006
PublisherUniversity of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
Pages96-105
Number of pages10
ISBN (Electronic)9781604237924
StatePublished - Jan 1 2006
Externally publishedYes
Event44th Annual Allerton Conference on Communication, Control, and Computing 2006 - Monticello, United States
Duration: Sep 27 2006Sep 29 2006

Publication series

Name44th Annual Allerton Conference on Communication, Control, and Computing 2006
Volume1

Other

Other44th Annual Allerton Conference on Communication, Control, and Computing 2006
CountryUnited States
CityMonticello
Period9/27/069/29/06

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Large deviations of queues under qos scheduling algorithms'. Together they form a unique fingerprint.

Cite this