Representing Workloads in GI/G/1 Queues
through the Preemptive-Resume LIFO Queue Discipline
We give in this paper a detailed sample-average analysis of GI/G/1 queues
with the preemptive-resume LIFO (last-in-first-out) queue discipline: We
study the long-run "state" behavior of the system by averaging over
arrival epochs, departure epochs, as well as time, and obtain relations that
express the resulting averages in terms of basic characteristics within busy
cycles. These relations, together with the fact that the preemptive-resume
LIFO queue discipline is work-conserving, imply new representations for both
"actual" and "virtual" delays in standard GI/G/1 queues with the FIFO
(first-in-first-out) queue discipline. The arguments by which our results
are obtained unveil the underlying structural "explanations" for many
classical and somewhat mysterious results relating to queue lengths and/or
delays in standard GI/G/1 queues, including the well-known Benes's
formula for the delay distribution in M/G/1. We also discuss how to extend
our results to settings more general than GI/G/1.