13 - General queueing theory  pp. 247-270

General queueing theory

By Piet Van Mieghem

Image View Previous Chapter Next Chapter

Queueing theory describes basic phenomena such as the waiting time, the throughput, the losses, the number of queueing items, etc. in queueing systems. Following Kleinrock (1975), any system in which arrivals place demands upon a finite-capacity resource can be broadly termed a queueing system.

Queuing theory is a relatively new branch of applied mathematics that is generally considered to have been initiated by A. K. Erlang in 1918 with his paper on the design of automatic telephone exchanges, in which the famous Erlang blocking probability, the Erlang B-formula (14.17), was derived (Brockmeyer et al., 1948, p. 139). It was only after the Second World War, however, that queueing theory was boosted mainly by the introduction of computers and the digitalization of the telecommunications infrastructure. For engineers, the two volumes by Kleinrock (1975, 1976) are perhaps the most well-known, while in applied mathematics, apart from the penetrating influence of Feller (1970, 1971), the Single Server Queue of Cohen (1969) is regarded as a landmark. Since Cohen's book, which incorporates most of the important work before 1969, a wealth of books and excellent papers have appeared, an evolution that is still continuing today.

A queueing system

Examples of queueing abound in daily life: queueing situations at a ticket window in the railway station or post office, at the cash points in the supermarket, the waiting room at the airport, train or hospital, etc. In telecommunications, the packets arriving at the input port of a router or switch are buffered in the output queue before transmission to the next hop towards the destination.