Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Postnova O. S., Tananko I. E., Rogachko E. S. Calculation of time characteristics for acyclic fork-join queueing network. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2026, vol. 26, iss. 3, pp. 448-458. DOI: 10.18500/1816-9791-2026-26-3-448-458, EDN: XUBEEY

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
31.08.2026
Full text:
download
(downloads: 53)
Language: 
Russian
Heading: 
Computer Sciences
Article type: 
Article
UDC: 
519.872
DOI: 
10.18500/1816-9791-2026-26-3-448-458
EDN: 
XUBEEY

Calculation of time characteristics for acyclic fork-join queueing network

Autors: 
Postnova Oksana Sergeevna, Saratov State University
Tananko Igor Evstaf'evich, Saratov State University
Rogachko Ekaterina Sergeevna, Saratov State University
Abstract: 

An open acyclic fork-join queueing network is considered. When a job arrives from a source into the network, it is split to be serviced into a given constant number of associated tasks. The tasks are routed between service-nodes independently of each other and independently of tasks associated with other jobs. Upon leaving the queuing network, all tasks enter a node called the join-node, where associated tasks join into a job. A method is proposed for calculating the mean time spent by a task in the join-node and the mean response time in the fork-join queueing network. For the case of so-called uniform workload distribution in the queueing network, the calculation of the mean response time in the queueing network is described. Uniform workload distribution is determined by equal route lengths of tasks in the queuing network, equal probabilities of these routes, as well as equal service rates in the service-nodes, proportional to the number of tasks associated with jobs. A comparison of numerical results obtained in computational experiments using analytical and simulation models of a fork-join queueing network is presented. The results can be used to evaluate the time characteristics of the operation of multiprocessor systems, cloud computing systems and other stochastic systems modeled by fork-join queueing networks.

