Representing workloads in GI/G/1 queues through the preemptive-resume LIFO queue discipline (Q1107224)

We give 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 Beneš's formula for the delay distribution in M/G/1. We also discuss how to extend our results to settings more general then GI/G/1.