Control of end-to-end delay tails in a multiclass network: LWDF discipline optimality

Research output: Contribution to journalArticle

Abstract

We consider a multiclass queueing network with N customer classes, each having an arbitrary fixed route through the network. (Thus, the network is not necessarily feedforward.) We show that the largest weighted delay first (LWDF) discipline is an optimal scheduling discipline in the network in the following sense. Let w i be the (random) instantaneous largest end-to-end delay of a class i customer in the network in stationary regime. For any set of positive constants α 1,...,α N, the LWDF discipline associated with this set maximizes (among all disciplines) the quantity (1) min i=1,...,N1 lim n→∞ -1/n log P (w i > n)] = lim n→∞ -1/n log P (r>n), where r =̇ max i w ii is the maximal weighted delay in the network. [This result is a generalization of the single-server result proved by A. L. Stolyar and K. Ramanan in Ann. Appl. Probab. 11 (2001) 1-48.] As the key element of the proof, we establish the following critical node property: In a LWDF network, there exists a most likely path to build large r, which is a most likely path to do so in one of the network nodes in isolation. Such a most likely path has a very simple structure: its parameters [and the optimal value of (1)] can be computed by solving a finite-dimensional optimization problem for each network node.

Original languageEnglish (US)
Pages (from-to)1151-1206
Number of pages56
JournalAnnals of Applied Probability
Volume13
Issue number3
DOIs
StatePublished - Aug 1 2003

Keywords

  • End-to-end delay
  • Fluid limit
  • Large deviations
  • Queueing networks
  • Scheduling

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Control of end-to-end delay tails in a multiclass network: LWDF discipline optimality'. Together they form a unique fingerprint.

  • Cite this