An approximation for the response time in fork-join queueing networks
- 作者: Postnova O.S.1, Tananko I.E.1, Rogachko E.S.1
-
隶属关系:
- Saratov State University
- 期: 编号 115 (2025)
- 页面: 33-51
- 栏目: Systems analysis
- URL: https://bakhtiniada.ru/1819-2440/article/view/306190
- ID: 306190
如何引用文章
全文:
详细
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.
作者简介
Oksana Postnova
Saratov State University
Email: oksana.karpenko.2000@mail.ru
Saratov
Igor Tananko
Saratov State University
Email: tanankoie@info.sgu.ru
Saratov
Ekaterina Rogachko
Saratov State University
Email: rogachkoes@info.sgu.ru
Saratov
参考
- ВИШНЕВСКИЙ В.М. Теоретические основы проектирова-ния компьютерных сетей. – М.: Техносфера, 2003. – 512 с.
- КАРПЕНКО О.С., ТАНАНКО И.Е., РОГАЧКО Е.С. Иссле-дование имитационной модели открытой сети массовогообслуживания с делением и слиянием требований // Си-стемы управления, информационные технологии и мате-матическое моделирование : Материалы V Всероссийскойнаучно-практической конференции с международным уча-стием. – Омск: ОмГТУ, 2023. – С. 209–214.
- КЛИМЕНОК В.И. Характеристики производительностисистемы массового обслуживания с расщеплением запро-сов // Информатика. – 2023. – Т. 20, №3. – С. 50–60.
- ОСИПОВ О.А., ТАНАНКО И.Е. Сети массового обслужи-вания произвольной топологии с делением и слиянием тре-бований: случай бесконечноприборных систем обслужива-ния // Вестник Тверского государственного университета.Серия: Прикладная математика. – 2017. – №4. – С. 43–58.
- ЦИЦИАШВИЛИ Г.Ш., ОСИПОВА М.А. Стационарныепотоки в ациклических сетях массового обслуживания //Дальневосточный математический журнал. – 2016. – №2. –С. 223–228.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- LEMOINE A.J. Networks of queues – a survey of equilibriumanalysis // Management Science. – 1977. – Vol. 24, No. 4. –P. 464–481.
- 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.
- NELSON R., TANTAWI A.N. Approximate analysisof fork/join synchronization in parallel queues // IEEETrans. on Comp. – 1988. – Vol. 37, No. 6. – P. 739–743.
- 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.
- 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.
- RAAIJMAKERS Y., BORST S., BOXMA O. Fork–join andredundancy systems with heavy-tailed job sizes // QueueingSystems. – 2023. – Vol. 103, No. 1. – P. 131–159.
- 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.
- THOMASIAN A. Analysis of fork/join and related queueingsystems // ACM Computing Surveys. – 2014. – Vol. 47, No. 2. –Article No. 17. – P. 1–71.
- 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.
补充文件
