A Server with General Service: The M/G/1 Queue

We consider a queue with Poisson arrivals of rate $\lambda$ . Since exponentially distributed service times are often unrealistic, we assume that service times are independent and identically distributed with general distribution $F_S(\cdot)$ . There is a single server, which serves jobs at unit speed.

The amount of work in the queue does not depend on the order in which jobs are served. By work, we mean the amount of time required for the server to empty the queue. By the PASTA property, the expected waiting time of an arriving job is determined by the expected work it sees in the queue.

However, when service times are not exponential, the service order matters when analysing the number of jobs in the system. We therefore assume that jobs are served in the order in which they arrive. This is called first-in first-out (FIFO) service, or equivalently first-come first-served (FCFS).

Pollaczek-Khintchine Formula

For an M/G/1 queue with $\rho<1$ under FIFO service, the expected number of jobs in the system is

$\displaystyle \mathbb E[N]=\rho+\frac{\rho^2+\lambda^2\mathbb V[S]}{2(1-\rho)}.$

The expected time spent in the system by an arriving job is

$\displaystyle \mathbb E[W]=\frac{1}{\mu}+\frac{\rho^2+\lambda\mu\mathbb V[S]}{2(\mu-\lambda)}.$

Both results follow from the probability-generating-function formula

$\displaystyle \mathbb E[z^N]=\frac{(1-z)(1-\rho)G_S(\lambda(1-z))}{G_S(\lambda(1-z))-z},$

where

$\displaystyle G_S(s):=\mathbb E[e^{-sS}]$

is the Laplace transform of $S$ .

Note that $\mathbb E[N]=\mathbb E[Q]+\rho$ , where $Q$ denotes the number of jobs waiting in the queue. This is because a job is in service with probability $\rho$ .

The generating-function identity above is called the Pollaczek-Khintchine formula. The corresponding formulas for the expected number of jobs and the expected waiting time are also often referred to as Pollaczek-Khintchine formulas.

A Quick Comparison of the M/M/1 and M/G/1 Queues

For the M/M/1 and M/G/1 queues, respectively,

$\displaystyle \mathbb E[N]=\frac{\rho}{1-\rho}\qquad\text{compared with}\qquad\mathbb E[N]=\rho+\frac{\rho^2+\lambda^2\mathbb V[S]}{2(1-\rho)}.$

The variance of the service time therefore affects the expected number of jobs in the system. This is intuitive: more predictable service times tend to synchronize the system better and reduce congestion.

Proof of the Pollaczek-Khintchine Formula

We first prove the formulas for the expected number of jobs and the expected waiting time directly. We then prove the probability-generating-function formula.

Proof

Part 1. For $\rho<1$ , the proportion of time for which the server is busy is $\rho$ . Let $W^0$ denote the waiting time of an arriving job before its own service begins. By the PASTA property,

$\displaystyle \mathbb E[W^0]=\mathbb E[Q]\mathbb E[S]+\rho\mathbb E[R],$

where $Q$ is the number of jobs waiting in the queue and $R$ is the residual service time of the job currently in service. Thus, $Q=(N-1)_+$ .

The term $\mathbb E[Q]\mathbb E[S]$ is the expected amount of work waiting in the queue. In particular,

$\displaystyle \mathbb E\left[\sum_{k=1}^{Q}S_k\right]=\mathbb E[Q]\mathbb E[S].$

By Little’s Law,

$\displaystyle \mathbb E[Q]=\lambda\mathbb E[W^0].$

From the residual-service formula,

$\displaystyle \mathbb E[R]=\frac{\mathbb E[S^2]}{2\mathbb E[S]}.$

Combining these identities gives

$\displaystyle \mathbb E[W^0]=\rho\mathbb E[W^0]+\rho\frac{\mathbb E[S^2]}{2\mathbb E[S]}.$

Therefore,

$\displaystyle (1-\rho)\mathbb E[W^0]=\rho\frac{\mathbb E[S^2]}{2\mathbb E[S]},$

and hence

$\displaystyle \mathbb E[W^0]=\frac{\rho}{2(1-\rho)}\frac{\mathbb E[S^2]}{\mathbb E[S]}=\frac{\lambda\mathbb E[S^2]}{2(1-\rho)}.$

Using $\mathbb E[S^2]=\mathbb V[S]+\mu^{-2}$ , we obtain

$\displaystyle \mathbb E[W^0]=\frac{\lambda\mu}{\mu-\lambda}\frac{\mathbb V[S]}{2}+\frac{\rho^2}{2(\mu-\lambda)}.$

Including the service time of the arriving job gives

$\displaystyle \mathbb E[W]=\frac{1}{\mu}+\frac{\rho^2+\lambda\mu\mathbb V[S]}{2(\mu-\lambda)}.$

Applying Little’s Law to the total number of jobs in the system gives

$\displaystyle \mathbb E[N]=\lambda\mathbb E[W]=\rho+\frac{\rho^2+\lambda^2\mathbb V[S]}{2(1-\rho)}.$

Part 2. We now prove the probability-generating-function formula. Let $N$ be the number of jobs in the system immediately after a departure in stationarity, let $N'$ be the number immediately after the next departure, and let $A$ be the number of arrivals during the service time of the next job served.

These random variables satisfy

$\displaystyle N'=N+A-\mathbb I_{\{N>0\}},\qquad N'\overset{\mathcal D}{=}N.$

Since $N$ and $A$ are independent,

$\displaystyle \mathbb E[z^N]=\mathbb E[z^{N'}]=\mathbb E\!\left[z^{N-\mathbb I_{\{N>0\}}}\right]\mathbb E[z^A].$

If $A(s)$ is Poisson with mean $\lambda s$ , then

$\displaystyle \mathbb E[z^{A(s)}]=e^{\lambda s(z-1)}.$

Conditioning on the service time gives

$\displaystyle \mathbb E[z^A]=\int_0^\infty e^{\lambda s(z-1)}\,dF_S(s)=G_S(\lambda(1-z)).$

Also, writing $\pi_k=\mathbb P(N=k)$ ,

$\displaystyle \mathbb E\!\left[z^{N-\mathbb I_{\{N>0\}}}\right]=\pi_0+z^{-1}\sum_{k=1}^{\infty}\pi_kz^k=\pi_0(1-z^{-1})+z^{-1}\mathbb E[z^N].$

Since the server is busy for a fraction $\rho$ of the time, the stationary probability that the system is empty is $\pi_0=1-\rho$ . Substitution gives

$\displaystyle \mathbb E[z^N]=\left\{\pi_0(1-z^{-1})+z^{-1}\mathbb E[z^N]\right\}G_S(\lambda(1-z)).$

Rearranging,

$\displaystyle \mathbb E[z^N]=\frac{(1-z)(1-\rho)G_S(\lambda(1-z))}{G_S(\lambda(1-z))-z}.$

This is the Pollaczek-Khintchine probability-generating-function formula.

The mean formulas can also be recovered by differentiating this expression and evaluating the resulting limit as $z\to1$ . This calculation requires L’Hôpital’s rule.

□

Pollaczek-Khintchine Formula

A Quick Comparison of the M/M/1 and M/G/1 Queues

Proof of the Pollaczek-Khintchine Formula

Proof

Share this:

Leave a comment Cancel reply