An approximation for the response time in fork-join queueing networks

Cover Page

Cite item

Full Text

Abstract

An open fork-join queueing network is considered. An arriving job issplit to be serviced into two tasks. The tasks are serviced independently at multiple service-nodes. Each service-node is a queueing system with one server and infinite capacity queue. Service-nodes form a queueing network with an acyclic topology. Two tasks associated with the job synchronize at a join-node before they leave the network. Approximations for the mean time spent by a task in the join-node and the mean response time in the fork-join queueing network are derived by assuming that jobs arrive according to a Poisson process and task service times have an exponential distribution. The accuracy of these approximations is demonstrated by comparing approximate results to simulation results. These approximations can be applied to the analysis of queueing networks with relatively small steady-state workload. The results can be used for the performance analysis of multiprocessor systems and other modern distributed computing systems.

About the authors

Oksana Sergeevna Postnova

Saratov State University

Email: oksana.karpenko.2000@mail.ru
Saratov

Igor Evstaf'evich Tananko

Saratov State University

Email: tanankoie@info.sgu.ru
Saratov

Ekaterina Sergeevna Rogachko

Saratov State University

Email: rogachkoes@info.sgu.ru
Saratov

References

  1. ВИШНЕВСКИЙ В.М. Теоретические основы проектирова-ния компьютерных сетей. – М.: Техносфера, 2003. – 512 с.
  2. КАРПЕНКО О.С., ТАНАНКО И.Е., РОГАЧКО Е.С. Иссле-дование имитационной модели открытой сети массовогообслуживания с делением и слиянием требований // Си-стемы управления, информационные технологии и мате-матическое моделирование : Материалы V Всероссийскойнаучно-практической конференции с международным уча-стием. – Омск: ОмГТУ, 2023. – С. 209–214.
  3. КЛИМЕНОК В.И. Характеристики производительностисистемы массового обслуживания с расщеплением запро-сов // Информатика. – 2023. – Т. 20, №3. – С. 50–60.
  4. ОСИПОВ О.А., ТАНАНКО И.Е. Сети массового обслужи-вания произвольной топологии с делением и слиянием тре-бований: случай бесконечноприборных систем обслужива-ния // Вестник Тверского государственного университета.Серия: Прикладная математика. – 2017. – №4. – С. 43–58.
  5. ЦИЦИАШВИЛИ Г.Ш., ОСИПОВА М.А. Стационарныепотоки в ациклических сетях массового обслуживания //Дальневосточный математический журнал. – 2016. – №2. –С. 223–228.
  6. ENGANTI P., ROSENKRANTZ T., SUN L. et al. ForkMV:Mean-and-variance estimation of fork-join queuing networksfor datacenter applications // IEEE Int. Conf. on Networking,Architecture and Storage (NAS–2022). – Philadelphia, PA,USA, 2022. – P. 1–8.
  7. FLATTO L., HAHN S. Two parallel queues created by arrivalswith two demands I // SIAM Journal on Applied Mathematics. –1984. – Vol. 44, No. 5. – P. 1041—1053.
  8. GORBUNOVA A.V., LEBEDEV A.V. Correlations of thesojourn times of subtasks in fork-join queueing systems withM/M/1-type subsystems // Advances in Systems Science andApplications. – 2024. – Vol. 24, No. 2. – P. 1–18.
  9. GORBUNOVA A.V., LEBEDEV A.V. Nonlinearapproximation of characteristics of a fork-join queueingsystem with Pareto service as a model of parallel structure ofdata processing // Mathematics and Computers in Simulation. –2023. – Vol. 214. – P. 409–428.
  10. GORBUNOVA A.V., LEBEDEV A.V. On estimatingthe characteristics of a fork-join queueing system withPoisson input and exponential service times // Advances inSystems Science and Applications. – 2023. – Vol. 23, No. 2. –P. 99–114.
  11. KEMPER B., MANDJES M. Mean sojourn times in two-queue fork-join systems: bounds and approximations //OR Spectrum. – 2012. – Vol. 34, No. 3. – P. 723—742.
  12. KO S.S., SERFOZO R. Response times in M/M/s fork–joinnetworks // Advances in Applied Probability. – 2004. – Vol. 36,No. 3. – P. 854—871.
  13. LEMOINE A.J. Networks of queues – a survey of equilibriumanalysis // Management Science. – 1977. – Vol. 24, No. 4. –P. 464–481.
  14. MARIN A., ROSSI S., SOTTANA M. Dynamic resourceallocation in fork-join queues // ACM Trans. on Modelingand Performance Evaluation of Computing Systems. – 2020. –Vol. 5, No. 1. – Article No. 3. – P. 1–28.
  15. NELSON R., TANTAWI A.N. Approximate analysisof fork/join synchronization in parallel queues // IEEETrans. on Comp. – 1988. – Vol. 37, No. 6. – P. 739–743.
  16. NGUYEN M., ALESAWI S., LI N. et al. A black-box fork-joinlatency prediction model for data-intensive applications // IEEETrans. on Parallel and Distributed Systems. – 2020. – Vol. 31,No. 9. – P. 1983–2000.
  17. OZKAN E. Control of fork-join processing networks withmultiple job types and parallel shared resources // Mathematicsof Operations Research. – 2022.–Vol.47,No.2.–P.1310–1334.
  18. RAAIJMAKERS Y., BORST S., BOXMA O. Fork–join andredundancy systems with heavy-tailed job sizes // QueueingSystems. – 2023. – Vol. 103, No. 1. – P. 131–159.
  19. SCHOL D., VLASIOU M., ZWART B. Large fork-joinqueues with nearly deterministic arrival and service times //Mathematics of Operations Research. – 2021. – Vol. 47, No. 2. –P. 1335–1364.
  20. THOMASIAN A. Analysis of fork/join and related queueingsystems // ACM Computing Surveys. – 2014. – Vol. 47, No. 2. –Article No. 17. – P. 1–71.
  21. VISHNEVSKY V.M., KLIMENOK V.I., SOKOLOV A.M.et al. Investigation of the fork-join system with Markovianarrival process arrivals and phase-type service time distributionusing machine learning methods // Mathematics. – 2024. –Vol. 12, No. 5. – Article No. 659. – P. 1–22.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Согласие на обработку персональных данных

 

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