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

DOI10.1214/105051605000000809zbMATH Open1129.60084arXivmath/0607056OpenAlexW1985042389MaRDI QIDQ997940FDOQ997940

John P. Lehoczky, Steven Shreve, Łukasz Kruk

Publication date: 8 August 2007

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Convergence Criteria for Multiparameter Stochastic Processes and Some Applications
• Title not available (Why is that?)
• Stochastic-Process Limits
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiple channel queues in heavy traffic. I
• Earliest-deadline-first service in heavy-traffic acyclic networks.
• Title not available (Why is that?)
• Real-time queues in heavy traffic with earliest-deadline-first queue discipline
• The Equivalence of Functional Central Limit Theorems for Counting Processes and Associated Partial Sums
• Multiple-input heavy-traffic real-time queues.

Cited In (9)

• Fluid Limits for Multiple-Input Shortest Remaining Processing Time Queues
• 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
• Stability of linear EDF networks with resource sharing

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)