=Paper= {{Paper |id=Vol-2556/paper11 |storemode=property |title=Relationship Invariants Based Sojourn Time Approximation for the Fork-Join Queueing System (short paper) |pdfUrl=https://ceur-ws.org/Vol-2556/paper11.pdf |volume=Vol-2556 |authors=Roman S. Khabarov,Vladimir A. Lokhvitckii,Andry S. Dudkin }} ==Relationship Invariants Based Sojourn Time Approximation for the Fork-Join Queueing System (short paper)== https://ceur-ws.org/Vol-2556/paper11.pdf

Relationship Invariants Based Sojourn Time Approximation
for the Fork-Join Queueing System

Roman S. Khabarov Vladimir A. Lokhvitckii Andry S. Dudkin
MSA named MSA named MSA named
after A.F.Mozhaysky after A.F.Mozhaysky after A.F.Mozhaysky
Saint Petersburg, Russia Saint Petersburg, Russia Saint Petersburg, Russia
xabarov1985@gmail.com lokhv_va@mail.ru andry-ll@mail.ru

3 service channels. In the case of Fork-Join, the freed
channel may be occupied by the subtask of the next
task (Figure 1). When organizing the Split-Merge
service (Figure 2), a block occurs at the time of task
Abstract entering, and the freed channels are idle, waiting for
The approximation method of task the last of the subtasks of the current task to be
sojourn time in the fork-join queuing serviced.
system based on relationship invariants is
proposed. The idea is in application of
intuitive proportion between the certain
queuing systems time characteristics. It is
shown that, compared with the known
methods, the proposed approximation is
more accurate with server utilization
higher then 0.7. Figure 1: Task service chart in Fork-Join
queueing system

1 Introduction
To evaluate the efficiency of query processing in
systems using distributed and parallel computing
technologies, queuing systems like Split-Merge and
Figure 2: Task service chart in Split-Merge
Fork-Join are used.
queueing system
The general idea of the Split-Merge and Fork-Join
systems functioning is as follows: tasks received in the
A rather large number of works has been devoted to the
system are “split” into n sub-tasks, each of which is
Fork-Join and Split-Merge processes [Alom2014,
sent to the channel with numbers 1, 2, ..., n,
Bacc1985, Bacc1989, Fior2015, Flat1979, Harr2003,
respectively. Processed subtasks fall into the
Khab2019, Nels1988, Olv2014, Ryzh1980, Ryzh2015,
synchronization buffer, where they wait for the
Qui2015, Var2002, Varma1994, Wright1992]. For the
servicing completion of their related subtasks. At the
Split-Merge system in [Harr2003], an exact solution
end servicing of the last related subtask,
was obtained to determine the maximum service time
synchronization occurs, i.e. aggregation, after which
of independent channels with exponential service time
task leaves the system. It is regarded that
and various intensities, as well as approximations for
synchronization occurs instantly.
the case of a general distribution. In [Fior2015], the
The difference between the Split-Merge and Fork-Join
mentioned distribution was obtained for homogeneous
systems is shown in Figures 1 and 2 for the example of
and heterogeneous servers, and its representation in
Copyright c by the paper's authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
matrix-exponential form made it possible to find both
In: A. Khomonenko, B. Sokolov, K. Ivanova (eds.): Selected Papers of the first and the moments of higher orders. It should be
the Models and Methods of Information Systems Research noted that this method is characterized by high
Workshop, St. Petersburg, Russia, 4-5 Dec. 2019, published at
http://ceur-ws.org. 63
computational complexity, which is a consequence of of high and low system utilization interpolation
the laborious operations of inversion and the Kronecker methods:
product of matrices that are included in it. The use of
1
Kronecker algebra is associated with a significant v1 » [H n + (Vn - H n )r ] , (4)
additional memory consumption, as well as many µ -l
redundant operations with zero operands. In
[Ryzh2019], an exact solution was found for an ænö æ i ö (m - 1)!
å çç i ÷÷(-1) å
n i -1 i
where Vn = çç ÷÷ m+1 .
arbitrary distribution of services based on Chebyshev- i =1 m =1
Laguerre numerical integration. The solution has a
è ø èmø i
relatively low complexity and high accuracy.
For Fork-Join systems, the exact expression for the In this paper, we propose a method for finding the
average sojourn time with an arbitrary service average sojourn time for a Fork-Join queueing system
distribution was obtained only for a system with two with an arbitrary service distribution based on the
approximation of relationship invariants.
channels [Bacc1985, Fior2015]. For the case n > 2 and
exponential service, using various methods,
approximations of the average sojourn time were
obtained in [Nels1988, Var2002, Varma1994]. We give 2 Method idea
below a brief summary of the results. In [Ryzh2015], to find the time characteristics of multi-
In [Flat1979], an exact formula is given for the average channel queueing system with priorities, a method was
sojourn time for n = 2, and the exponential distribution used based on the invariants idea of the relationship
of the service time between the desired characteristics:
æ rö
v1 = ç H 2 - ÷ × v1( M ) , (1) M /G/n
è 8ø M k / Gk / n » M k / Gk / 1 × . (5)
M / G /1
å 1 / i for n = 2 , H = 1.5 ,
n
where H n = i =1 2
All designations are given in Kendall notation.
r = l / µ – system utilization, Calculation methods for the systems indicated on the
right are considered known. In particular, iterative
v1( M ) = 1 ( µ - l ) – average sojourn time in methods of Takahashi-Takami or matrix-geometric
M / M / 1 queueing system. progression are used to calculate systems [Ryzh1980,
In [Nels1988], Nelson and Tantawi proposed an Taka1976]. For the non-priority systems M / G / 1
approximation for the average sojourn time in a Fork- and M / G / n with a non-uniform task flow, the total
Join queueing system with n service channels intensity of the task flow and the weighted average
moments of the servicing distribution were used.
éH 4 æ H ö ù 12 - r 1 As an approximation of the service time, it is proposed
v1 » ê n + çç1 - n ÷÷ r ú , n ³ 2. (2)
ë H 2 11 è H 2 ø û 8 µ - l
to use a second-order hyperexponential distribution
H 2 applicable for values of the coefficient of
In [Var2002], Varki and Merchant proposed a formula variation, both smaller and larger than 1.0. For
example, when replacing the gamma distribution with
1é r æ n 1
v1 » êH n + çå + the parameter 1 < a < 2 by H 2 -approximation, one
µë 2(1 - r ) çè i =1 i - r of the “probabilities” will be negative, and the other
n
1 öù will exceed 1.0. As computational experiments show
+ (1 - 2 r )å ÷÷ú, n ³ 2. (3) [Ryzh2015], these paradoxical intermediate results do
i =1 i (i - r ) ø û
not interfere with the successful calculation of
queueing system using known numerical methods
In [Varma1994], Varma proposed a method for [Taka1976].
approximating the sojourn time based on a combination

64
Here we present the scheme proposed in 3 Calculation results
[Ryzh2015] for the implementation of conversion
invariants for an n-channel priority system: The following are the results of calculations of the
a) By multiplying the channel rate by n, we obtain average sojourn time in the queueing system (Figures
the equivalent single-channel system rate. 3-8) in comparison with the methods proposed in
b) Calculate the waiting time distribution [Nels1988,Var2002,Varma1994] (formulas (2), (3),
(4)) and simulation data. The comparison was carried
moments {wi , j } for all types of requests i and the order
out depending on the system utilization and the number
of the moments j = 1, 3. of service channels at three values of the service time
c) For the same initial data on the weighted average coefficient of variation {0.5, 1.0, 1.5}.
service times and the total intensity of the incoming
flow L as applied to the M / H 2 / 1 system,
calculate the number of requests stationary distribution
{ pi } and the average requests number in the queue:
¥
Q(1) = å (i - 1) pi .
i =1

