Queueing Notes for USC Course EE549
By: Michael Neely
Introduction to Queueing Systems
A modern data communication system consists of a network of information processing stations or nodes interconnected by data transmission channels or links. Information flows from node to node in packetized data units. These packets can originate from a variety of sources, and the paths over which they traverse the network can intersect, so that multiple packets are often intended for delivery over the same transmission link. When the number of packets in a particular node exceeds the service capabilities of the outgoing links of the node, some packets must either be dropped (resulting in a loss of information) or placed in a storage buffer or queue for future service. Queueing theory is the study of congestion and delay in such systems.
The dynamics of queueing systems are event driven, that is, the state of a queue changes based on discrete events such as packet arrivals or departures. Such systems are fundamentally different from the linear or nonlinear systems studied in classical control theory, where inputs are continuous functions of time (such as voltage or current waveforms) and where state dynamics are described by differential equations. Queueing systems are also very different from the point-to-point transmission models of physical layer communication, where inputs consist of band-limited signals that are corrupted by continuous background processes such as additive Gaussian noise. Thus, queueing systems require a different and unique set of mathematical tools. An understanding of these tools is essential in the analysis, design, and control of data networks.