UC San Diego

Stochastic processing networks arise as models in manufacturing, telecommunications, transportation, computer systems, the customer service industry, and biochemical reaction networks. Common characteristics of these networks are that they have entities—such as jobs, packets, vehicles, customers, or molecules—that move along routes, wait in buffers, receive processing from various resources, and are subject to the effects of stochastic variability through such quantities as arrival times, processing times, and routing protocols. The mathematical theory of queueing aims to understand, analyze, and control congestion in stochastic processing networks. In this article, we begin by summarizing some of the highlights in the development of the theory of queueing prior to 1990; this includes some exact analysis and development of approximate models for certain queueing networks. We then describe some surprises of the early 1990s and ensuing developments of the past 25 years related to the use of approximate models for analyzing the stability and performance of multiclass queueing networks. We conclude with a description of recent developments for more general stochastic processing networks and point to some open problems.