d) For the M / H 2 / n system, it is similar to carry
out the calculation of state probabilities at initial
service intensities and obtain the average queue length:
¥
Q(n) = å (i - n) pi .
i = n +1 Figure 3: Average sojourn time depending on the
e) Recalculate the waiting time distribution number of service channels, υ = 0.5, ρ=0.9
moments in the system with priorities for all i and j for
the multichannel case:
Wi , j = wi , j × Q(n) Q(1) .
f) Using them, according to relation (5), obtain the
sojourn time distribution moments of each task type in
a multichannel system.
We propose a similar approach for finding the
average sojourn time in the Fork-Join queueing system
with the number of channels. We rewrite the proportion
(5) in the following form
M /G/n
FJ n » FJ 2 × . (6)
M /G/2
Figure 4: Average sojourn time depending on the
Here FJ n and FJ 2 – Fork-Join queuing systems number of service channels, υ = 1.0, ρ=0.9
with n and 2 channels, respectively. To find the
average sojourn time in FJ 2 , we use the formula (1).
The calculation of the remaining queueing systems
from the right-hand side of (6) will be carried out by
known methods [Ryzh1980, Taka1976]. To ensure the
equality of system utilization values, when calculating
M / G / n queuing systems, the initial moments of
service time for were multiplied by n 2 .

