Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling

F.P. Kelly
C.N. Laws

Queueing Systems 13 (1993) 47-86


We present an introductory review of recent work on the control of open queueing networks. We assume that customers of different types arrive at a network and pass through the system via one of several possible routes; the set of routes available to a customer depends on its type. A route through the network is an ordered set of service stations: a customer queues for service at each station on its route and then leaves the system. The two methods of control we consider are the routing of customers through the network, and the sequencing of service at the stations, and our aim is to minimize the number of customers in the system. We concentrate especially on the insights which can be obtained from heavy traffic analysis, and in particular from Harrison's Brownian network models. Our main conclusion is that in many respects dynamic routing simplifies the behaviour of networks, and that under good control policies it may well possible to model the aggregate behaviour of a network quite straightforwardly.

Keywords: Brownian network models, resource pooling, threshold strategies, generalized cut constraints, heavy traffic analysis, pathwise solution, dynamic sequencing, shortest delay routing.


See also Neil Laws' paper on "Resource pooling in queueing networks with dynamic routing", and
Yih-Choung Teh and Amy Ward's paper on "Critical Thresholds for Dynamic Routing in Queueing Networks".

Frank Kelly's papers