Horner's rule for the evaluation of general closed queueing networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Horner's rule for the evaluation of general closed queueing networks

Full text

Pdf (187 KB)

Source

Communications of the ACM archive
Volume 18 , Issue 10 (October 1975) table of contents

Pages: 592 - 593

Year of Publication: 1975

ISSN:0001-0782

Authors

M. Reiser	IBM Thomas J. Watson Research Center, Yorktown Heights, NY
H. Kobayashi	IBM Thomas J. Watson Research Center, Yorktown Heights, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 26, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/361020.361217 What is a DOI?

ABSTRACT

The solution of separable closed queueing networks requires the evaluation of homogeneous multinomial expressions. The number of terms in those expressions grows combinatorially with the size of the network such that a direct summation may become impractical. An algorithm is given which does not show a combinatorial operation count. The algorithm is based on a generalization of Horner's rule for polynomials. It is also shown how mean queue size and throughput can be obtained at negligible extra cost once the normalization constant is evaluated.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
	2	Posner, M., and Bernholtz, P. Closed finite queueing networks with time lags and with several classes of units. Op. Res. 16 (1968), 977-985.
	3	Jackson, J.R. Jobshop-like queueing systems, Management Sci. 10 (Oct. 1963), 131-142.
	4	Gordon, W.T., and Newell, G.F. Closed queueing systems with exponential servers. Op. Res. 15 (Apr. 1967), 254-265.
	5	Moore, R.I. Computation model of a closed queueing network with exponential servers. IBM J. Res. Dev. 16 (Nov. 1972), 567-572.
	6	Reiser, M., and Kobayashi, H. Recursive algorithms for general queueing networks with exponential servers. IBM Res. Rep. RC 4254, March 1973.
	7	Jeffrey P. Buzen, Computational algorithms for closed queueing networks with exponential servers, Communications of the ACM, v.16 n.9, p.527-531, Sept. 1973 [doi>10.1145/362342.362345]
	8	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997

CITED BY 3

	M. Reiser , S. S. Lavenberg, Mean-Value Analysis of Closed Multichain Queuing Networks, Journal of the ACM (JACM), v.27 n.2, p.313-322, April 1980
	M. Reiser , H. Kobayashi, On the convolution algorithm for separable queuing networks, Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation, p.109-117, March 29-31, 1976, Cambridge, Massachusetts, United States
	J. C. Browne, A critical overview of computer performance evaluation, Proceedings of the 2nd international conference on Software engineering, p.138-145, October 13-15, 1976, San Francisco, California, United States