Pollaczek–Khinchine Service Variability

Worked Example

Let us calculate the performance metrics for a queue with a "Bursty zero four" service law, a mean service time m = 1, and an arrival rate λ = 0.5.

The "Bursty zero four" service time distribution is defined as taking value 0 with probability 3/4 and value 4m with probability 1/4.

1. Calculate the second moment of the service time, E[S²]:

   E[S^2] = (0^2 * 3/4) + ((4m)^2 * 1/4) = 16m^2 / 4 = 4m^2

   Substituting m = 1, we get E[S²] = 4(1)² = 4.
2. Calculate the traffic intensity, ρ:

   rho = lambda * m = 0.5 * 1 = 0.5

3. Calculate the mean queue wait time, W_q, using the P-K formula:

   W_q = (lambda * E[S^2]) / (2 * (1 - rho)) W_q = (0.5 * 4) / (2 * (1 - 0.5)) W_q = 2 / (2 * 0.5) = 2 / 1 = 2

4. Calculate the mean tagged sojourn time (total time in system):

   sojourn = W_q + m = 2 + 1 = 3

5. Calculate the mean queue length, L_q, using Little's Law:

   L_q = lambda * W_q = 0.5 * 2 = 1

The independently calculated visible results for this state are: Mean service = 1.0, Second service moment = 4.0, Traffic intensity = 0.5, Mean queue wait = 2.0, Mean tagged sojourn = 3.0, Mean queue length = 1.0, and Status = Stable.

Experiment

You can interactively explore the relationship between service variability and queue performance using the Pollaczek–Khinchine Service Variability module.

1. Set the Service law to "Exponential", the Mean service to "1", and the Arrival rate to "0.5". Observe that the mean queue wait is 1.0.
2. Change the Service law to "Two point zero two" while keeping the other settings identical. Notice that the mean queue wait is still 1.0, because both laws have the same mean and second moment E[S²] = 2m².
3. Change the Service law to "Bursty zero four". The mean queue wait jumps to 2.0, demonstrating how higher variance in service times (even with the same mean) drastically increases queueing delays.
4. Increase the Arrival rate to "1". The status changes to "No stationary mean" and metrics become unavailable since ρ = 1, indicating instability.

Limitations

The Pollaczek–Khinchine formula specifically applies to M/G/1 queues. It assumes a Poisson arrival process (the "M" part, memoryless). Applying it to queues with arbitrary non-Poisson arrivals will yield incorrect results. Additionally, it models a single server with an unlimited buffer and first-in-first-out (FIFO) discipline.

The system must be stable (ρ < 1) for a stationary finite mean to exist. When ρ ≥ 1, the queue grows unbounded over time, and the formula does not produce a valid steady-state probability or delay.

References

The following reference provides an in-depth derivation and analysis of the M/G/1 queue properties and the Pollaczek-Khinchine formula used in this interactive simulation.

• Stanford EE384X Handout 10 - Discusses the M/G/1 queue and derives the Pollaczek-Khinchine formula, supporting the calculations of mean delay and queue lengths presented.