Nonlinear approximation of quantiles of the response time distribution of a fork-join queueing system with M|M|1 subsystems | Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitelnaja tehnika i informatika – Tomsk State University Journal of Control and Computer Science. 2025. № 72. DOI: 10.17223/19988605/72/2

Nonlinear approximation of quantiles of the response time distribution of a fork-join queueing system with M|M|1 subsystems

A fork-join queueing system with a Poisson input flow and exponential distribution of service time on servers is considered. Using this queuing system, various types of physical structures are modeled in which the original problem is divided into parts to reduce the solution time. The paper proposes an analytical estimate for the distribution quantiles of one of the most important performance indicators of such systems - the system response time, i.e., the time a request stays in the system. The derivation of the expression is based on elements of the copula theory, their diagonal sections, and on simulation modeling of a fork-join queueing system. The author declares no conflicts of interests.

Download file

Keywords

fork-join queueing system, average response time, distribution quantiles, copula, diagonal section, simulation modeling

Authors

Name	Organization	E-mail
Gorbunova Anastasia V.	V.A. Trapeznikov Institute of Control Sciences of the Russian Academy of Sciences	avgorbunova@list.ru

Всего: 1

References

Горбунова А.В., Лебедев А.В. О новом подходе к оценке квантилей времени отклика системы с разделением и параллельным обслуживанием заявок // Управление большими системами: сборник трудов (электронный журнал). 2024. № 108. С. 6-21. doi: 10.25728/ubs.2024.108.1.

Gorbunova A.V., Lebedev A.V. Copulas and quantiles in Fork-Join queueing systems // Advances in Systems Science and Appli cations. V. 24 (1). P. 1-19. doi: 10.25728/assa.2024.24.1.1585.

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. V. 24 (2). P. 1-18. doi: 10.25728/assa.2024.2024.02.1641.

Gorbunova A.V., Lebedev A.V. Nonlinear approximation of characteristics of a Fork-Join queueing system with pareto service as a model of parallel structure of data processing // Mathematics and Computers in Simulation. 2023. V. 214. P. 409-428. doi: 10.1016/j.matcom.2023.07.029.

Nelson R., Tantawi A.N. Approximate analysis of fork/join synchronization in parallel queues // IEEE Transactions on Computers. 1988. V. 37 (6). P. 739-743. doi: 10.1109/12.2213.

Varma S., Makowski A.M.Interpolation approximations for symmetric Fork-Join queues // Performance Evaluation. 1994. V. 20. P. 245-265. doi: 10.1016/0166-5316(94)90016-7.

Kemper B., Mandjes M. Mean sojourn time in two-queue fork-join systems: Bounds and approximations // OR Spectrum. 2012. V. 34. P. 723-742. doi: 10.1007/s00291-010-0235-y.

Thomasian A. Analysis of fork/join and related queueing systems // ACM Computing Surveys (CSUR). 2014. V. 47 (2). P. 1-71. doi: 10.1145/2628913.

Qiu Zh., Perez J.F., Harrison P.G. Beyond the mean in fork-join queues: Efficient approximation for response-time tails // Perfor mance Evaluation. 2015. V. 91. P. 99-116. doi: 10.1016/j.peva.2015.06.007.

Nguyen M., Alesawi S., Li N., Che H., Jiang H. A black-box Fork-Join latency prediction model for data-intensive applications // IEEE Transactions on Parallel and Distributed Systems. 2020. V. 31 (9). P. 1983-2000. doi: 10.1109/TPDS.2020.2982137.

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 // Proc. IEEE International Conference on Networking, Architecture and Storage (NAS). 2022. P. 1-8. doi: 10.1109/NAS55553.2022.9925531.

Sethuraman S. Analysis of Fork-Join Systems: Network of Queues with Precedence Constraints. Boca Raton : CRC Press, 2022. 104 p.

Жидкова Л.А., Моисеева С.П. Исследование системы параллельного обслуживания кратных заявок простейшего потока // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2011. Т. 17, № 4. С. 49-54.

Моисеева С.П., Панкратова Е.В., Убонова Е.Г. Исследование бесконечнолинейной системы массового обслуживания с разнотипным обслуживанием и входящим потоком марковского восстановления // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2016. Т. 35, № 2. С. 46-53. doi: 10.17223/19988605/35/5.

Nelsen R. An introduction to copulas. Berlin : Springer, 2006. 269 p.

Лебедев А.В. Верхняя граница среднего минимума зависимых случайных величин с известным коэффициентом Кендалла // Теория вероятностей и ее применения. 2019. Т. 64, вып. 3. С. 578-589. doi: 10.4213/tvp5199.

Nelder J.A., Mead R. A Simplex Method for Function Minimization // Computer Journal. 1965. V. 7 P. 308-313.

Колмогоров А.Н. О представлении непрерывных функций нескольких переменных в виде суперпозиции непрерывных функций одного переменного и сложения // Доклады АН СССР. 1957. Т. 114, № 5. С. 953-956.

Арнольд В.И. О представлении функций нескольких переменных в виде суперпозиции функций меньшего числа переменных // Математическое просвещение. 1958. № 3. С. 41-61.

Горбань А.Н. Обобщенная аппроксимационная теорема и вычислительные возможности нейронных сетей // Сибирский журнал вычислительной техники. 1998. Т. 1, № 1. С. 11-24.

Бутырский Е.Ю., Кувалдин И.А., Чалкин В.П. Аппроксимация многомерных функций // Научное приборостроение. 2010. Т. 20, № 2. С. 82-92.