University of Texas at Austin Department of Computer Sciences
Networking Research Laboratory
Department of Computer Sciences
The University of Texas at Austin

Director: Simon S. Lam (more publications)

Queueing Network Models and Computational Algorithms

We made fundamental contributions to the theory of queueing networks motivated by applications to the performance analysis of packet switching networks that have flow and congestion control constraints. In particular, we extended the product-form solution for the class of open and closed queueing networks to networks with general population size constraints in our 1977 IBM Journal of R&D and 1982 JACM papers.

We invented the Tree Convolution Algorithm for computing performance measures of networks with a large number of closed chains (which model window flow controlled sessions in a packet switching network).  We discovered that the well-known mean value analysis (MVA) algorithm of Reiser and Lavenberg can be derived from the basic Convolution algorithm in a few algebraic steps.

Our 1977 theorem on networks with population size constraints was applied by J. Kaufman to formulate a blocking model that was widely used for calculating the loss probability of multirate multiservice networks (J. Kaufman, Blocking in a Shared Resource Environment, IEEE Trans. on Comm.,1981).

Selected Publications