Heavy traffic analysis for EDF queues with reneging
Open Access
- 1 April 2011
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 21 (2)
- https://doi.org/10.1214/10-aap681
Abstract
This paper presents a heavy-traffic analysis of the behavior of a single-server queue under an Earliest-Deadline-First (EDF) scheduling policy in which customers have deadlines and are served only until their deadlines elapse. The performance of the system is measured by the fraction of reneged work (the residual work lost due to elapsed deadlines) which is shown to be minimized by the EDF policy. The evolution of the lead time distribution of customers in queue is described by a measure-valued process. The heavy traffic limit of this (properly scaled) process is shown to be a deterministic function of the limit of the scaled workload process which, in turn, is identified to be a doubly reflected Brownian motion. This paper complements previous work by Doytchinov, Lehoczky and Shreve on the EDF discipline in which customers are served to completion even after their deadlines elapse. The fraction of reneged work in a heavily loaded system and the fraction of late work in the corresponding system without reneging are compared using explicit formulas based on the heavy traffic approximations. The formulas are validated by simulation results.Comment: Published in at http://dx.doi.org/10.1214/10-AAP681 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.orgKeywords
This publication has 31 references indexed in Scilit:
- Law of large numbers limits for many-server queuesThe Annals of Applied Probability, 2011
- Heavy traffic limit for a processor sharing queue with soft deadlinesThe Annals of Applied Probability, 2007
- Accuracy of state space collapse for earliest-deadline-first queuesThe Annals of Applied Probability, 2006
- Validity of heavy traffic steady-state approximations in generalized Jackson networksThe Annals of Applied Probability, 2006
- Earliest-deadline-first service in heavy-traffic acyclic networksThe Annals of Applied Probability, 2004
- Diffusion approximation for a processor sharing queue in heavy trafficThe Annals of Applied Probability, 2004
- Fluid and heavy traffic diffusion limits for a generalized processor sharing modelThe Annals of Applied Probability, 2003
- Convex duality and the Skorokhod Problem. IProbability Theory and Related Fields, 1999
- Weak convergence theorems for priority queues: preemptive-resume disciplineJournal of Applied Probability, 1971
- Multiple channel queues in heavy traffic. IAdvances in Applied Probability, 1970