Skip to content
Telecom Networks

Queueing theory: Little's law, the M/M/1 queue and statistical multiplexing

Utilisation, Little's law with proof, the M/M/1 queue with distribution and delay proved, growth of delay with load, a numerical example, the advantage of statistical multiplexing proved.

4 min read 0 comments

In a packet network the largest and most variable delays arise in queues: a router receives packets from many directions and must transmit them one at a time. How long does one wait on average? How heavily can a link be loaded before delays explode? Queueing theory answers with simple and surprisingly useful formulas. In this lesson we look at Little’s law with its proof, the M/M/1 queue with the proof of the distribution of the number of packets, the growth of delay with load, and the advantage of statistical multiplexing proved.

The model

A queue is described by how customers (packets) arrive, how long service (transmission) lasts and how many servers there are. Let \lambda be the arrival rate (packets per second) and \mu the service rate (packets per second the link transmits when busy). The ratio

    \[ \rho = \frac{\lambda}{\mu} \]

is the utilisation: the fraction of time the link is busy. For the queue not to grow without bound, \rho \lt 1 is needed.

Little’s law

Theorem (Little). In a system in equilibrium, the mean number of customers present E[N], the arrival rate \lambda and the mean time spent in the system E[T] are related by

    \[ E[N] = \lambda\,E[T] \]

Proof (idea). Observe the system for a long time \tau. Plot the number of customers present as a function of time and compute the area under the curve. It can be computed in two ways: integrating the number present over time, \int_0^\tau N(t)dt = \tau\,E[N]; or adding up the time each customer spent in the system, because each contributes to the area a strip of height 1 and length equal to its stay. In time \tau about \lambda\tau customers arrive, with mean stay E[T], for an area \lambda\tau\,E[T]. Equating and dividing by \tau gives the law. ∎

It holds for any distribution of arrivals and services, and for any part of the system: the queue alone, the server alone, a whole network. If a router holds 50 packets on average and 10 000 arrive per second, each stays 5 ms on average.

The M/M/1 queue

The simplest model has Poisson arrivals (independent, with exponential inter-arrival times), exponential service times and a single server: it is written M/M/1. The state is the number n of packets present.

Theorem. In equilibrium the probability of finding n packets is p_n = (1 - \rho)\rho^n, and

    \[ E[N] = \frac{\rho}{1 - \rho},\qquad E[T] = \frac{1}{\mu - \lambda} \]

Proof. The state goes from n to n + 1 with an arrival, at rate \lambda, and from n + 1 to n with a departure, at rate \mu. In equilibrium the probability flow between two adjacent states balances: \lambda p_n = \mu p_{n+1}, i.e. p_{n+1} = \rho\,p_n, whence p_n = \rho^n p_0. The probabilities must sum to 1: p_0\sum\rho^n = p_0/(1 - \rho) = 1, so p_0 = 1 - \rho. The mean of a geometric distribution of this kind is \sum n(1-\rho)\rho^n = \rho/(1 - \rho). Finally, by Little’s law, E[T] = E[N]/\lambda = \frac{\rho}{\lambda(1-\rho)} = \frac{1}{\mu - \lambda}. ∎

Mean delay in the M/M/1 queue as a function of utilisation
The mean time in the system, measured in service times, is 2 with the link 50 % busy, 5 at 80 % and 10 at 90 %, and grows without bound approaching 100 %.

The lesson of the graph

The delay, measured in service times 1/\mu, is 1/(1 - \rho): 2 at 50 % utilisation, 5 at 80 %, 10 at 90 %, 100 at 99 %. Growth is gentle up to half load and violent beyond 80 %.

Example. A 10 Mb/s link with 1000-byte packets has \mu = 1250 packets per second, i.e. 0.8 ms per packet. With \lambda = 1000 packets per second (\rho = 0.8) the mean time in the system is 1/(1250 - 1000) = 4 ms: five times the transmission time. That is why network operators add capacity well before links are saturated, and why a “slow” network is often not slow but loaded.

Real traffic is not exactly Poisson: it is burstier, and delays at the same load are larger. But the shape of the curve, exploding near \rho = 1, remains.

Statistical multiplexing

Theorem. A single link of capacity C shared by N flows each of rate \lambda gives a mean delay N times smaller than N separate links of capacity C/N, each dedicated to one flow.

Proof. With separate links, each has service rate \mu/N (where \mu corresponds to capacity C) and arrivals \lambda: E[T] = 1/(\mu/N - \lambda) = N/(\mu - N\lambda). With the shared link service is \mu and arrivals N\lambda: E[T] = 1/(\mu - N\lambda). The ratio is N. Utilisation is the same in both cases. ∎

It is the quantitative justification of packet switching (lesson on architecture): pooling resources reduces waiting, because a flow can use the capacity left free by the others. The same principle, pooling resources, explains why in a supermarket a single queue serving several tills works better than separate queues.

Related articles

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x