Renewal Processes and Residual Service

The assumption of exponential inter-arrival times is often reasonable. The Poisson process provides a useful model for many real-world systems when arrivals are drawn independently from a large population. However, the assumption of exponential service times is usually less realistic.

Exponential service times are a useful starting point because the resulting models can often be analysed using the well-developed theory of continuous-time Markov chains. These models allow us to understand the main features of a queueing system and build intuition before introducing more realistic service-time distributions.

We now consider service times drawn from a general distribution.

A Server with an Infinite Backlog

Consider a server that processes jobs at unit speed and always has another job waiting. Suppose that the service times are independent and identically distributed copies of a random variable S. We assume that S has finite mean and variance, and denote its cumulative distribution function by F_S(x).

Infinite backlog.

The residual service time R is the amount of time remaining until the job currently in service is completed.

Suppose that the server has been running for a long time and we observe it at a randomly chosen time. A key observation is:

The remaining service time is not distributed in the same way as S, and it is not necessarily smaller. We are more likely to observe a long job in service than a short job.

More specifically:

The probability of observing a job of size s is proportional to its size, and conditional on observing a job of size s, the amount of service already received is uniformly distributed on [0,s].

Let Z denote the total size of the job in service. Its size-biased distribution satisfies

\displaystyle dF_Z(z)=\frac{z}{\mathbb E[S]}\,dF_S(z).

Therefore,

\displaystyle F_Z(z)=\mathbb P(Z\leq z)=\frac{1}{\mathbb E[S]}\int_0^z s\,dF_S(s).

Conditional on Z=z, the residual service time is uniformly distributed on [0,z]. Hence,

\displaystyle dF_R(r)=\int_r^\infty \frac{1}{z}\,dF_Z(z)\,dr=\frac{1}{\mathbb E[S]}\int_r^\infty dF_S(z)\,dr=\frac{\mathbb P(S\geq r)}{\mathbb E[S]}\,dr.

The expected residual service time is therefore

\displaystyle \mathbb E[R]=\frac{1}{\mathbb E[S]}\int_0^\infty r\,\mathbb P(S\geq r)\,dr.

Using the tail-integral identity,

\displaystyle \mathbb E[R]=\frac{1}{\mathbb E[S]}\int_0^\infty\int_0^\infty r\,\mathbb I_{\{s\geq r\}}\,dr\,dF_S(s)=\frac{1}{\mathbb E[S]}\int_0^\infty\frac{s^2}{2}\,dF_S(s)=\frac{\mathbb E[S^2]}{2\mathbb E[S]}.

Thus,

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

The expected residual service time depends on the second moment, and therefore on the variance, of the service-time distribution. This dependence on service-time variability is an important feature of queues with general job sizes.

Leave a comment