Little’s Law

Little’s Law is such a fundamental result in queueing theory that it is called a “law.” It states that the average number of jobs in a system is equal to the average arrival rate multiplied by the average time spent in the system. It applies to any system involving waiting, provided that the system is not overloaded.

Little’s Law

For a queueing system in equilibrium,

\displaystyle \bar N = \lambda \bar W

where

\bar N is the mean number of jobs in the system,

\lambda is the mean arrival rate, and

\bar W is the mean time spent in the system.

We use the letter W to denote the time spent in the system, also called the sojourn time.

Proof

Consider the figure below. Here, A_i denotes the time of the ith arrival, and W_i denotes the time that job i spends in the system. Thus, A_i+W_i is the time at which the ith job leaves the system.

Suppose for now that the system is empty initially and is again empty at time T. Let \alpha(T) denote the number of arrivals by time T.

The key idea in the proof of Little’s Law.

The average number of jobs in the system can be found from the area under the curve showing the number of jobs present over time. This area is also equal to the sum of the areas of the rectangles between each job’s arrival and departure. Therefore,

\displaystyle \frac{1}{T}\int_0^T N(t)\,dt = \frac{1}{T}\sum_{i=1}^{\alpha(T)}W_i = \frac{\alpha(T)}{T}\cdot \frac{1}{\alpha(T)}\sum_{i=1}^{\alpha(T)}W_i

This identity expresses the time-average number of jobs in the system as the arrival rate multiplied by the average time spent in the system.

Letting T\to\infty gives

\displaystyle \bar N=\lambda\bar W

Technical point. We assumed that the system is empty at times 0 and T. In general, some jobs may be present at either endpoint. However, in equilibrium, the resulting boundary terms do not grow proportionally with T. Their contribution therefore becomes negligible as T\to\infty.

□

Leave a comment