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 \(\hat{w}_{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 [image] within a large class of work conserving disciplines.
Publié le : 2001-02-14
Classification:
queueing theory,
queueing delay,
large deviations,
rate function,
optimality,
fluid limit,
control,
scheduling,
quality of service,
(Qos),
earliest deadline first,
(EDF),
LWDF,
60F10,
90B12,
60K25
@article{998926986,
author = {Stolyar, Alexander L. and Ramanan, Kavita},
title = {Largest Weighted Delay First Scheduling: Large Deviations and Optimality},
journal = {Ann. Appl. Probab.},
volume = {11},
number = {2},
year = {2001},
pages = { 1-48},
language = {en},
url = {http://dml.mathdoc.fr/item/998926986}
}
Stolyar, Alexander L.; Ramanan, Kavita. Largest Weighted Delay First Scheduling: Large Deviations and Optimality. Ann. Appl. Probab., Tome 11 (2001) no. 2, pp. 1-48. http://gdmltest.u-ga.fr/item/998926986/