Accuracy of state space collapse for earliest-deadline-first queues

DOI10.1214/105051605000000809MaRDI QIDQ997940zbMATH OpenOpenAlexFDO

Authors Łukasz Kruk, John P. Lehoczky, Steven Shreve

Publication date 8 August 2007

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0607056

zbMATH Keywords

Brownian motionperformance evaluationqueueing theoryrandom measures

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Brownian motion (60J65) Random measures (60G57)

Abstract: This paper presents a second-order heavy traffic analysis of a single server queue that processes customers having deadlines using the earliest-deadline-first scheduling policy. For such systems, referred to as real-time queueing systems, performance is measured by the fraction of customers who meet their deadline, rather than more traditional performance measures, such as customer delay, queue length or server utilization. To model such systems, one must keep track of customer lead times (the time remaining until a customer deadline elapses) or equivalent information. This paper reviews the earlier heavy traffic analysis of such systems that provided approximations to the system's behavior. The main result of this paper is the development of a second-order analysis that gives the accuracy of the approximations and the rate of convergence of the sequence of real-time queueing systems to its heavy traffic limit.

Recommendations

• Real-time queues in heavy traffic with earliest-deadline-first queue discipline
• Diffusion approximation for a \(G/G/1\) EDF queue with unbounded lead times
• Heavy traffic analysis for EDF queues with reneging
• Earliest-deadline-first service in heavy-traffic acyclic networks.
• Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits

Cites work

• scientific article; zbMATH DE number 3125504 (Why is no real title available?)
• scientific article; zbMATH DE number 5604036 (Why is no real title available?)
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 4060392 (Why is no real title available?)
• scientific article; zbMATH DE number 192908 (Why is no real title available?)
• scientific article; zbMATH DE number 1196650 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• Convergence Criteria for Multiparameter Stochastic Processes and Some Applications
• Earliest-deadline-first service in heavy-traffic acyclic networks.
• Multiple channel queues in heavy traffic. I
• Multiple-input heavy-traffic real-time queues.
• Real-time queues in heavy traffic with earliest-deadline-first queue discipline
• Stochastic-Process Limits
• The Equivalence of Functional Central Limit Theorems for Counting Processes and Associated Partial Sums

Cited in

(10)

• Real-time queues in heavy traffic with earliest-deadline-first queue discipline
• An explicit formula for the Skorokhod map on \([0,a]\)
• Heavy traffic limit for a processor sharing queue with soft deadlines
• Personalized queues: the customer view, via a fluid model of serving least-patient first
• Multiple-input heavy-traffic real-time queues.
• A single server queue in a hard-real-time environment
• Heavy traffic analysis for EDF queues with reneging
• Fluid limits for multiple-input shortest remaining processing time queues
• Stability of linear EDF networks with resource sharing
• Closed-form approximations for the URLLC capacity using \(G/G/s\) queues

This page was built for publication: Accuracy of state space collapse for earliest-deadline-first queues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q997940)