A Survey on Queuing Systems with Parallel Servingof Customers

Cover Page

Cite item

Full Text

Abstract

This paper is the first in a series of two articles devoted to the review of “fork-join” (inthe western classification) queuing systems or systems with the splitting of incoming queries.This system is a natural model for many other real systems. The article describes the fork-joinqueueing model construction and main characteristics of this model. Special attention is paid tomethods of analysis of the response time of the system. Since the exact expression for the meanresponse time is known only for the case of two servers, the article gives a detailed descriptionof the approach to obtaining an accurate expression of this characteristic. For the case whenthe number of servers is more than two, approximations of the mean response time are obtainedby different methods, which is explained by the complexity of the studies due to the existingdependence between the queues of subqueries due to common arrival moments. The paperpresents several methods of approximate analysis: various variants of empirical approximation,i.e. methods that refine the obtained characteristics by using the results of simulation modeling;interpolation methods using system load limit values in cases when the incoming flow and servicetime distributions are not exponential.

About the authors

A V Gorbunova

Department of Applied Probability and Informatics Peoples’ Friendship University of Russia (RUDN University)

Author for correspondence.
Email: gorbunova_av@rudn.university

Gorbunova A. V. - assistant of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University)

6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

I S Zaryadov

Institute of Informatics Problems Federal Research Center “Computer Science and Control” Russian Academy of Sciences

Email: zaryadov_is@rudn.university

Zaryadov I. S. - Candidate of Physical and Mathematical Sciences, assistant professor of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University); Senior Researcher of Institute of Informatics Problems of Federal Research Center “Computer Science and Control” Russian Academy of Sciences

44-2 Vavilova St., Moscow, 119333, Russian Federation

K E Samouylov

Department of Applied Probability and Informatics Peoples’ Friendship University of Russia (RUDN University)

Email: samuylov_ke@rudn.university

Samouylov K. E. - professor, Doctor of Engineering Science, head of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University)

6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

E S Sopin

Institute of Informatics Problems Federal Research Center “Computer Science and Control” Russian Academy of Sciences

Email: sopin_es@rudn.university

Sopin E. S. - Candidate of Physical and Mathematical Sciences, assistant professor of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University); Senior Researcher of Institute of Informatics Problems of Federal Research Center “Computer Science and Control” Russian Academy of Sciences

44-2 Vavilova St., Moscow, 119333, Russian Federation

