Article

Free access

On the convolution algorithm for separable queuing networks

Authors:

SIGMETRICS '76: Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation

Pages 109 - 117

https://doi.org/10.1145/800200.806187

Published: 29 March 1976 Publication History

PDF eReader

Abstract

Research into queuing networks and their applications to computer systems is in a state of prosperity. The object of this paper is to discuss the computational aspect of separable queuing networks. Separable networks constitute that class of models for which a solution can be computed efficiently for fairly large problems. Open networks do not pose any computational problem. It is the case of closed networks where the subject of numerical algorithms becomes an issue.

In this paper, we shall take a fresh look at closed queuing networks, which we introduce as conditioned solution of suitably chosen open networks. This view will provide a probabilistic interpretation of what is normally called the normalization constant. Computational algorithms, then, result in a systematic way.

References

[1]

K.M. Chandy, U. Herzog and L. Woo, "Approximate Analysis of General Queuing Networks", IBM J. Res. and Develop., 19, January 1975, pp. 43-49.

Digital Library

Google Scholar

[2]

M. Reiser, "QNET4 User's Guide", IBM Research Report RA 71, June 1975.

Google Scholar

[3]

F. Baskett, K.M. Chandy, R.R. Muntz, and F.G. Palacios, "Open, Closed, and Mixed Networks of Queues with Different Classes of Customers," Journal of the ACM, April 1975. pp. 248-260

Digital Library

Google Scholar

[4]

F.R. Moore, "Computational Model of a Closed Queuing Network with Exponential Servers," IBM J. Res. Dev., 16, November 1972, pp. 567-572.

Digital Library

Google Scholar

[5]

S.S. Lam, "On an Extension of Moore's Results for Closed Queuing Networks," IBM Research Report, April 9, 1975.

Google Scholar

[6]

T.P. Buzen, "Computational Algorithms for Closed Queuing Networks with Exponential Servers," Communications of the ACM, 16, September pp. 527-531.

Digital Library

Google Scholar

[7]

M. Reiser and H. Kobayashi, "Recursive Algorithms for General Queuing Networks with Exponential Servers," IBM Res. Report, RC-4254, March 1973.

Google Scholar

[8]

M. Reiser and H. Kobayashi, "Horner's Rule for the Evaluation of General Closed Queuing Networks," CACM, 18 October 1975, pp. 592-593.

Digital Library

Google Scholar

[9]

M. Reiser and H. Kobayashi, "Queuing Networks with Multiple Closed Chains: Theory and Computational Algorithms," IBM Research Report RC-4919, July, 1974, IBM Research Center, Yorktown Heights, New York Also in IBM Journal of Research and Development, May 1975. pp. 283-294.

Google Scholar

[10]

M. Reiser and H. Kobayashi, "Numerical Methods in Queueing Networks", Proc. Camp. Sci and Statistics, 8th Annual Symp. of the Interface, (Univ. of California, Los Angelos), Feb. 1975.

Google Scholar

[11]

M. Reiser, "Numerical Methods in Separable Queuing Networks", IBM Research Report

Google Scholar

[12]

Lin Woo, private communication (see also ref. 1).

Google Scholar

Cited By

View all

Wang WCasale GKattepur ANambiar MAvritzer AIosup AZhu XBecker S(2016)Maximum Likelihood Estimation of Closed Queueing Network Demands from Queue Length DataProceedings of the 7th ACM/SPEC on International Conference on Performance Engineering10.1145/2851553.2851565(3-14)Online publication date: 12-Mar-2016
https://dl.acm.org/doi/10.1145/2851553.2851565
Wang HSevcik KSerazzi GWang S(2008)The general form linearizer algorithmsPerformance Evaluation10.1016/j.peva.2007.05.00565:2(129-151)Online publication date: 1-Feb-2008
https://dl.acm.org/doi/10.1016/j.peva.2007.05.005
Harrison PTing Ting Lee (2004)A new recursive algorithm for computing generating functions in closed multi-class queueing networksThe IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, 2004. (MASCOTS 2004). Proceedings.10.1109/MASCOT.2004.1348255(231-238)Online publication date: 2004
https://doi.org/10.1109/MASCOT.2004.1348255
Show More Cited By

Index Terms

On the convolution algorithm for separable queuing networks
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
  2. Probability and statistics
    1. Statistical paradigms
      1. Queueing theory

Recommendations

