Характеристики производительности системы массового обслуживания с расщеплением запросов

Цели. Рассматривается задача построения и исследования математической модели стохастической системы с расщеплением и сборкой запросов. Требуется построить процесс функционирования системы, найти условие существования стационарного распределения, предложить алгоритмы его вычисления и основных стационарных характеристик производительности системы. Особый интерес вызывает задача получения нижней и верхней границ математического ожидания времени пребывания запроса в системе.

Методы. Используются методы теории вероятностей, теории массового обслуживания и теории матриц.

Результаты. Функционирование системы описано в терминах многомерной цепи Маркова. Найдено конструктивное условие существования стационарного распределения, предложены алгоритмы его вычисления и стационарных характеристик производительности системы. Получены аналитические выражения для нижней и верхней границ математического ожидания времени пребывания запросов в системе.

Заключение. Исследован стационарный режим функционирования системы массового обслуживания с расщеплением и сборкой запросов, поступающих в систему в стационарном пуассоновском потоке. Каждый из поступающих запросов расщепляется на два задания, которые идут в две подсистемы, состоящие из обслуживающего прибора и буфера. Времена обслуживания заданий имеют разные фазовые распределения (PH-Phase type distributions). Для данной системы найдено условие существования стационарного распределения, предложены алгоритмы вычисления стационарного распределения и ряда стационарных характеристик производительности системы. Получены аналитические выражения для нижней и верхней границ математического ожидания времени пребывания запроса в системе от момента его поступления в систему до момента синхронизации, которое является критическим показателем производительности системы с расщеплением и сборкой запросов.

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.