Estimates of the copula and quantiles of the response time distribution for a fork-join queueing system with the pareto distribution of service time
- Authors: Gorbunova A.V.1
-
Affiliations:
- V.A. Trapeznikov Institute of Control Sciences of RAS
- Issue: No 112 (2024)
- Pages: 7-29
- Section: Systems analysis
- URL: https://ogarev-online.ru/1819-2440/article/view/284207
- ID: 284207
Cite item
Full Text
Abstract
A fork-join queueing system is considered. It is assumed that the service time distribution on all servers has a Pareto distribution. The dependence between the sojourn times of subtasks in subsystems is studied, which is the main reason for the complexity of analyzing such systems. The sojourn time of a task in the system (or the average response time) is the maximum of the dependent random variables of the sojourn time of subtasks in the system. Approximations of the joint distribution of the sojourn times of subtasks are obtained using copula theory. An approach is also proposed for determining the quantiles of the system response time distribution using a diagonal section of copulas. This approach was previously used to analyze a similar system, but with an exponential distribution of service time. However, the main difference between the system under study and the exponential case is that the type of the distribution function of the sojourn time of a subtask in the subsystem is unknown. Therefore, an analytical approximation is used for the quantiles of the response time distribution in the subsystem under the assumption that the distribution of the time of stay of a subtask in the subsystem is approximated by the Frechet distribution obtained earlier. The estimates obtained for the quantiles and copula of the response time distribution show good agreement with the simulation data.
About the authors
Anastasia Vladimirovna Gorbunova
V.A. Trapeznikov Institute of Control Sciences of RAS
Email: avgorbunova@list.ru
Moscow
References
- ГОРБУНОВА А.В., ЛЕБЕДЕВ А.В. Квантили распределе-ния времени отклика в fork-join системах с распределениемПарето времени обслуживания // Вестник ВГУ. Серия: Си-стемный анализ и информационные технологии. – 2024. –№3. – С. 5–16.
- ARMONY M., ISRAELIT S., MANDELBAUM A. et al.Patient flow in hospitals: a data-based queueing-scienceperspective // Stochastic Systems. – 2015. – Vol. 5, No. 1. –P. 146–194.
- BACCELLI F., MAKOWSKI A.M. Queueing models forsystems with synchronization constraints // Proc. of the IEEE. –1989. – Vol. 77, No. 1. – P. 138-161.
- 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. – P. 1–8.
- GALLIEN J., WEIN L.M. A simple and effective componentprocurement policy for stochastic assembly Systems // QueueingSystems. – 2001. – Vol. 38. – P. 221–248.
- 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.
- GORBUNOVA A.V., LEBEDEV A.V. Copulas and quantilesin fork-join queueing Systems // Advances in Systems Scienceand Applications. – 2024. – Vol. 24, No. 1. –1–19.
- GUDENDORF G., SEGERS J. Extreme-Value Copulas //In: Copula theory and Its Application. – Springer, 2010. –P. 127–145.
- LEBEDEV A.V. On the Interrelation between DependenceCoefficients of Bivariate Extreme Value Copulas // MarkovProc. Relat. Fields. – 2019. – Vol. 25, No. 4. – P. 639–648.
- MCNEIL A.J., FREY R., EMBRECHTS P. Quantitative riskmanagement. – Princeton: Princeton University Press, 2005. –538 p.
- NELDER J.A., MEAD R. A simplex method for functionminimization // The Computer Journal. – 1965. – Vol. 7. –P. 308–313.
- NELSEN R.B. An introduction to copulas. – Springer Science &Business Media, 2007. – 272 p.
- NELSON R., TANTAWI A.N. Approximate analysis offork/join synchronization in parallel queues // IEEE Trans.Comput. – 1988. – Vol. 37, No. 6. – P. 739–743.
- NGUYEN M., ALESAWI S., LI N. et al. ForkTail: A black-box fork-join tail latency prediction model for user-facingdatacenter workloads // Proc. of the 27th Int. Symposium onHigh-Perform. Parallel Distrib. Comput.. – 2018. – P. 206–217.
- NGUYEN M., ALESAWI S., LI S. 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.
- OLIVEIRA D.C.M., LIU J., PACITTI E. Data-intensiveworkflow management: for clouds and data-intensive andscalable computing environments // Synthesis Lectures on DataManagement. – 2019. – Vol. 14, No. 4. – P. 1–179.
- 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.
- 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.
- THOMASIAN A. Analysis of fork/join and related queueingsystems // ACM Computing Surveys (CSUR). – 2014. – Vol. 47,No. 2. – P. 17:1–17:71.
- VARKI E., MERCHANT A., CHEN H. The M/M/1 fork-join queue with variable subtasks // Unpublished. – URL:https://www.cs.unh.edu/∼varki/publication/2002-nov-open.pdf(дата обращения: 02.09.2024).
- VARMA S., MAKOWSKI A.M. Interpolation approximationsfor symmetric fork-join queues // Performance Evaluation. –1994. – Vol. 20. – P. 245–265.
Supplementary files