65
Figure 5: Average sojourn time depending on the Figure 8: Average sojourn time depending on the
number of service channels, υ = 1.5, ρ=0.9 system utilization, υ = 1.5, n=4

As can be seen from the figures, the accuracy of
approximation by the method of invariants of the ratio
is higher than calculated by the formulas (2-4).
Moreover, at low ρ values, the method of invariant
relations gives underestimated estimates of the average
sojourn time, especially when increasing the coefficient
of variation of the service time. Since the proposed
method (as well as other approximation methods
compared here) allows us to estimate only the average
sojourn time of task in the system, if higher moments
are necessary, the Split-Merge calculation method
mentioned above should be used, since the estimated
values of the sojourn time estimates in this case are the
Figure 6: Average sojourn time depending on the upper bound stay in Fork-Join queuing system.
system utilization, υ = 0.5, n=4

4 Summary
The relation invariants method showed well average
sojourn time approximation accuracy for Fork-Join
queueing system. Calculation results and simulation
data comparison showed that the proposed
approximation accuracy increases as system utilization
increasing. At high the service time coefficient of
variation values, the method gives underestimated
sojourn time of the task in the system. If it is necessary
to find the upper bounds of sojourn time higher
moments, it is recommended to use the method
Figure 7: Average sojourn time depending on the proposed in [Khab2019,Ryzh2019]
system utilization, υ = 1.0, n=4