Stability of Multiclass Queueing Networks Under FIFO Service Discipline

In this paper, we first formally identify a FIFO fluid network that corresponds to the queueing network under a first-in first-out FIFO service discipline, thus complementing the result of Dai Dai, J. G. 1995a. On positive Harris recurrence of ...
Stability of Multiclass Queueing Networks Under FIFO Service Discipline

In this paper, we first formally identify a FIFO fluid network that corresponds to the queueing network under a first-in first-out FIFO service discipline, thus complementing the result of Dai Dai, J. G. 1995a. On positive Harris recurrence of ...
Stability of Earliest-Due-Date, First-Served Queueing Networks

We study multiclass queueing networks with the earliest-due-date, first-served (EDDFS) discipline. For these networks, the service priority of a customer is determined, upon its arrival in the network, by an assigned random due date. First-in-system, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGMETRICS '76: Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation

March 1976

326 pages

ISBN:9781450374972

DOI:10.1145/800200

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 March 1976

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
421
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)10

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang WCasale GKattepur ANambiar MAvritzer AIosup AZhu XBecker S(2016)Maximum Likelihood Estimation of Closed Queueing Network Demands from Queue Length DataProceedings of the 7th ACM/SPEC on International Conference on Performance Engineering10.1145/2851553.2851565(3-14)Online publication date: 12-Mar-2016
https://dl.acm.org/doi/10.1145/2851553.2851565
Wang HSevcik KSerazzi GWang S(2008)The general form linearizer algorithmsPerformance Evaluation10.1016/j.peva.2007.05.00565:2(129-151)Online publication date: 1-Feb-2008
https://dl.acm.org/doi/10.1016/j.peva.2007.05.005
Harrison PTing Ting Lee (2004)A new recursive algorithm for computing generating functions in closed multi-class queueing networksThe IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, 2004. (MASCOTS 2004). Proceedings.10.1109/MASCOT.2004.1348255(231-238)Online publication date: 2004
https://doi.org/10.1109/MASCOT.2004.1348255
Wang HSevcik K(2000)Experiments with improved approximate mean value analysis algorithmsPerformance Evaluation10.1016/S0166-5316(99)00064-439:1-4(189-206)Online publication date: 1-Feb-2000
https://dl.acm.org/doi/10.1016/S0166-5316%2899%2900064-4
de Souza e Silva ELavenberg SMuntz R(1986)A Clustering Approximation Technique for Queueing Network Models with a Large Number of ChainsIEEE Transactions on Computers10.1109/TC.1986.167678435:5(419-430)Online publication date: 1-May-1986
https://dl.acm.org/doi/10.1109/TC.1986.1676784
Sevcik K(1982)Queueing Networks and their Computer System Applications: An Introductory SurveyDeterministic and Stochastic Scheduling10.1007/978-94-009-7801-0_11(211-222)Online publication date: 1982
https://doi.org/10.1007/978-94-009-7801-0_11
Zahorjan JWong ESchwetman HSherman S(1981)The solution of separable queueing network models using mean value analysisProceedings of the 1981 ACM SIGMETRICS conference on Measurement and modeling of computer systems10.1145/800189.805477(80-85)Online publication date: 14-Sep-1981
https://dl.acm.org/doi/10.1145/800189.805477
Zahorjan JWong E(1981)The solution of separable queueing network models using mean value analysisACM SIGMETRICS Performance Evaluation Review10.1145/1010629.80547710:3(80-85)Online publication date: 1-Sep-1981
https://dl.acm.org/doi/10.1145/1010629.805477
Gordon KDowdy LSevcik KGraham GNutt G(1980)The impact of certain parameter estimation errors in queueing network modelsProceedings of the 1980 international symposium on Computer performance modelling, measurement and evaluation10.1145/800199.806145(3-9)Online publication date: 28-May-1980
https://dl.acm.org/doi/10.1145/800199.806145
Gordon KDowdy L(1980)The impact of certain parameter estimation errors in queueing network modelsACM SIGMETRICS Performance Evaluation Review10.1145/1009375.8061459:2(3-9)Online publication date: 28-May-1980
https://dl.acm.org/doi/10.1145/1009375.806145
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Stability of Multiclass Queueing Networks Under FIFO Service Discipline

Stability of Multiclass Queueing Networks Under FIFO Service Discipline

Stability of Earliest-Due-Date, First-Served Queueing Networks