Transient Models for Queueing Networks

Graham P. Phillips
Department of Computer Science
University of Stellenbosch
Stellenbosch
South Africa

Abstract:

Models for communication networks provide tools for network dimensioning and facilitate the design of control mechanisms, for example, access control, congestion control and routing mechanisms. The aim of the thesis is to investigate models for transient queueing systems. Exact models for transient systems are computationally expensive and therefore approximate models are compared to determine which models are best suited.

A literature survey is given and the following models are selected for further analysis: Filipiak's model for the M/M/1/K queue, Moore's model for the queue as well as Filipiak's and Tipper & Sundareshan's (TS) models for a network of M/M/1/K queues. The AQ-model is derived in this thesis from Filipiak's model.

The models are implemented in the C programming language and compared over a wide range of conditions. The accuracy for an approximate model is defined in terms of the difference between the queue length yielded by the exact model and the queue length yielded by the approximate model. The following results are obtained:

• The models for the M/M/1/K queue listed in order of decreasing accuracy are: the AQ-model, Moore's model and Filipiak's model while the models in order of increasing computation are: Moore's model, Filipiak's model and the AQ-model.
• The models for a network of M/M/1/K queues listed in order of decreasing accuracy are: the TS-model, the AQ-model and Filipiak's model. Filipiak's model and the AQ-model have similar computational requirements, while the TS-model has a significantly greater requirement. Therefore the AQ-model provides a good compromise between accuracy and computation for transient networks.