Product-form queuing network models have been widely used to model systems with shared resources such as computer systems (both centralized and distributed), communication networks, and flexible manufacturing systems. Closed multichain product-form networks are inherently more difficult to analyze than open networks, due to the effect of normalization. Results in workload characterization for closed networks in the literature are often for networks having special structures and only specific performance measures have been considered.
In this article, we derive certain properties (insensitivity of conditional state probability distributions and fractional-linearity of Markov reward functions) for a broad class of closed multichain product-form networks. These properties are derived using the most basic flow balance conditions of product-form networks. Then we show how these basic properties can be applied in obtaining error bounds when similar customers are clustered together to speed up computation.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: C.4 [Performance of Systems]; D.4.8 [Operating Systems]: Performance -- queuing theory; G.m [Miscellaneous]
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Balance equation, closed network, clustering, error bound, product--form, quasi-reversibility, queuing network
- Forest Baskett, K. Mani Chandy, Richard R. Muntz, and Fernando G. Palacios. Open, closed, and mixed networks of queues with different classes of customers. Journal of the ACM, 22(2):248-260, April 1975.
- K. Mani Chandy, John H. Howard Jr., and Donald F. Towsley. Product form and local balance in queueing networks. Journal of the ACM, 24(2):250-263, April 1977.
- K. M. Chandy and D. Neuse. Linearizer: a heuristic algorithm for queueing network models of computing systems. Communications of the ACM, 25(2):126-134, February 1982.
- Lawrence W. Dowdy, Brian M. Carlson, Alan T. Krantz, and Satish K. Tripathi. Single-class bounds of multi-class queuing networks. Journal of the ACM, 39(1):188-213, January 1992.
- M. Reiser and S. S. Lavenberg. Mean-value analysis of closed multichain queuing networks. Journal of the ACM, 27(2):313-322, April 1980.
- Edmundo de Souza e Silva and S. S. Lavenberg. Calculating joint queue-length distributions in product-form queuing networks. Journal of the ACM, 36(1):194-207, January 1989.
- Satish K. Tripathi and C. Murray Woodside. A vertex-allocation theorem for resources in queuing networks. Journal of the ACM, 35(1):221-230, January 1988.