A Survey on Queuing Systems with Parallel Servingof Customers

Cover Page

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.


A V Gorbunova

Principal contact for editorial correspondence.
gorbunova_av@rudn.university
Department of Applied Probability and Informatics Peoples’ Friendship University of Russia (RUDN University) 6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

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

I S Zaryadov

zaryadov_is@rudn.university
Institute of Informatics Problems Federal Research Center “Computer Science and Control” Russian Academy of Sciences 44-2 Vavilova St., Moscow, 119333, Russian Federation

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

K E Samouylov

samuylov_ke@rudn.university
Department of Applied Probability and Informatics Peoples’ Friendship University of Russia (RUDN University) 6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

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

E S Sopin

sopin_es@rudn.university
Institute of Informatics Problems Federal Research Center “Computer Science and Control” Russian Academy of Sciences 44-2 Vavilova St., Moscow, 119333, Russian Federation

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

  • R. Nelson, A. N. Tantawi, Approximate Analysis of Fork/Join Synchronization in Parallel Queues, IEEE Transactions on Computers 37 (1988) 739–743.
  • Thomasian, Analysis of Fork/Join and Related Queueing Systems, ACM Computing Surveys (CSUR) 47 (2) (2014) 17:1–17:71.
  • Tsimashenka, W. J. Knottenbelt, Reduction of Subtask Dispersion in Fork-Join Systems, in: Computer Performance Engineering, Springer Berlin Heidelberg, 2013, pp. 325–336.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • M. Mandelbaum, A.-B. Itzhak, Introduction to Queueing with Splitting and Matching, Israel Journal of Technology 6 (5) (1968) 376–382.
  • Duda, T. Czach´orski, Performance Evaluation of Fork and Join Synchronization Primitives, Acta Informatica 24 (5) (1987) 525–533.
  • L. Green, A Queueing System in which Customers Require a Random Number of Servers, Operations Research 28 (6) (1980) 1335–1346.
  • 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.
  • 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.
  • T. Javidi, Cooperative and Non-Cooperative Resource Sharing in Networks: a Delay Perspective, IEEE Transactions on Automatic Control 53 (9) (2008) 2134–2142.
  • 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.
  • L. Flatto, S. Hahn, Two Parallel Queues Created by Arrivals with Two Demands I, SIAM Journal on Applied Mathematics 44 (5) (1984) 1041–1053.
  • 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.
  • F. Baccelli, Two Parallel Queues Created by Arrivals with Two Demands: the
  • W. E. Boyce, R. C. DiPrima, Elementary Differential Equations and Boundary Value Problems, John Wiley & Sons, 2012.
  • G. P. Basharin, Introduction to Probability Theory, PFUR, Moscow, 1990, in Russian.
  • P. P. Bocharov, A. V. Pechinkin, Queueing Theory, PFUR, Moscow, 1995, in Russian.
  • G. P. Basharin, Lectures on the Mathematical Theory of Teletraffic, PFUR, Moscow, 2009, in Russian.
  • P. P. Bocharov, C. D’Apice, A. V. Pechinkin, S. Salerno, Queueing Theory, Brill Academic Publishers, 2004.
  • R. E. Barlow, F. Proschan, Statistical Theory of Reliability and Life Testing: Probability Models, John Wiley & Sons, 1981.
  • 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
  • E. Varki, Response Time Analysis of Parallel Computer and Storage Systems, IEEE Transactions on Parallel and Distributed Systems 12 (11) (2001) 1146–1161.
  • S. Varma, A. M. Makowski, Interpolation Approximations for Symmetric Fork-Join Queues, Performance Evaluation 20 (1994) 245–265.

Views

Abstract - 585

PDF (Russian) - 565


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.