Control of end-to-end delay tails in a multiclass network: LWDF discipline optimality
type: Item
instance of: scholarly article
title: Control of end-to-end delay tails in a multiclass network: LWDF discipline optimality
zbMATH Open document ID: 1044.60090
published in: The Annals of Applied Probability
publication date: 2004-03-21T00:00:00Z
review text: One considers the queueing network control problem to find a scheduling discipline such that \( P\{w_i>T_i\}\leq \delta _i\), \(i=1,\dots ,N, \) where \(N\) is the number of traffic flows, \(w_i\) is the steady-state end-to-end delay for flow \(i\), \(T_i>0\) is a predefined delay threshold and \(\delta _i\) is the maximal acceptable deadline violation probability. It has been shown that the largest weighted delay first (LWDF) discipline is optimal to satisfy these requirements in the large deviation and heavy traffic asymptotic regimes in single-server systems. The LWDF discipline picks up for service the customer \(c^*=\text{arg}\max_c W(c)/\alpha _{i(c)},\) where the maximum is taken over the customers \(c\) available for service, \(W(c)\) is the customer's current delay and \(i(c)\) is its class. The above mentioned scheduling discipline is replaced by asymptotic ``tail'' conditions, and the satisfaction of these conditions is equivalent to solving an optimization problem. The main result of the paper: the LWDF discipline (with parameters \(\alpha _i\)) is the optimal solution of this optimization problem in a queueing network of arbitrary topology. The paper is a generalization of \textit{A. L. Stolyar's} and \textit{K. Ramanan's} result for single-server system [Ann. Appl. Probab. 11, No. 1, 1--48 (2001; Zbl 1024.60012)].
Mathematics Subject Classification ID: 60K25
Mathematics Subject Classification ID: 60F10
Mathematics Subject Classification ID: 90B22
Mathematics Subject Classification ID: 90B15
zbMATH DE Number: 2061213
zbMATH Keywords: queueing networks
zbMATH Keywords: scheduling
zbMATH Keywords: end-to-end delay
author: Alexander L. Stolyar
reviewed by: László Lakatos
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1060202838
OpenAlex ID: W2088792715
cites work: Q4952650
cites work: Asymptotic buffer overflow probabilities in multiclass multiplexers: an optimal control approach
cites work: Q5560061
cites work: Stability of earliest-due-date, first-served queueing networks
cites work: Fluid approximations and stability of multiclass queueing networks: Work-conserving disciplines
cites work: On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
cites work: Stability and convergence of moments for multiclass queueing networks via fluid limit models
cites work: Q4391441
cites work: Real-time queues in heavy traffic with earliest-deadline-first queue discipline
cites work: Optimal multiplexing on a single link: delay and buffer requirements
cites work: Q5602045
cites work: Q4360317
cites work: Markov chains and stochastic stability
cites work: Stability of Markovian processes II: continuous-time processes and sampled chains
cites work: Stability of Markovian processes III: Foster–Lyapunov criteria for continuous-time processes
cites work: State-dependent criteria for convergence of Markov chains
cites work: General Irreducible Markov Chains and Non-Negative Operators
cites work: A multiclass queue in heavy traffic with throughput time constraints: Asymptotically optimal dynamic controls
cites work: Large deviation properties of data streams that share a buffer
cites work: Ergodicity of stochastic processes describing the operation of open queueing networks
cites work: Q4865050
cites work: Q3239624
cites work: Q3840956
cites work: Largest weighted delay first scheduling: Large deviations and optimality
cites work: Due-Date Scheduling: Asymptotic Optimality of Generalized Longest Queue and Generalized Largest Delay Rules
DOI: 10.1214/AOAP/1060202838
Recommended article: Largest weighted delay first scheduling: Large deviations and optimality
Recommended article: Optimal QoS control of interacting service stations
Recommended article: Scheduling in multiclass networks with deterministic service times
Recommended article: A linear programming problem in separable closed queueing networks
Recommended article: SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATES
Recommended article: A multiclass queue in heavy traffic with throughput time constraints: Asymptotically optimal dynamic controls
Recommended article: Q5753341
description: scientific article; zbMATH DE number 2061213