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**

- Simon S. Lam, Queueing
Networks with Population Size Constraints,
*IBM Journal of Research and Development*, Vol. 21, July 1977. - Simon S. Lam, Dynamic
Scaling and Growth Behavior of Queueing Network Normalization Constants,
*Journal of the ACM*, Vol. 29, No. 2, April 1982. - Simon S. Lam and Y. Luke Lien, A
Tree Convolution Algorithm for the Solution of Queueing Networks,
*Comm. ACM*, Vol. 26, No. 3, March 1983. - Simon S. Lam, A
Simple Derivation of the MVA and LBANC Algorithms from the Convolution
Algorithm,
*IEEE Trans. on Computers*, Vol. C-32, No. 11, November 1983. - Johnny W. Wong and Simon S. Lam, Queueing
Network Models of Packet Switching Networks, Part 1: Open Networks,
*Performance Evaluation*, Vol. 2, No. 1, 1982. - Simon S. Lam and Johnny W. Wong, Queueing
Network Models of Packet Switching Networks, Part 2: Networks with Population
Size Constraints,
*Performance Evaluation*, Vol. 2, No. 3, 1982. - C. T. Hsieh and Simon S. Lam,
Two
Classes of Performance Bounds for Closed Queueing Networks,
*Performance Evaluation*, Vol. 7, No. 1, February 1987. - C. T. Hsieh and Simon S. Lam,
PAM--A Noniterative Approximate Solution Method for Closed Multichain Queueing
Networks,
*Performance Evaluation*, Vol. 9, No. 2, April 1989.