Largest weighted delay first scheduling: Large deviations and optimality

Alexander L. Stolyar, Kavita Ramanan

Research output: Contribution to journalArticle

Abstract

We consider a single server system with N input flows. We assume that each flow has stationary increments and satisfies a sample path large deviation principle, and that the system is stable. We introduce the largest weighted delay first (LWDF) queueing discipline associated with any given weight vector α = (α1, . . ., αN). We show that under the LWDF discipline the sequence of scaled stationary distributions of the delay ŵi of each flow satisfies a large deviation principle with the rate function given by a finite-dimensional optimization problem. We also prove that the LWDF discipline is optimal in the sense that it maximizes the quantity mini=1, ..., Ni limn→∞ -1/n log P(ŵi > n)], within a large class of work conserving disciplines.

Original languageEnglish (US)
Pages (from-to)1-48
Number of pages48
JournalAnnals of Applied Probability
Volume11
Issue number1
DOIs
StatePublished - Feb 2001

    Fingerprint

Keywords

  • Control
  • Earliest deadline first (EDF)
  • Fluid limit
  • LWDF
  • Large deviations
  • Optimality
  • Quality of service (QoS)
  • Queueing delay
  • Queueing theory
  • Rate function
  • Scheduling

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Cite this