References

  1. R. Nelson, A. N. Tantawi, Approximate Analysis of Fork/Join Synchronization in Parallel Queues, IEEE Transactions on Computers 37 (1988) 739–743.
  2. Thomasian, Analysis of Fork/Join and Related Queueing Systems, ACM Computing Surveys (CSUR) 47 (2) (2014) 17:1–17:71.
  3. Tsimashenka, W. J. Knottenbelt, Reduction of Subtask Dispersion in Fork-Join Systems, in: Computer Performance Engineering, Springer Berlin Heidelberg, 2013, pp. 325–336.
  4. V. Gorbunova, I. S. Zaryadov, S. I. Matyushenko, K. E. Samouylov, S. Ya. Shorgin, The Approximation of Response Time of a Cloud Computing System, Informatics and applications 9 (2015) 32–38, in Russian.
  5. S. V. Vyshenski, P. V. Grigoriev, Yu. Yu. Dubenskaya, Ideal Synchronizer for Marked Pairs in Fork-Join Network, Review of applied and industrial mathematics 15 (3) (2008) 385–399, in Russian.
  6. S. P. Moiseeva, I. A. Ivanovskaya, Analysis of the Mathematical Model of Parallel Service of Mixed Type Requests, Bulletin of the Tomsk Polytechnic University. Control, Computer Science and Technology 317 (5) (2010) 32–34, in Russian.
  7. S. P. Moiseeva, L. A. Zhidkova, Investigation of the Parallel Service System with Multiple Claims of the Poisson Process, Bulletin of the Tomsk Polytechnic University. Control, Computer Science and Technology 17 (4) (2011) 49–54, in Russian.
  8. V. Gorbunova, I. S. Zaryadov, S. I. Matushenko, E. S. Sopin, The Estimation of Probability Characteristics of Cloud Computing Systems with Splitting of Requests, in: Proceedings of the Nineteenth International Scientific Conference Russia: Distributed computer and communication networks: control, computation, communications (DCCN-2016), Vol. 3, 2016, pp. 467–472.
  9. V. Gorbunova, I. S. Zaryadov, S. I. Matushenko, E. S. Sopin, The Estimation of Probability Characteristics of Cloud Computing Systems with Splitting of Requests, in: Proceedings of the 15th International Conference named after A. F. Terpugov: Information technologies and mathematical modelling (ITMM-2016), 2016, pp. 167– 172, in Russian.
  10. M. Mandelbaum, A.-B. Itzhak, Introduction to Queueing with Splitting and Matching, Israel Journal of Technology 6 (5) (1968) 376–382.
  11. Duda, T. Czach´orski, Performance Evaluation of Fork and Join Synchronization Primitives, Acta Informatica 24 (5) (1987) 525–533.
  12. L. Green, A Queueing System in which Customers Require a Random Number of Servers, Operations Research 28 (6) (1980) 1335–1346.
  13. K. J. Omahen, L. Schrage, A Queueing Analysis of a Multiprocessor System with Shared Memory, in: Proc. of the Symposium on Computer Communication Networks and Teletraffic, 1972, pp. 77–88.
  14. Thomasian, A. Avizienis, Dynamic Scheduling of Tasks Requiring Multiple Processors, in: Proceedings of the 11th IEEE Computer Society International Conference (COMPCON’75 Fall), 1975, pp. 77–80.
  15. T. Javidi, Cooperative and Non-Cooperative Resource Sharing in Networks: a Delay Perspective, IEEE Transactions on Automatic Control 53 (9) (2008) 2134–2142.
  16. Kumar, R. Shorey, Performance Analysis and Scheduling of Stochastic Fork-Join Jobs in a Multicomputer System, IEEE Transactions on Parallel and Distributed Systems 10 (4) (1993) 1147–1164.
  17. L. Flatto, S. Hahn, Two Parallel Queues Created by Arrivals with Two Demands I, SIAM Journal on Applied Mathematics 44 (5) (1984) 1041–1053.
  18. G. Bolch, S. Greiner, H. de Meer, K. S. Trivedi, Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications, John Wiley & Sons, 2006.
  19. F. Baccelli, Two Parallel Queues Created by Arrivals with Two Demands: the
  20. W. E. Boyce, R. C. DiPrima, Elementary Differential Equations and Boundary Value Problems, John Wiley & Sons, 2012.
  21. G. P. Basharin, Introduction to Probability Theory, PFUR, Moscow, 1990, in Russian.
  22. P. P. Bocharov, A. V. Pechinkin, Queueing Theory, PFUR, Moscow, 1995, in Russian.
  23. G. P. Basharin, Lectures on the Mathematical Theory of Teletraffic, PFUR, Moscow, 2009, in Russian.
  24. P. P. Bocharov, C. D’Apice, A. V. Pechinkin, S. Salerno, Queueing Theory, Brill Academic Publishers, 2004.
  25. R. E. Barlow, F. Proschan, Statistical Theory of Reliability and Life Testing: Probability Models, John Wiley & Sons, 1981.
  26. E. Varki, A. Merchant, H. Chen, The M|M|1 Fork-Join Queue with Variable Subtasks. URL http://www.cs.unh.edu/~varki/publication/2002-nov-open.pdf
  27. E. Varki, Response Time Analysis of Parallel Computer and Storage Systems, IEEE Transactions on Parallel and Distributed Systems 12 (11) (2001) 1146–1161.
  28. S. Varma, A. M. Makowski, Interpolation Approximations for Symmetric Fork-Join Queues, Performance Evaluation 20 (1994) 245–265.

Copyright (c) 2017 Gorbunova A.V., Zaryadov I.S., Samouylov K.E., Sopin E.S.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies