Geodesic
Analysis of fork/join and related queueing systems
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2017), pp. 43-58 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This article introduces a generalization of the classical parallel-server fork-join queueing networks. We consider open fork-join queueing networks with an arbitrary topology. There are three types of nodes in the queueing networks (service-nodes, fork-nodes, join-nodes). We focus on the infinite server case, in which each service-node is a queueing system with infinite servers. An arriving job is split (at fork-nodes) into a number of independent tasks that are serviced in parallel (at multiple service-nodes). Each task can be split at fork-nodes repetitively. These tasks synchronize (at join-nodes) before they leave the network. A method, which allows to obtain the sojourn time distribution, was developed.
Keywords: fork-join networks, queueing network, sojourn time distribution, performance evaluation, synchronization, parallel processing, PH-distribution. 
@article{VTPMK_2017_4_a3,
     author = {O. Osipov and I. E. Tananko},
     title = {Analysis of fork/join and related queueing systems},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {43--58},
     year = {2017},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a3/}
}
TY  - JOUR
AU  - O. Osipov
AU  - I. E. Tananko
TI  - Analysis of fork/join and related queueing systems
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2017
SP  - 43
EP  - 58
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a3/
LA  - ru
ID  - VTPMK_2017_4_a3
ER  - 
%0 Journal Article
%A O. Osipov
%A I. E. Tananko
%T Analysis of fork/join and related queueing systems
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2017
%P 43-58
%N 4
%U http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a3/
%G ru
%F VTPMK_2017_4_a3
O. Osipov; I. E. Tananko. Analysis of fork/join and related queueing systems. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2017), pp. 43-58. http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a3/

[1] Thomasian A., “Analysis of fork/join and related queueing systems”, ACM Computing Surveys, 47:2 (2014), 1-71 | DOI

[2] Rizk A., Poloczek F., Ciucu F., “Computable bounds in fork-join queueing systems”, ACM SIGMETRICS Performance Evaluation Review, 43:1 (2015), 335-346 | DOI

[3] Joshi G., Liu Y., Soljanin E., “On the delay-storage trade-off in content download from coded distributed storage systems”, IEEE Journal on Selected Areas in Communications, 32:5 (2014), 989-997 | DOI

[4] Gorbunova A. V., Zaryadov K. S., Matyushenko S. I., Samuylov K. E., Shorgin S. Ya., “The approximation of response time of a cloud computing system”, Informatics and Applications, 9:3 (2015), 31-38 (in Russian)

[5] Heidelberger P., Trivedi K. S., “Analytic queueing models for programs with internal concurrency”, IEEE Transactions on Computers, 32:1 (1983), 73-82 | DOI | Zbl

[6] Flatto L., Hahn S., “Two parallel queues created by arrivals with two demands I”, SIAM Journal on Applied Mathematics, 44:5 (1984), 1041-1053 | DOI | MR | Zbl

[7] Nelson R., Tantawi A. N., “Approximate analysis of fork/join synchronization in parallel queues”, IEEE Transactions on Computers, 37:6 (1988), 739-743 | DOI

[8] Ko S.-S., Serfozo R. F., “Response times in M/M/s fork-join networks”, Advances in Applied Probability, 36:3 (2004), 854-871 | DOI | MR | Zbl

[9] Ko S.-S., Serfozo R. F., “Sojourn times in G/M/1 fork-join networks”, Naval Research Logistics, 55:5 (2008), 432-443 | DOI | MR | Zbl

[10] Baccelli F., Makowski A. M., Shwartz A., “The fork-join queue and related systems with synchronization constraints: Stochastic ordering and computable bounds”, Advances in Applied Probability, 21:3 (1989), 629-660 | DOI | MR | Zbl

[11] Latouche G., Ramaswami V., Introduction to Matrix Analytic Methods in Stochastic Modeling, Society for Industrial Applied Mathematics (SIAM), 1999 | MR | Zbl

[12] He Q.-M., Fundamentals of Matrix-Analytic Methods, Springer, New York, USA, 2014, 349 pp. | MR | Zbl

[13] Neuts M. F., Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, The Johns Hopkins University Press, Baltimore, 1981 | MR | Zbl

[14] Lipsky L., Queueing Theory: A Linear Algebraic Approach, Springer, New York, USA, 2009, 548 pp. | MR | Zbl

[15] Basharin G. P., Bocharov P. P., Kogan Ya. A., Analysis of Queues in Computer Networks. Theory and Computational Methods, Nauka Publ., Moscow, 1989, 336 pp. (in Russian) | MR