Abstract
The purpose of this tutorial is to survey queueing networks, a class of stochastic models extensively applied to represent and analyze resource sharing systems such as communication and computer systems. Queueing networks (QNs) have been proved to be a powerful and versatile tool for system performance evaluation and prediction. First we briefly survey QNs that consist of a single service center, i.e., the basic queueing systems defined under various hypotheses, and we discuss their analysis to evaluate a set of performance indices, such as resource utilization and throughput and customer response time. Their solution is based on the introduction of an underlying stochastic Markov process. Then, we introduce QNs that consist of a set of service centers representing the system resources that provide service to a collection of customers that represent the users. Various types of customers define the customers classes in the network that are gathered in chains. We consider various analytical methods to analyze QNs with single-class and multiple-class. We mostly focus on product-form QNs that have a simple closed form expression of the stationary state distribution that allows to define efficient algorithms to evaluate average performance measures. We review the basic results, stating from the BCMP theorem that defines a large class of product-form QNs, and we present the main solution algorithms for single-class e multiple-class QNs. We discuss some interesting properties of QNs including the arrival theorem, exact aggregation and insensitivity. Finally, we discuss some particular models of product-form QNs that allow to represent special system features such as state-dependent routing, negative customers, customers batch arrivals and departures and finite capacity queues. The class of QN models is illustrated through some application examples of to analyze computer and communication systems.
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Afshari, P.V., Bruell, S.C., Kain, R.Y.: Modeling a new technique for accessing shared buses. In: Proc. of the Computer Network Performance Symposium, College Park, Maryland, United States, pp. 4–13. ACM Press, New York (1982), doi:10.1145/800047.801685
Akyildiz, I.F.: Exact product form solution for queueing networks with blocking. IEEE Trans. on Computer 36(1), 122–125 (1987)
Akyildiz, I.F., Bolch, G.: Mean value analysis approximation for multiple server queueing networks. Perform. Eval. 8(2), 77–91 (1988)
Baccelli, F., Massey, W., Towsley, D.: Acyclic fork-join queueing networks. Journal of the ACM 36, 615–642 (1989)
Balsamo, S., De Nitto Personé, V., Onvural, R.: Analysis of Queueing Networks with Blocking. Kluwer Academic Publishers, Dordrecht (2001)
Balsamo, S., Iazeolla, G.: An extension of Norton’s theorem for queueing networks. IEEE Trans. on Software Eng. 8 (1982)
Balsamo, S., Iazeolla, G.: Product-form synthesis of queueing networks. IEEE Trans. on Software Eng. 11(2), 194–199 (1985)
Bard, Y.: Some extensions to multiclass queueing network analysis. In: Proc. of the Third Int. Symp. on Modelling and Performance Evaluation of Computer Systems, Amsterdam, NL, pp. 51–62. North-Holland, Amsterdam (1979)
Baskett, F., Chandy, K.M., Muntz, R.R., Palacios, F.G.: Open, closed, and mixed networks of queues with different classes of customers. J. ACM 22(2), 248–260 (1975), doi:10.1145/321879.321887
Bolch, G., Greiner, S., de Meer, H., Trivedi, K.S.: Queueing networks and Markov chains. John Wiley, Chichester (1998)
Boucherie, R., van Dijk, N.M.: Product-form queueing networks with state dependent multiple job transitions. Advances in Applied Prob. 23, 152–187 (1991)
Bruell, S.C., Balbo, G.: Computational Algorithms for Closed Queueing Networks. The Computer Science Library. Elsevier, New York (1980)
Buzen, J.P.: Computational algorithms for closed queueing networks with exponential servers. Commun. ACM 16(9), 527–531 (1973), doi:10.1145/362342.362345
Calzarossa, M.C., Tucci, S. (eds.): Performance 2002. LNCS, vol. 2459. Springer, Heidelberg (2002)
Chandy, K.M., Herzog, U., Woo, L.: Parametric analysis of queueing networks. IBM Journal of Res. and Dev. 1(1), 36–42 (1975)
Chandy, K.M., Hergox, U., Woo, L.: Approximate analysis of general queueing networks. IBM Journal of Res. and Dev. 19, 43–49 (1975)
Chandy, K.M., John, H., Howard, J., Towsley, D.F.: Product form and local balance in queueing networks. J. ACM 24(2), 250–263 (1977)
Chandy, K.M., Martin, A.J.: A characterization of product-form queuing networks. J. ACM 30(2), 286–299 (1983), doi:10.1145/322374.322378
Chandy, K.M., Neuse, D.: Linearizer: a heuristic algorithm for queueing network models of computing systems. Commun. ACM 25(2), 126–134 (1982), doi:10.1145/358396.358403
Chandy, K.M., Sauer, C.H.: Computational algorithms for product form queueing networks. Commun. ACM 23(10), 573–583 (1980), doi:10.1145/359015.359020
Cohen, J.W.: The single server queue. Wiley-Interscience, Chichester (1969)
Conway, A.E., de Souza e Silva, E., Lavenberg, S.S.: Mean Value Analysis by chain of product form queueing networks. IEEE Trans. Comput. 38(3), 432–442 (1989), doi:10.1109/12.21129
Conway, A.E., Georganas, N.D.: Recal - a new efficient algorithm for the exact analysis of multiple-chain closed queuing networks. J. ACM 33(4), 768–791 (1986), doi:10.1145/6490.6495
Conway, A.E., Georganas, N.D.: Queueing Networks - Exact Computational Algorithms: A unified Theory Based on Decomposition and Aggregation. The MIT Press, Cambridge (1989)
Courtois, P.J.: Decomposability. Academic Press, New York (1977)
de Souza e Silva, E., Lavenberg, S.S.: Calculating joint queue-length distributions in product-form queuing networks. J. ACM 36(1), 194–207 (1989), doi:10.1145/58562.58563
Fourneau, J.-M., Gelenbe, E., Suros, R.: G-networks with multiple class negative and positive customers. In: MASCOTS ’94: Proc. of the Second International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, Washington, DC, USA, pp. 30–34. IEEE Computer Society Press, Los Alamitos (1994)
Fourneau, J.-M., Verchere, D.: G-networks with triggered batch state-dependent movement. In: Proc. MASCOTS, pp. 33–37 (1995), citeseer.ist.psu.edu/fourneau94gnetworks.html
Gelenbe, E.: Product form networks with negative and positive customers. Journal of Applied Prob. 28(3), 656–663 (1991)
Gelenbe, E.: G-networks: a unifying model for neural and queueing networks. Annals of Operations Research 48(5), 433–461 (1994)
Gelenbe, E., Fourneau, J.-M.: G-networks with resets. Perform. Eval. 49(1-4), 179–191 (2002)
Gelenbe, E., Mitrani, I.: Analysis and Synthesis of Computer Systems. Academic Press, New York (1980)
Gordon, W.J., Newell, G.F.: Cyclic queueing networks with exponential servers. Operations Research 15(2), 254–265 (1967)
Gordon, W.J., Newell, G.F.: Cyclic queueing networks with restricted length queues. Operations Research 15(2), 266–277 (1967)
Henderson, W., Taylor, P.: Product form in networks of queues with batch arrivals and batch services. Queueing Systems 6, 71–88 (1990)
Henderson, W., Taylor, P.: Some new results on queueing networks with batch movements. Journal of Applied Prob. 28, 409–421 (1990)
Hoyme, K.P., Bruell, S.C., Afshari, P.V., Kain, R.Y.: A tree-structured Mean Value Analysis algorithm. ACM Trans. Comput. Syst. 4(2), 178–185 (1986), doi:10.1145/214419.214423
Jackson, J.R.: Jobshop-like queueing systems. Management Science 10, 131–142 (1963)
Kant, K.: Introduction to Computer System Performance Evaluation. McGraw-Hill, New York (1992)
Kelly, F.: Reversibility and stochastic networks. Wiley, New York (1979)
Kemeny, J.G., Snell, J.L.: Finite Markov Chains. D. Van Nostrand Company, inc., New York (1960)
Kleinrock, L.: Queueing Systems, vol. 1: Theory. John Wiley and Sons, Chichester (1975)
Kritzinger, P., van Wyk, S., Krezesinski, A.: A generalization of Norton’s theorem for multiclass queueing networks. Performance Evaluation 2, 98–107 (1982)
Lam, S.S.: Queueing networks with capacity constraints. IBM Journal of Res. and Dev. 21(4), 370–378 (1977)
Lam, S.S.: Dynamic scaling and growth behavior of queuing network normalization constants. J. ACM 29(2), 492–513 (1982), doi:10.1145/322307.322321
Lam, S.S., Lien, Y.L.: A tree-convolution algorithm for the solution of queueing networks. Commun. ACM 26(3), 203–215 (1983), doi:10.1145/358061.358075
Lavenberg, S., Reiser, M.: Stationary state probabilities at arrival instants for closed queueing networks with multiple types of customers. Journal of Applied Prob. 17, 1048–1061 (1980)
Lavenberg, S.S.: Computer Performance Modeling Handbook. Academic Press, New York (1983)
Lazowska, E.D., Zahorjan, J.L., Graham, G.S., Sevcick, K.C.: Quantitative system performance: computer system analysis using queueing network models. Prentice Hall, Englewood Cliffs (1984)
Le Boudec, J.-Y.: A BCMP extension to multiserver stations with concurrent classes of customers. In: SIGMETRICS ’86/PERFORMANCE ’86: Proc. of the 1986 ACM SIGMETRICS Int. Conf. on Computer performance modelling, measurement and evaluation, Raleigh, North Carolina, United States, pp. 78–91. ACM Press, New York (1986), doi:10.1145/317499.317541
Marie, R.: An approximate analytical method for general queueing networks. IEEE Trans. on Software Eng. 5(5), 530–538 (1979)
Menascè, D.A., Almeida, V.A.F.: Capacity Planning for Web Performance. Metrics, Models, & Methods. Prentice-Hall, Englewood Cliffs (1998)
Muntz, R.: Network of queues. Tech. Rep. Notes for Engineering 226 C., University of Los Angeles, Department of Computer Science (1972)
Muntz, R., Wong, J.: Efficient computational procedures for closed queueing network models. In: Proc. 7th Hawaii Int. Conf. on System Science, Hawaii, January 1974, pp. 33–36 (1974)
Muntz, R.R.: Poisson departure processes and queueing networks. Tech. Rep. IBM Research Report RC4145, Yorktown Heights, New York (1972)
Nelson, R.: The mathematics of product-form queueing networks. ACM Computing Survey 25(3), 339–369 (1993)
Neuse, D., Chandy, K.: SCAT: A heuristic algorithm for queueing network models of computing systems. In: Proc. of ACM SIGMETRICS Conf. on measurement and modeling of computer systems, Las Vegas, Nevada, United States, pp. 59–79. ACM Press, New York (1981), doi:10.1145/800189.805476
Neuts, M.F.: Matrix Geometric Solutions in Stochastic Models. John Hopkins, Baltimore (1981)
Noetzel, A.S.: A generalized queueing discipline for product form network solutions. J. ACM 26(4), 779–793 (1979), doi:10.1145/322154.322166
Pattipati, K.R., Kostreva, M.M., Teele, J.L.: Approximate mean value analysis algorithms for queuing networks: existence, uniqueness, and convergence results. J. ACM 37(3), 643–673 (1990), doi:10.1145/79147.214074
Petriu, D.C., Neilson, J.E., Woodside, C.M., Majumdar, S.: Software bottlenecking in client-server systems and rendezvous networks. IEEE Trans. on Software Eng. 21(9), 776–782 (1995)
Raiser, M.: Mean Value Analysis and Convolution method for queue-dependent servers in closed queueing networks. Performance Evaluation 1(1), 7–18 (1981)
Reiser, M., Sauer, C.H.: Queueing network models: Methods of solution and their program implementation. In: Chandy, K.M., Yeh, R.T. (eds.) Current Trends in Programming Methodology, Prentice-Hall, Englewood Cliffs (1978)
Resiser, M., Lavenberg, S.S.: Mean Value Analysis of closed multichain queueing network. J. ACM 27(2), 313–320 (1980)
Rolia, J.A., Sevcick, K.C.: The methods of layers. IEEE Trans. on Software Eng. 21(8), 682–688 (1995)
Sahner, R., Trivedi, K., Puliafito, A.: Performance and Reliability Analysis of Computer Systems - An Example-Based Approach Using the SHARPE Software Package. Kluwer Academic Publishers, Boston (1996)
Sauer, C.H.: Computational algorithms for state-dependent queueing networks. ACM Trans. Comput. Syst. 1(1), 67–92 (1983), doi:10.1145/357353.357359
Sauer, C.H., Chandy, K.M.: Computer Systems performance modeling. Prentice-Hall, Englewood Cliffs (1981)
Schweitzer, P.: Approximate analysis of multiclass closed network of queues. In: Proc. of Int. Conf. on Stochastic Control and Optimization, Amsterdam, NL (1979)
Sevcik, K.C., Mitrani, I.: The distribution of queuing network states at input and output instants. J. ACM 28(2), 358–371 (1981), doi:10.1145/322248.322257
Shassenberger, R.: The insensitivity of stationary probabilities in networks of queues. Journal of Applied Prob. 10, 85–93 (1978)
Smith, C.: Performance Engineering of Software Systems. Addison-Wesley, Reading (1990)
Strelen, J.: A generalization of Mean Value Analysis to higher moments: moment analysis. In: SIGMETRICS ’86/PERFORMANCE ’86: Proc. of 1986 ACM SIGMETRICS Int. Conf. on computer performance modelling, measurement and evaluation, Raleigh, North Carolina, United States, pp. 129–140. ACM Press, New York (1986), doi:10.1145/317499.317546
Suri, R.: Robustness of queuing network formulas. J. ACM 30(3), 564–594 (1983), doi:10.1145/2402.2995
Towsley, D.: Queuing network models with state-dependent routing. J. ACM 27(2), 323–337 (1980), doi:10.1145/322186.322196
Trivedi, K.S.: Probability and statistics with reliability, queuing and computer science applications, 2nd edn. Wiley-Interscience, Chichester (2002)
Tucci, S., Sauer, C.: The tree MVA algorithm. Performance Evaluation 5(3), 187–196 (1985)
van Dijk, N.: Queueing networks and product forms. John Wiley, Chichester (1993)
Whittle, P.: Partial balance and insensitivity. Journal of Applied Prob. 22, 168–175 (1985)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this chapter
Cite this chapter
Balsamo, S., Marin, A. (2007). Queueing Networks. In: Bernardo, M., Hillston, J. (eds) Formal Methods for Performance Evaluation. SFM 2007. Lecture Notes in Computer Science, vol 4486. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72522-0_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-72522-0_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72482-7
Online ISBN: 978-3-540-72522-0
eBook Packages: Computer ScienceComputer Science (R0)