A large-deviations analysis of the GI/GI/1 SRPT queue

DOI10.1007/S11134-006-8767-1MaRDI QIDQ854992zbMATH OpenOpenAlexFDO

Authors Misja Nuyens, Bert Zwart

Publication date 20 December 2006

Published in Queueing Systems (Search for Journal in Brave)

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

zbMATH Keywords

Busy periodlarge deviationslight-tailed service timespriority queueshortest remaining processing timesojourn time

Mathematics Subject Classification ID

Large deviations (60F10) Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22)

Abstract: We consider a GI/GI/1 queue with the shortest remaining processing time discipline (SRPT) and light-tailed service times. Our interest is focused on the tail behavior of the sojourn-time distribution. We obtain a general expression for its large-deviations decay rate. The value of this decay rate critically depends on whether there is mass in the endpoint of the service-time distribution or not. An auxiliary priority queue, for which we obtain some new results, plays an important role in our analysis. We apply our SRPT-results to compare SRPT with FIFO from a large-deviations point of view.

Review text

For the GI/GI/1 queue with light-tailed service times, the authors obtain expressions for the logarithmic decay rate of the tail of the workload, the busy period, the waiting time and sojourn time of low-priority customers in a priority queue, and the sojourn time under the (preemptive and non-preemptive) SRPT discipline. For the sojourn time under SRPT, it turns out that there are three different regimes, namely for service times with no mass, with some mass and with all mass in the endpoint of the service time distribution. In the first case the decay rate is minimal among all work-conserving disciplines, in the last case it is maximal, but if there is some mass in the endpoint, then the decay rate lies strictly in between these two. The large-deviations results for the unconditional sojourn times suggest that a switch from FIFO to SRPT is not advisable.

Recommendations

• Large deviations of sojourn times in processor sharing queues
• Queues with equally heavy sojourn time and service requirement distributions
• Large deviations of the waiting time in the GI/G/1 queue with random order service
• Diffusion limits for SRPT and LRPT queues via EDF approximations
• On the average sojourn time under \(M/M/1/\)SRPT

Cites work

• Applied Probability and Queues
• Asymptotics for M/G/1 low-priority waiting-time tail probabilities
• Big queues.
• Calculation of the Laplace transform of the length of the busy period for the M/G/1 queue via martingales
• Handling load with less stress
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 1460450 (Why is no real title available?)
• scientific article; zbMATH DE number 1466126 (Why is no real title available?)
• scientific article; zbMATH DE number 3206642 (Why is no real title available?)
• Large deviations of sojourn times in processor sharing queues
• Largest weighted delay first scheduling: Large deviations and optimality
• Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline
• Logarithmic asymptotics for steady-state tail probabilities in a single-server queue
• On the average sojourn time under \(M/M/1/\)SRPT
• On the exact asymptotics of the busy period in GI/G/1 queues
• Sample-path large deviations for tandem and priority queues with Gaussian inputs
• SOJOURN TIME TAILS IN THE M/D/1 PROCESSOR SHARING QUEUE
• SOJOURN TIMES IN THE M/G/1 FB QUEUE WITH LIGHT-TAILED SERVICE TIMES

Cited in

(17)

• Local edge minimality of SRPT networks with shared resources
• Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits
• Fluid limits for shortest job first with aging
• Approximately optimal scheduling of an \(\mathrm{M}/\mathrm{G}/1\) queue with heavy tails
• Sojourn time asymptotics in processor sharing queues with varying service rate
• Large deviations of sojourn times in processor sharing queues
• Sojourn time asymptotics in processor-sharing queues
• Note on the GI/GI/1 queue with LCFS-PR observed at arbitrary times
• Fluid limits for multiple-input shortest remaining processing time queues
• Monotonicity in the Limited Processor-Sharing Queue
• Invariance of fluid limits for the shortest remaining processing time and shortest job first policies
• The Map/G//1/$\infty$ Queue with SRPT Service Discipline
• Diffusion limits for shortest remaining processing time queues
• Large deviations: a survey on its theory and applications
• Heavy-tailed limits for medium size jobs and comparison scheduling
• Tail behavior of conditional sojourn times in processor-sharing queues
• Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling

This page was built for publication: A large-deviations analysis of the GI/GI/1 SRPT queue

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