A Survey on Queuing Systems with Parallel Servingof Customers. Part II

Cover Page

Cite item

Full Text

Abstract

This paper is a continuation of the survey of the “fork-join” queuing systems (in the westernclassification) or the systems with splitting of queries. Interest in such systems is explainedby a wide range of problems that can be solved with their help, since in fact it is a matter ofparallel processing of data and their applications. For example, this may concern the analysis ofdisk arrays, cloud computing, high-performance services and even the process of picking ordersin a warehouse. In the first part of the survey, the main features of the described model (andrelated systems) and its construction were introduced. Also the detailed description of theapproach to obtaining an accurate expression of the average response time in the case of twodevices was presented as well as several methods of approximate analysis of this characteristic(the case when the number of devices is more than two). This part of the survey is devotedto the description of other existing methods for approximating the average response time. Inparticular, the approaches of the approximate analysis of the response time are as follows: thematrix-geometric method, the analysis with the help of order statistics for various types ofdistribution of the service time of subqueries.

About the authors

A V Gorbunova

Peoples’ Friendship University of Russia (RUDN University)

Author for correspondence.
Email: gorbunova_av@rudn.university

Gorbunova A. V. - Candidate of Physical and Mathematical Sciences, 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

Peoples’ Friendship University of Russia (RUDN University); 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

6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation; 44-2 Vavilova St., Moscow, 119333, Russian Federation

K E Samouylov

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

References

  1. A. V. Gorbunova, I. S. Zaryadov, K. E. Samouylov, E. S. Sopin, A Survey on Queuing Systems with Parallel Serving of Customers, RUDN Journal of Mathematics, Information Sciences and Physics 25 (4) (2017) 350–362, in Russian.
  2. I. Tsimashenka, W. J. Knottenbelt, Reduction of Subtask Dispersion in Fork-Join Systems, in: Computer Performance Engineering, Springer Berlin Heidelberg, 2013, pp. 325–336.
  3. G. P. Basharin, Lectures on the Mathematical Theory of Teletraffic, PFUR, Moscow, 2009, in Russian.
  4. P. P. Bocharov, A. V. Pechinkin, Queueing Theory, PFUR, Moscow, 1995, in Russian.
  5. P. Bocharov, C. D’Apice, A. Pechinkin, S. Salerno, Queueing theory, Brill Academic Publishers, 2004.
  6. E. V. Mokrov, K. E. Samouylov, Modeling of Cloud Computing as a Queuing System with Batch Arrivals, T-Comm — Telecommunications and transport 11 (7) (2013) 139–141, in Russian.
  7. E. V. Mokrov, A. V. Chukarin, Performance Analysis of Cloud Computing System with Live Migration, T-Comm — Telecommunications and transport 8 (8) (2014) 64–67, in Russian.
  8. S. Balsamo, I. Mura, Approximate Response Time Distribution in Fork and Join Systems, SIGMETRICS Performance Evaluation Review 23 (1) (1995) 305–306.
  9. S. Balsamo, I. Mura, On Queue Length Moments in Fork and Join Queuing Networks with General Service Times, Computer Performance Evaluation Modelling Techniques and Tools. LNCS 1245 (1997) 218–231.
  10. S. Balsamo, L. Donatiello, N. M. Van Dijk, Bound Performance Models of Heterogeneous Parallel Processing Systems, IEEE Transactions on Parallel and Distributed Systems 9 (10) (1998) 1041—-1056.
  11. H. G. Perros, On the
  12. M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, Courier Corporation, 1981.
  13. B. M. Rao, M. J. M. Posner, Algorithmic and Approximation Analyses of the Split and Match Queue, Stochastic Models 1 (3) (1985) 433–456.
  14. M. Takahashi, H. ¯ Osawa, T. Fujisawa, On a Synchronization Queue with Two Finite Buffers, Queueing Systems 36 (2000) 107–123.
  15. M. Takahashi, Y. Takahashi, Synchronization Queue with Two MAP Inputs and Finite Buffers, in: Proc. of the Third International Conference on Matrix Analytical Methods in Stochastic Models, 2000, pp. 375–390.
  16. M. S. Squillante, Y. Zhang, A. Sivasubramaniam, N. Gautam, Generalized Parallel- Server Fork-Join Queues with Dynamic Task Scheduling, Annals of Operations Research 160 (1) (2008) 227–255.
  17. G. Joshi, E. Soljanin, G. Wornell, Efficient Redundancy Techniques for Latency Reduction in Cloud Systems, arXiv preprint arXiv:1508.03599.
  18. H. A. David, Order Statistics, Wiley, New York, 1981.
  19. H. A. David, H. N. Nagaraja, Order Statistics, John Wiley & Sons, 2003.
  20. E. J. Gumbel, Statistics of Extremes, Columbia University Press, New York, 1958.
  21. A. O. Allen, Probability, Statistics, and Queueing Theory: With Computer Science Applications, Gulf Professional Publishing, 1990.
  22. L. Kleinrock, Queueing Systems, Volume I: Theory, Wiley Interscience, 1975.
  23. K. S. Trivedi, Probability and Statistics with Reliability, Queueing, and Computer Science Applications (2nd ed.), John Wiley & Sons, 2002.
  24. A. Gravey, A Simple Construction of an Upper Bound for the Mean of the Maximum of
  25. A. V. Gorbunova, I. S. Zaryadov, S. I. Matushenko, E. S. Sopin, The Estimation of Probability Characteristics of Cloud Computing Systems with Splitting of Requests, Distributed Computer and Communication Networks. DCCN 2016. Communications in Computer and Information Science 678 (2016) 418–429.
  26. K. E. Samouylov, I. S. Zaryadov, A. V. Gorbunova, The Response Time Analysis of Cloud Computing System, T-Comm — Telecommunications and transport 9 (11) (2015) 57–61, in Russian.
  27. A. Thomasian, Analysis of Fork/Join and Related Queueing Systems, ACM Computing Surveys (CSUR) 47 (2) (2014) 17:1–17:71.
  28. P. Harrison, Z. S., Queueing Models with Maxima of Service Times, in: Computer Performance Evaluation. Modelling Techniques and Tools, Springer Berlin Heidelberg, 2003, pp. 152–168.
  29. A. Thomasian, J. Menon, RAID5 Performance with Distributed Sparing, IEEE Transactions on Parallel and Distributed Systems 8 (6) (1997) 640–657.
  30. N. L. Johnson, S. Kotz, N. Balakrishnan, Continuous Univariate Distributions, Vol. 1, Wiley Series in Probability and Statistics, 1995
  31. A. S. Lebrecht, W. J. Knottenbelt, Response Time Approximations in Fork-Join Queues, in: In Proceedings of the 23rd Annual UK Performance Engineering Workshop (UKPEW’07), 2007.
  32. B. C. Arnold, Distribution-Free Bounds on the Mean of the Maximum of a Dependent Sample, SIAM Journal on Applied Mathematics 38 (1) (1985) 163–167.
  33. M. Petzold, A Note on the First Moment of Extreme Order Statistics from the Normal Distribution, in: rapport nr.: Seminar Papers, 2000.
  34. A. Thomasian, A. N. Tantawi, Approximate Solutions for

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

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