On a new approach to estimating response time quantiles of a fork-join queueing system

封面

如何引用文章

全文:

详细

The article proposes a new approach to estimating the quantiles of the response time distribution of the fork-join queueing system. We consider a classic version of this system with a Poisson input flow and exponential service times on homogeneous servers. Upon receipt of tasks into the system, they are instantly divided into a fixed number of subtasks and sent for service to the appropriate subsystem with an unlimited capacity storage device and one server. The task is considered served after all its components have been serviced. This system allows you to simulate many real processes, which, in order to increase efficiency, are characterized by dividing large tasks into smaller components, for example, parallel or distributed computing systems. The difficulty of analyzing systems lies in the presence of a dependence between the sojourn times of subtasks, which significantly complicates the analysis of all performance characteristics of such systems. The main contribution of the article is the approach to determining the quantiles of the response time distribution, the assessment of which is no less valuable than the assessment of the mean response time. At the same time, a much larger number of works in this area are devoted to calculating the mean, which is explained, among other things, by the complexity of carrying out such an analysis even for a given characteristic, and estimating quantiles seems to be an even more laborious task.

作者简介

Anastasia Gorbunova

V.A. Trapeznikov Institute of Control Sciences of RAS

Email: avgorbunova@list.ru
Moscow

Alexey Lebedev

Lomonosov Moscow State University

Email: avlebed@yandex.ru
Moscow

参考

  1. ARMONY M., ISRAELIT S., MANDELBAUM A.,MARMOR Y.N. et al. Patient flow in hospitals: a data-based queueing-science perspective // Stochastic Systems. –2015. – Vol. 5, No. 1. – P. 146–194.
  2. BACCELLI F., MAKOWSKI A.M. Queueing models forsystems with synchronization constraints // Proc. of the IEEE. –1989. – Vol. 77, No. 1. – P. 138–161.
  3. BARON O., KRASS D., SHERZER E., SENDEROVICH A.Can machines solve general queueing problems? // WinterSimulation Conference (WSC) – 2022. – P. 2830–2841.
  4. CHOCRON E., COHEN I., FEIGIN P. Delay predictionfor managing multiclass service systems: An investigation ofqueueing theory and machine learning approaches // IEEETrans. on Engineering Management. – 2022. — P. 1–11.
  5. DIELEMAN A., BERKHOUT A., HEIDERGOTT B. A neuralnetwork approach to performance analysis of tandem lines:The value of analytical knowledge // Computers & OperationsResearch. – 2023. – Vol. 152. – P. 106–124.
  6. ENGANTI P., ROSENKRANTZ T., SUN L., WANG Z. et al.ForkMV: Mean-and-Variance Estimation of Fork-Join QueuingNetworks for Datacenter Applications // IEEE Int. Conf. onNetworking, Architecture and Storage (NAS). – 2022. – P. 1–8.
  7. GALLIEN J., WEIN L.M. A simple and effective componentprocurement policy for stochastic assembly Systems // QueueingSystems. – 2001. – Vol. 38. – P. 221–248.
  8. GORBUNOVA A.V., LEBEDEV A.V. Bivariate distributionsof maximum remaining service times in fork-join infinite-serverqueues // Probl. Inf. Transm. – 2020. –Vol. 56, No. 1. – P. 73–90. – DOI: https://doi.org/10.1134/S003294602001007X.
  9. GORBUNOVA A.V., LEBEDEV A.V. Nonlinearapproximation of characteristics of a fork–join queueingsystem with Pareto service as a model of parallel structureof data processing // Mathematics and Computers inSimulation. – 2023. – Vol. 214. – P. 409–428. – DOI:https://doi.org/10.1016/j.matcom.2023.07.029.
  10. GORBUNOVA A.V., LEBEDEV A.V. On estimating thecharacteristics of a fork-join queueing system with Poissoninput and exponential service times // Advances in SystemsScience and Applications. – 2023. – Vol. 23, No. 2. –P. 99–114. – DOI: https://doi.org/10.25728/assa.2023.23.2.1351.
  11. GORBUNOVA A.V., VISHNEVSKY V.M. Estimating theresponse time of a cloud computing system with the helpof neural networks // Advances in Systems Science andApplications. – 2020. – Vol. 20, No. 3. – P. 105–112.
  12. JIANG L., GIACHETTI R.E. A queueing network model toanalyze the impact of parallelization of care on patient cycletime // Health Care Management Science. – 2008. – Vol. 11. –P. 248–261.
  13. LEBEDEV A.V. Upper bound for the expected minimum ofdependent random variables with known Kendall’s tau // Theoryof Probability and Its Applications. – 2019. – Vol. 64, No. 3. –P. 465—473.
  14. LEBEDEV A.V. On the Interrelation between DependenceCoefficients of Bivariate Extreme Value Copulas // MarkovProc. Relat. Fields. – 2019. – Vol. 25, No. 4. – P. 639–648.
  15. NELSEN R.B. An introduction to copulas. – Springer Science& Business Media, 2007. – 272 p.
  16. NELSON R., TANTAWI A.N. Approximate analysis offork/join synchronization in parallel queues // IEEE Trans.Comput. – 1988. – Vol. 37, No. 6. – P. 739–743.
  17. NGUYEN M., ALESAWI S., LI S., CHE S. et al. Ablack-box fork-join latency prediction model for data-intensiveapplications // IEEE Trans. on Parallel and DistributedSystems. – 2020. – Vol. 31, No. 9. – P. 1983–2000.
  18. QIU ZH., PEREZ J.F., HARRISON P.G. Beyond the meanin fork-join queues: Efficient approximation for response-timetails // Performance Evaluation. – 2015. – Vol. 91. – P. 99–116.
  19. VISHNEVSKY V.M., GORBUNOVA A.V. Application ofmachine learning methods to solving problems of queuingtheory // Communications in Computer and InformationScience. – 2022. – Vol. 1605. – P. 304–316. – DOI:https://doi.org/10.1007/978-3-031-09331-9_24.
  20. SCHOL D., VLASIOU M., ZWART B. Large fork-joinqueues with nearly deterministic arrival and service times //Mathematics of Operations Research. – 2022. – Vol. 47, No. 2. –P. 1335–1364. – DOI: https://doi.org/10.1287/moor.2021.1171.

补充文件

附件文件
动作
1. JATS XML


Creative Commons License
此作品已接受知识共享署名-非商业性使用 4.0国际许可协议的许可。

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

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

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».