Queueing theory
Waiting lines and traffic follow statistical rules that set how much capacity a network needs.
Mathematics and information · Probability and statistics · No. 123
- Second industrial revolution
- Science
A Copenhagen Telephone Company scientist's 1909 paper began the mathematics of waiting lines, later applied to data networks.
Chart: Illustration: Queueing theory
Where it comes from
Chart: Map of where it comes from
Erlang joined the Copenhagen Telephone Company in 1908 and led its new laboratory. His 1909 paper on probability and telephone conversations began the subject, and a 1917 paper gave a formula for loss and waiting time.
Three things to know
- Erlang published a formula for loss and waiting time in automatic telephone exchanges in 1917.
- Little's law holds under remarkably general conditions and does not depend on the order in which items are served.
- In the simplest queue, the average time in the system is 1 divided by the service rate minus the arrival rate, so waits climb steeply as a server nears full use.
The journey
- 1 Telephone callsErlang's 1909 paper on probability and telephone conversations
- 2 ExchangesErlang's 1917 formula for loss and waiting time
- 3 General lawLittle's proof of L = λW, 1961
- 4 Data networksKleinrock proposes a study of data networks in 1961 and models them with queues
- 5 ARPANETA packet-switching network, 1969