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.