Performance characteristics of the fork-join queuing system

Objectives. The problem of investigating a fork-join queuing system is considered. It is required to build the process of the system functioning, to find the condition for the existence of a stationary distribution, and propose algorithms for calculating the stationary distribution and the main stationary performance characteristics. The special interest of the study is to obtain the lower and upper bounds of the mean sojourn time of a customer in the system.

Methods. Methods of probability theory, queuing theory and matrix theory are used.

Results. The functioning of the system is described in terms of a multidimensional Markov chain. A constructive condition for the existence of a stationary distribution is found, and algorithms for calculating the stationary distribution and stationary performance characteristics of the system are proposed. Analytical expressions are obtained for the lower and upper bounds of the mean sojourn time of customers in the system.

Conclusion. The functioning of the fork-join queuing system with a stationary Poisson flow has been studied. Each of the arriving customers forks into two tasks that go to two subsystems, each of which consists of a server and a buffer. We assume that the buffer to one of the servers is unlimited, and to the second server has a finite volume. Service times have, generally speaking, different phase distributions (PH-Phase type distributions). For this system, a condition for the existence of a stationary distribution is obtained, algorithms for calculating the stationary distribution and a number of stationary performance measures of the system are proposed. Analytical expressions for the lower and upper bounds of the mean sojourn time of a customer in the system from the moment it enters the system to the moment of synchronization, which is a critical performance indicator of the fork-join queues, are obtained. The results of the study can be used for modeling various computer and communication systems, in particular, systems that perform parallel computing, customer processing in distributed databases, and parallel disk access.

1. Flatto L., Hahn S. Two parallel queues created by arrivals with two demands. SIAM Journal on Applied Mathematics, 1984, vol. 44, pp. 1041-1053.

2. Nelson R., Tantawi A. N. Approximate analysis of fork/join synchronization in parallel queues. IEEE Transactions on Computers, 1988, vol. 37, pp. 739-743.

3. Kim C., Agrawala A. K. Analysis of the fork-join queue. IEEE Transactions on Computers, 1989, vol. 38, pp. 250-255.

4. Qiu Z., Juan P., Harrison H. G. Beyond the mean in fork-join queues: Efficient approximation for response-time tails. Performance Evaluation, 2015, vol. 91, pp. 99-116.

5. Lui J. C.-S., Muntz R. R., Towsley D. Computing Performance Bounds for Fork-Join Queueing Models. Los Angeles, University of California, Computer Science Department, 1994, 38 р.

6. Varma S., Makowski A. M. Interpolation approximations for symmetric fork-join queues. Performance Evaluation, 1994, vol. 20, pp. 245-265.

7. Ko S.-S., Serfozo R. F. Response times in M/M/s fork-join networks. Advances in Applied Probability, 2004, vol. 36, pp. 854-871.

8. Ko S.-S., Serfozo R. F. Sojourn times in G/M/1 fork-join networks. Naval Research Logistics, 2008, vol. 55, pp. 432-443.

9. Thomasian A. Analysis of fork/join and related queueing systems. ACM Computing Surveys, 2014, vol. 47, pp. 1-71.

10. Wang W., Harchol-Balter M., Jiang H., Scheller-Wolf A., Srikant R. Delay asymptotics and bounds for multitask parallel jobs. ACM SIGMETRICS Performance Evaluation Review, 2018, vol. 46, pp. 2-7.

11. Lee K., Shah N. B., Huang L., Ramchandran K. TheMDS queue: analysing the latency performance of erasure codes. IEEE Transactions on Information Theory, 2017, vol. 63, pp. 2822-2842.

12. Rizk A., Poloczek F., Ciucu F. Stochastic bounds in fork-join queueing systems under full and partial mapping. Queueing Systems, 2016, vol. 83, pp. 261-291.

13. Baccelli F., Makowski A. M., Shwartz A. The fork-join queue and related systems with synchronization constraints: stochastic ordering and computable bounds. Advances in Applied Probability, 1989, vol. 21, pp. 629-660.

14. Balsamo S., Donatiello L., Van Dijk N. M. Bound performance models of heterogeneous parallel processing systems. IEEE Transactions on Parallel and Distributed Systems, 1998, vol. 9, pp. 1041-1056.

15. Neuts M. F. Matrix-Geometric Solutions in Stochastic Models. Baltimore, The Johns Hopkins University Press, 1981, 352 p.

16. Dudin A. N., Klimenok V. I., Vishnevsky V. M. The theory of queuing systems with correlated flows. Springer, 2020, 430 р.

17. Graham A. Kronecker Products and Matrix Calculus with Applications. Ellis Horwood, Cichester, 1981, 130 р.

18. Ozawa T. Sojourn time distributions in the queue defined by a general QBD process. Queueing Systems, 2006, vol. 53, pp. 203–211.