14.1 Notation and Little’s law
A queue is described in Kendall’s notation \(A/B/c\): the inter-arrival distribution \(A\), the service distribution \(B\), and the number of servers \(c\), where \(M\) (Markov) means exponential, \(D\) deterministic and \(G\) general. So M/M/1 has Poisson arrivals at rate \(\lambda \), exponential services at rate \(\mu \) and one server. The traffic intensity \(\rho = \lambda /(c\mu )\) is the fraction of time each server is busy; the queue is stable only if \(\rho < 1\). The quantities of interest are \(L\) and \(L_q\), the mean numbers in the system and in the queue, and \(W\) and \(W_q\), the mean times spent in the system and waiting.
Theorem 14.1.1 (Little’s law, 1961). In a stable queueing system in steady state, \(L = \lambda W\); likewise \(L_q = \lambda W_q\), and the mean number in service is \(\lambda /\mu \).
Sketch. Let \(N(t)\) be the number in the system at time \(t\). Over a long interval \([0, T]\), the area \(\int _0^TN(t)\,dt\) can be computed in two ways: as \(T\) times the average number present, \(TL\); and as the sum over customers of the times they spent in the system, about \(\lambda T\) customers each staying \(W\) on average. Dividing by \(T\) and letting \(T \to \infty \) gives \(L = \lambda W\). The argument uses no assumption about the distributions or the service discipline. □
Exponential times are special because they are memoryless: \(P(S > s + t \mid S > s) = P(S > t)\), so the time a service still has to run does not depend on how long it has run. With exponential inter-arrival and service times the number in the system is therefore a Markov process, and its steady state can be found exactly.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.