66
Acknowledgments evaluating model of tasks multy-threading
processing in a distributed computing
The study was carried out with the financial support of environment with Split-Join processes].
the Russian Foundation for Basic Research, project Vestnik of Russian New University. Series
number 18-29-22064 \18. ”Complex systems: models, analisys,
management”, no. 1. Pp. 26-34, 2019 (In
References Russ.).
[Alom2014] Alomari F., Menasce D.A. Efficient
[Nels1988] Nelson, R., Tantawi A.N. Approximate
Response Time Approximation for Multiclass
analysis of fork/join synchronization in
Fork and Join Queues in Open and Close
parallel queues. IEEE Transactions on
Queueing Networks. IEEE Transaction on
Computers, vol. 37. Pp. 739-743, 1988.
Parallel and Distributed Systems, vol. 25.
pp.1437-1446, 2014.
[Olv2014] Olvera-Cravioto M., Ruiz-Lacedelli O.
Parallel queues with synchronization. In arXiv
[Bacc1989] Baccelli F., Makowski A.M., Shwartz A.
preprint https://arXiv:1501.00186, 2014.
The Fork-Join Queue and Related Systems
with Synchronization Constraints: Stochastic
[Ryzh1980] Ryzhikov Y.I., Khomonenko A.D.
Ordering and Computable Bounds. Advances
Iterativnyj metod rascheta mnogokanalnyh
in Applied Probability, vol. 21. No. 3. Pp.
system s proizvolnym raspredeleniem vremeni
629-660, 1989.
obsluzhivaniya [An iterative method for
calculating multichannel systems with an
[Bacc1985] Baccelli F. Two parallel queues created by
arbitrary distribution of service time].
arrivals with two demands. The M/G/2
Problemy upravleniya i teoriya informacii
symmetrical case. Technical report INRIA-
[Management problems and information
Rocquencourt, no. 426, 1985.
theory], no. 3, Pp. 32-38, 1980 (In Russ.).
[Fior2015] Fiorini P., Lipsky L. Exact Analysis of
[Ryzh2015] Ryzhikov Y.I., Khomonenko A.D. Raschet
Some Split-Merge Queues. Performance
mnogokanal’nyh sistem obsluzhivaniya s
Evaluation Review, vol. 43. No. 2. pp. 51-53,
absolyutnym i otnositel’nym prioritetami na
2015.
osnove invariantov otnosheniya [Calculation
of multi-channel queueing systems with
[Flat1979] Flatto, L., Hahn S. Two parallel queues
preemptive and non-preemptive priorities
created by arrivals with two demands. SIAM
based on relationship invariants].
Journal on Applied Mathematics, vol. 44.
Intellektual’nie technologii na transporte
Pp.1041-1053, 1979.
[Intellectual Technologies on Transport], no.
3, Pp. 11-17, 2015 (In Russ.).
[Harr2003] Harrison P.G., Zertal S. Queueing models
with maxima of service times. Computer
[Ryzh2019] Ryzhikov Y.I., Lokhvitckii V.A.,
Performance Evaluation. Modelling
Khabarov R.S. Metod rascheta dlitel’nosti
Techiniques and Tools, pp. 152-168, 2003.
obrabotki zadach v sisteme massovogo
obsluzhivaniya s uchetom processov Split-
[Khab2019] Khabarov R.S., Lokhvitckii V.A. Model’
Join [Method for calculating the duration of
otsenivaniya operativnosti mnogopotochnoi
processing tasks in a queuing system taking
obrabotki zadach v raspredelennoi
into account Split-Join processes]. Izvestiya
vychislitel’noi srede s uchetom protsessov
vysshikh uchebnykh zavedeniy.
Split-Join. Vestnik Rossiyskogo novogo
Priborostroenie [Journal of Instrument
universiteta. Seriya ”Slozhnye sistemy:
Engineering], vol. 62. No. 5. Pp. 419-423,
modeli, analiz i upravlenie” [Efficiency
2019 (In Russ.).

67
[Taka1976] Takahashi Y., Takami Y. A numerical
method for the steady-state probabilities of a
GI/G/c queuing system in a general class. J. of
the Operat. res. soc. of Japan, vol. 19(2).
Pp. 147-157, 1976.

Qui2015] Qiu Z., Perez J.G., Harrison P.G. Beyond the
mean in fork-join queues: Efficient
approximation for response-time tails.
Performance evaluations, vol. 91. pp. 99-106,
2015.

[Var2002] Varki E., Merchant A., Chen H. The M/M/1
Fork-Join Queue with Variable Subtasks.
http://www.cs.unh.edu/varki/publication/2000
-nov-open.pdf, Accessed 19 Nov 2019.

[Varma1994] Varma S., Makowski A.M. Interpolation
Approximations for Symmetric Fork-Join
Queues. Performance evaluations, vol. 20. Pp.
245-265, 1994.

[Wright1992] Wright P.E. Two parallel processors
with coupled inputs. Advances in Applied
Probability, vol. 24. Pp. 986-1007, 1992.