Key words: 
fork-join queueing network
acyclic queueing network
task service
time spent by task in join-node
response time in queueing network
References: 
  1. Thomasian A. Analysis of fork/join and related queueing systems. ACM Computing Surveys, 2014, vol. 47, iss. 2, art. 17, pp. 1–71. DOI: https://doi.org/10.1145/2628913
  2. Gorbunova A. V., Zaryadov I. S., Samouylov K. E., Sopin E. S. A survey on queuing systems with parallel serving of customers. RUDN Journal of Mathematics, Information Sciences and Physics, 2017, vol. 25, iss. 4, pp. 350–362 (in Russian). DOI: https://doi.org/10.22363/2312-9735-2017-25-4-350-362, EDN: ZVFIPZ
  3. Enganti P., Rosenkrantz T., Sun L., Wang Z., Che H., Jiang H. ForkMV: Mean-and-variance estimation of fork-join queuing networks for datacenter applications. IEEE International Conference on Networking, Architecture and Storage, 2022, pp. 1–8. DOI: https://doi.org/10.1109/NAS55553.2022.9925531
  4. Flatto L., Hahn S. Two parallel queues created by arrivals with two demands I. SIAM Journal on Applied Mathematics, 1984, vol. 44, iss. 5, pp. 1041–1053. DOI: https://doi.org/10.1137/0144074
  5. Flatto L. Two parallel queues created by arrivals with two demands II. SIAM Journal on Applied Mathematics, 1985, vol. 45, iss. 5, pp. 861–878. DOI: https://doi.org/10.1137/0145052
  6. Ko S.-S., Serfozo R. F. Response times in M/M/s fork–join networks. Advances in Applied Probability, 2004, vol. 36, iss. 3, pp. 854–871. DOI: https://doi.org/10.1239/aap/1093962238
  7. Ko S.-S., Serfozo R. F. Sojourn times in G/M/1 fork-join networks. Naval Research Logistics, 2008, vol. 55, iss. 5, pp. 432–443. DOI: https://doi.org/10.1002/nav.20294
  8. Thomasian A., Tantawi A. N. Approximate solutions for M/G/1 fork/join synchronization. Proceedings of Winter Simulation Conference, 1994, pp. 361–368. DOI: https://doi.org/10.1109/WSC.1994.717194
  9. Gorbunova A. V., Lebedev A. V. Correlations of the sojourn times of subtasks in fork-join queueing systems with M/M/1-type subsystems // Advances in Systems Science and Applications, 2024, vol. 24, iss. 2, pp. 1–18.
  10. 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, iss. 10, pp. 1041–1056. DOI: https://doi.org/10.1109/71.730531
  11. Arns M. A tool for the analysis of hierarchical service-oriented extended open fork/join queueing networks. 1st International ICST Workshop on Tools for Solving Structured Markov Chains, 2010, pp. 1–9. DOI: https://doi.org/10.4108/smctools.2007.1910
  12. Baccelli F., Makowski A. Simple computable bounds for the fork-join queue. Proceedings of Information Science and Systems Conference, 1985, pp. 436–441.
  13. Schol D., Vlasiou M., Zwart B. Extreme values for the waiting time in large fork-join queues. Queueing Systems, 2025, vol. 109, art. 9. DOI: https://doi.org/10.1007/s11134-025-09937-2
  14. Osipov O. A., Tananko I. E. Fork-join queueing networks with an arbitrary topology: The infinite server case. Vestnik TvGU. Seriya: Prikladnaya Matematika [Herald of Tver State University. Series: Applied Mathematics], 2017, iss. 4, pp. 43–58 (in Russian). DOI: https://doi.org/10.26456/vtpmk188, EDN: ZXRLIF
  15. Baynat B., Dallery Y. An approximation method for general closed queuing networks with fork-join mechanisms. Journal of the Operational Research Society, 2000, vol. 51, iss. 2, pp. 198–208. DOI: https://doi.org/10.1057/palgrave.jors.2600885
  16. Baccelli F., Massey W., Towsley D. Acyclic fork-join queuing networks. Journal of the ACM, 1989, vol. 36, iss. 3, pp. 615–642. DOI: https://doi.org/10.1145/65950.65957
  17. Tancrez J.-S., Chevalie P., Sema P. A tight bound on the throughput of queueing networks with blocking. In: Dudin A., de Turck K. (eds.) Analytical and Stochastic Modeling Techniques and Applications (ASMTA 2013). Lecture Notes in Computer Science, vol. 7984. Springer, Berlin, Heidelberg, 2013, pp. 396–415. DOI: https://doi.org/10.1007/978-3-642-39408-9_28
  18. Dallery Y., Towsley D., Liu Z. Properties of fork/join queueing networks with blocking under various operating mechanisms. IEEE Transactions on Robotics and Automation, 1997, vol. 13, iss. 4, pp. 503–518. DOI: https://doi.org/10.1109/70.611303
  19. Xia C. H., Liu Z., Towsley D., Lelarge M. Scalability of fork/join queueing networks with blocking. ACM SIGMETRICS Performance Evaluation Review, 2007, vol. 35, iss. 1, pp. 133–144. DOI: https://doi.org/10.1145/1269899.1254898
  20. Yannopoulos E., Alfa A. S. A simple and quick approximation algorithm for tandem, split and merge queueing networks with blocking. INFOR: Information Systems and Operational Research, 1994, vol. 32, iss. 4, pp. 288–308. DOI: https://doi.org/10.1080/03155986.1994.11732258
  21. Osipov O. A. Analysis of fork/join queueing networks with retrials. Tomsk State University Journal of Control and Computer Science, 2018, iss. 43, pp. 49–55 (in Russian). DOI: https://doi.org/10.17223/19988605/43/6, EDN: XQWQHJ
  22. Marin A., Rossi S., Sottana M. Dynamic resource allocation in fork-join queues. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 2020, vol. 5, iss. 1, pp. 1–28. DOI: https://doi.org/10.1145/3372376
  23. Özkan E. Control of fork-join processing networks with multiple job types and parallel shared resources. Mathematics of Operations Research, 2021, vol. 47, iss. 2, pp. 1310–1334. DOI: https://doi.org/10.1287/moor.2021.1170
  24. Postnova O. S., Tananko I. E., Rogachko E. S. An approximation for the response time in fork-join queueing networks. Large-Scale Systems Control, 2025, iss. 115, pp. 33–51 (in Russian). EDN: HVKWYL
  25. Ventsel’ E. S., Ovcharov L. A. Teoriya veroyatnostey i yeye inzhenernye prilozheniya [Probability theory and its engineering applications]. Moscow, Nauka, 1988. 480 p. (in Russian).
  26. He Q.-M. Fundamentals of matrix-analytic methods. New York, Springer Science+Business Media, 2014. 363 p. DOI: https://doi.org/10.1007/978-1-4614-7330-5
  27. Embrechts P., Klüppelberg C., Mikosch T. Modelling extremal events for insurance and finance. Stochastic Modelling and Applied Probability (SMAP, vol. 33). Berlin, Heidelberg, Springer-Verlag, 1997. 648 p. DOI: https://doi.org/10.1007/978-3-642-33483-2
  28. Postnova O. S., Tananko I. E. Imitatsionnaya model’ setey massovogo obsluzhivania s deleniem i sliyaniem trebovaniy [Simulation model of fork-join queueing networks]. Certificate of state registration of a computer program RU 2025660299. EDN: KQEPPO
Received: 
06.05.2026
Accepted: 
11.06.2026
Published: 
31.08.2026
  • 118 reads