QUEUEING THEORY

5/30/98

Queueing Theory: A branch of Mathematics that deals with systems where activities must wait in lines (queues) to be served by devices (servers) with limited throughput. In the case of computer systems, the system is modeled as a group of devices with transaction flows between them, queues at their inputs and an average service time per transaction. Queueing theory can be used to predict the behavior of many complex systems including market checkout lines, traffic flow, and complex computer systems.

Queueing theory is based in statistics and is rigorous in the sense that its theorems can be tested and logically proved. Real systems often have features that violate some assumptions on which queueing theory is based. For example a task may manage to do other work while waiting in a queue whereas queueing theory assumes that no work occurs while a task is waiting for service. But it has been observed that queueing theory often produces fairly accurate predictions even though the system in question is not really logically required to behave according to the theory.

Queueing theory is most useful for predicting average performance. Because queueing theory is a mathematical system and not an empirical model, it can be used to compute elements other than throughput. For example if one knows thruput, data flows, and queue lengths, then service times can be computed. Queueing theory can be useful in predicting where bottlenecks will occur and in preventing embarrassing situations where a performance oriented upgrade makes improvements in the wrong places and provides little or no system performance improvement.

Return To Index Copyright 1994-2002 by Donald Kenney.