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

DOI10.1007/S11134-006-8767-1zbMATH Open1107.60061arXivmath/0505450OpenAlexW2134936565MaRDI QIDQ854992FDOQ854992

Authors: Misja Nuyens, Bert Zwart 

Publication date: 20 December 2006

Published in: Queueing Systems (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

large deviationssojourn timeshortest remaining processing timepriority queueBusy periodlight-tailed service times

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

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

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)