Abstract
Complex models of computer systems are often difficult to study with numerical or analytical approaches because of the state space explosion problem. The class of product-form models is one of the most significant tools for overcoming this problem, and in many applications, this tool is the only way to perform a quantitative analysis.
In this paper, we study the duality between two different product-form models. The first consists of a queuing network with finite capacity waiting rooms governed by the skip-over policy. The second is a recently presented product-form model in which a job fetching policy is applied. To investigate the relationships between these two models, we first extend the fetching queuing model to allow for finite capacity warehouses and for a Repetitive Service Blocking with Random Destination (RS-RD) discipline. Subsequently, we represent their distinctive features in terms of Generalized Stochastic Petri Nets which precisely specify their semantics in a modular manner and provide clear and intuitive interpretations of these policies. With these two preliminary results, we prove that it is possible to structurally transform a model of one class into one of the other and vice versa, thus choosing the representation that is computationally more convenient to compute the performance measures of interest.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Marsan, M.A., Balbo, G., Conte, G., Donatelli, S., Franceschinis, G.: Modelling with Generalized Stochastic Petri Nets. Wiley, Hoboken (1995)
Ajmone Marsan, M., Balbo, G., Conte, G.: A class of generalized stochastic petri nets for the performance evaluation of multiprocessor systems. ACM Trans. Comput. Syst. 2(2), 93–122 (1984)
Balbo, G., Bruell, S.C., Sereno, M.: Product form solution for generalized stochastic petri nets. IEEE Trans. Software Eng. 28(10), 915–932 (2002)
Balsamo, S., Harrison, P.G., Marin, A.: A unifying approach to product-forms in networks with finite capacity constraints. In: SIGMETRICS 2010, Proceedings of the 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pp. 25–36. ACM (2010)
Balsamo, S., de Nitto Persone, V.: A survey of product form queueing networks with blocking and their equivalences. Ann. Oper. Res. 48(1), 31–61 (1994)
Baskett, F., Chandy, K., Muntz, R., Palacios, F.: Open, closed and mixed networks of queues with different classes of customers. J. ACM 22(2), 248–260 (1975)
Boucherie, R.J., van Dijk, N.M.: On the arrival theorem for product form queueing networks with blocking. Perform. Eval. 29(3), 155–176 (1997)
Chao, X., Miyazawa, M., Pinedo, M.: Queueing Networks: Customers, Signals and Product Form Solutions. Wiley, Hoboken (1999)
Chiola, G., Ajmone Marsan, M., Balbo, G., Conte, G.: Generalized stochastic petri nets: a definition at the net level and its implications. IEEE Trans. Software Eng. 19(2), 89–107 (1993)
Ciardo, G., Miner, A., Wan, M.: Advanced features in SMART: the stochastic model checking analyzer for reliability and timing. ACM SIGMETRICS Perform. Eval. Rev. 36(4), 58–63 (2009)
Ciardo, G., Muppala, J., Trivedi, K.: On the solution of GSPN reward models. Perform. Eval. 12(4), 237–253 (1991)
Gates, D., Westcott, M.: Stationary states of crystal growth in three dimensions. J. Stat. Phys. 81, 681–715 (1995)
Gelenbe, E.: G-networks: multiple classes of positive customers, signals, and product form results. In: Calzarossa, M.C., Tucci, S. (eds.) Performance 2002. LNCS, vol. 2459, pp. 1–16. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45798-4_1
Harchol-Balter, M.: Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge Press, Cambridge (2013)
Harrison, P.G., Marin, A.: Product-forms in multi-way synchronizations. Comput. J. 57(11), 1693–1710 (2014)
Jackson, J.R.: Networks of waiting lines. Oper. Res. 5(4), 518–521 (1957)
Jackson, J.R.: Jobshop-like queueing systems. Manage. Sci. 10(1), 131–142 (1963)
Kelly, F.P.: Reversibility and Stochastic Networks. Wiley, Hoboken (1979)
Lam, S.S.: Dynamic scaling and growth behavior of queueing network normalization constants. J. ACM 29(2), 492–513 (1982)
Marin, A., Rossi, S., Olliaro, D.: A product-form network for systems with job stealing policies. SIGMETRICS Perform. Eval. Rev. 50(4), 2–4 (2023)
Pittel, B.G.: Closed exponential networks of queues with saturation: the Jackson-type stationary distribution and its asymptotic analysis. Math. Oper. Res. 4(4), 357–378 (1979)
Sevcik, K.C., Mitrani, I.: The distribution of queuing network states at input and output instants. J. ACM 28(2), 358–371 (1981)
Towsley, D.F.: Queuing network models with state-dependent routing. J. ACM 27(2), 323–337 (1980)
Van der Gaast, J., De Koster, R., Adan, I.J.B.F., Resing, J.A.C.: Capacity analysis of sequential zone picking systems. Oper. Res. 68(1), 161–179 (2020)
Zhang, X., Xue, Q., Li, L., Fan, E., Wu, F., Chen, R.: Sustainable recycling and regeneration of cathode scraps from industrial production of lithium-ion batteries. ACS Sustain. Chem. Eng. 4(12), 7041–7049 (2016)
Acknowledgements
This work has been partially supported by project INdAM-GNCS 2023 RISICO CUP E53C22001930001.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Olliaro, D., Balbo, G., Marin, A., Sereno, M. (2023). Skipping and Fetching: Insights on Non-conventional Product-Form Solutions. In: Jansen, N., Tribastone, M. (eds) Quantitative Evaluation of Systems. QEST 2023. Lecture Notes in Computer Science, vol 14287. Springer, Cham. https://doi.org/10.1007/978-3-031-43835-6_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-43835-6_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-43834-9
Online ISBN: 978-3-031-43835-6
eBook Packages: Computer ScienceComputer Science (R0)