A Little Triplet

Little's law appears in various guises in performance analysis. It was known to Agner Erlang (the father of queueing theory) in 1909 to be intuitively correct but was not proven mathematically until 1961 by John Little. Even though you experience it all the time, queueing is not such a trivial phenomenon as it may seem. In the subsequent discussion, I'll show you that there is actually a triplet of such laws, where each version refers to a slightly different aspect of queueing. Although they have a common general form, the less than obvious interpretation of each version is handy to know for solving almost any problem in performance analysis.

To see the Little's law triplet, consider the line of customers at the grocery store checkout lane shown in Figure 1. Following the usual queueing theory convention, the queue includes not only the customers waiting but also the customer currently in service.

Figure 1. Checkout lane decomposed into its space and time components

As an aside, it is useful to keep in mind that there are only three types of performance metric:

1. Time $T$ (the fundamental performance metric), e.g., minutes
2. Count or a number $N$ (no formal dimensions), e.g., transactions
3. Rate $N/T$ (inverse time dimension), e.g., transactions per minute

From this standpoint, Little's law has the simple general form \begin{equation} N = \dfrac{N}{T} ~\times ~T \label{eqn:dims} \end{equation} which says: a rate (type- C metric) multiplied by time (type- A metric) produces a number (type- B metric), because the $T$s cancel out. The three metric types (A,B,C) should not be confused with the three forms of Little's law being discussed here. That's just a coincidence because good things often come in threes. :-)

Shoppers in Figure 1 arrive from the left into the checkout lane with arrival rate $\lambda$ customers per minute, for example. Since $\lambda$ is a rate, it must be a type-C metric. The total time they spend at the checkout is the sum of their waiting time, $W$ (due to the customers already ahead of them), and their service time, $S$ (the average time it takes to ring up their groceries). This time is called their residence time \begin{equation} R = W + S \label{eqn:Rtime} \end{equation} which is a type-A metric. Equation \eqref{eqn:Rtime} gives us the temporal view of the queue, i.e., the time components of the system. After paying the cashier each customer departs to the right and leaves the system.

Example

For the purpose of simple numerical calculations, let's assume the following average values for the queueing parameters: \begin{align} \lambda &= 0.5 ~\text{customer per minute} \label{eqn:arate}\\ S &= 1.0 ~\text{minute} \label{eqn:Smins}\\ W &= 1.0 ~\text{minute} \label{eqn:Wmins} \end{align} From eqn.\eqref{eqn:Rtime} it follows that \begin{equation} R = 1 + 1 = 2 ~\text{minutes} \label{eqn:Rmins} \end{equation} The residence time tells us that the average time a customer can expect to spend getting through the checkout lane is two minutes.

Little's Law Version 1

The corresponding average queue length, $Q$, in Figure 1 tells us how much space customers are expected to occupy and it can be determined from this version of Little's law \begin{equation} Q = \lambda ~\times ~R \label{eqn:LLQ} \end{equation} Clearly, \eqref{eqn:LLQ} has the form \eqref{eqn:dims}: a rate multiplied by a time. $Q$ is a number (an average value), so it's a type-B metric. Equation \eqref{eqn:LLQ} is probably the most common form of Little's law arising in performance calculations.

Example

Using the values in \eqref{eqn:arate} and \eqref{eqn:Rmins} it follows that \begin{equation} Q = \dfrac{1}{2} \times 2 = 1 ~\text{customer} \label{eqn:LLQval} \end{equation} The average queue length is 1 customer (i.e., both waiting and in service). How a single customer can be simultaneously waiting and in service will become clearer shortly. In the meantime, that's count one for Little.

Little's Law Version 2

Figure 1 reveals that there's another way to express the queue length, $Q$. Just as the residence time \eqref{eqn:Rtime} can be decomposed into the waiting time ($W$) and the service time ($S$), we can also decompose the queue length into the length of the waiting line, $L$, and the average number of customers in service: \begin{equation} Q = L + m \rho \label{eqn:Qdecomp} \end{equation} Equation \eqref{eqn:Qdecomp} gives us the spatial view of the queue, i.e., the occupancy components of the system. Here, $m$ is the number of service facilities and $m\rho$ is the average occupancy of those servers. In Figure 1 $m = 1$, since there is only a single cashier, and $0 \leq \rho < 1$ is the fraction of time for which the cashier is busy (AKA the utilization of the cashier). The value $\rho = 1$ would correspond to 100% busy. Clearly, the cashier can't be busier than 100% of the time.

Equation \eqref{eqn:LLQ} can be written in another way by substituting \eqref{eqn:Qdecomp} and \eqref{eqn:Rtime} respectively into the left-hand and right-hand sides to produce \begin{equation} L + m \rho = \lambda W + \lambda S \label{eqn:decompAll} \end{equation} The first terms on each side of \eqref{eqn:decompAll} can be equated separately as \begin{equation} L = \lambda ~\times ~W \label{eqn:LLW} \end{equation} Once again \eqref{eqn:LLW} has the form \eqref{eqn:dims}. You can think of $L$ as an estimate of buffer size. Remarkably, this is the form of Little's law that appears in the title of John Little's 1961 paper.

Example

Using the values in \eqref{eqn:arate} and \eqref{eqn:Wmins} it follows that \begin{equation} L = \dfrac{1}{2} \times 1 = \dfrac{1}{2} ~\text{customer} \label{eqn:LLLval} \end{equation} Half a customer may look strange but remember, these are average values. That's count two for Little.

Little's Law Version 3

Repeating the previous step for the corresponding second terms in \eqref{eqn:decompAll}, we have \begin{equation} \rho = \dfrac{\lambda ~\times ~S}{m} \label{eqn:LLS} \end{equation} Again, \eqref{eqn:LLS} has the form \eqref{eqn:dims}: division by the constant $m$ doesn't alter anything. In Figure 1, $m=1$ since there is a single server (the cashier).

This version of Little's law is often referred to as the Utilization law, but that doesn't help to make useful connections between performance metrics. It is common practice to use a notation like $U = m \rho$ to represent the total utilization of $m$-servers such that $0 \leq U < m$.

Example

Using the values in \eqref{eqn:arate} and \eqref{eqn:Smins} it follows that the total utilization is \begin{equation} U = \dfrac{1}{2} \times 1 = 50\% \end{equation} Notice also that \begin{equation} Q = L + U = \dfrac{1}{2} + \dfrac{1}{2} = 1 ~\text{customer} \end{equation} in agreement with the Little's law calculation in \eqref{eqn:LLQval}. And that's count three for Little.

Triplet of Interpretations

The Little's law triplet can be summarized as follows:

\begin{align*} Q &= \lambda \, \mathbf{R}: \; \text{average number of customers in Residence (R)}\\ L &= \lambda \, \mathbf{W}: \; \text{average number of customers in Waiting (W)}\\ U &= \lambda \, \mathbf{S}: \; \text{average number of customers in Service (S)} \end{align*} where all three equations are consistent with \eqref{eqn:dims}. Knowing the word interpretation of these equational forms of Little's law can often provide the key to solving an otherwise obscure performance problem.