In this paper, we consider a Markovian centralized splitting fork-join queueing system with heterogeneous servers and an in nite capacity queue. Jobs arrive at the system according to a Poisson process, a job consists of multiple homogeneous tasks. Tasks of a job are served independently, when all the tasks associated with the job are nished, the job service is completed. The system operates under a threshold control policy. The control consists in sending tasks to one of idle servers or to the queue. The threshold policy uses the slow servers only when the queue length reaches certain threshold levels. We perform an exact analysis which is based on the matrix-geometric method and obtain expressions for the performance measures. Some numerical examples are presented. The results can be used for the performance analysis of multiprocessor systems and other modern distributed systems.
Fork-join queueing systems are widely used to model parallel and distributed systems. Some examples of these systems include RAID, distributed web applications, MapReduce, GRID, multipath routing networks, multiprocessor systems and etc. In these systems, arriving jobs are split for service by numerous servers and joined before departure.
In papers [
Paper [
The parallel-server fork-join queueing system consists of homogeneous servers
[
In [
The threshold control policy is used as optimal solution for the job routing
problem named the slow server problem [
In this paper, we consider a centralized splitting fork-join queueing model [
The remainder of the paper is organized as follows. Section 2 describes the fork-join queueing system under consideration. In Sections 3 and 4 we obtain the stationary distribution and the main performance measures. Section 5 provides an illustration of the above results, we also discuss some control policies and compare them. Finally, a section of conclusions commenting the main research contributions of this paper is presented.
λ μ M
We consider a system which consists of M heterogeneous servers Si, i = 1; : : : ; M , and a FCFS in nite capacity queue as shown in Fig. 1. Jobs arrive at the system according to a Poisson process with rate . Each job is split into d homogeneous tasks, d M . An arriving task is placed in the queue. The service times at server Si have exponential distribution with parameter i, i = 1; : : : ; M , and 1 > 2 > > M .
Let b denote the number of waiting tasks in the queue (queue length). At the arrival times of new tasks the control consists in sending tasks from the queue to the fastest idle server or leaving them in the queue. A task from the front of the queue is assigned to a fastest idle server Si, i 2 f1; : : : ; M g, if the queue length immediately after the arrival is not less than threshold level qi, i.e., qi b + 1, (1 = q1 q2 qM < qM+1 = 1).
When a task nishes its service at server Si, a task from the queue will be assigned to server Si if the queue length satis es b qi. Otherwise server Si will be idle. Tasks of a job are served independently, when all the tasks associated with the job are nished, the job service is completed. 3
The system state is described by a vector x = (r; n0; n1; : : : ; nM ), where r = r(b) = b div d denotes the number of waiting jobs in the queue, n0 = n0(b) = b mod d is the number of tasks for the served job in the queue, ni = (0; if server Si is idle,
The process fx(t); t 0g is a (M + 2)-dimensional continuous-time Markov chain on the state space X .
For each state x, we denote by F (x) and F (x) the sets of idle and busy server indices, respectively,
F (x) = fi > 0 : ni = 0g;
F (x) = fi > 0 : ni = 1g:
Denote by (b) the mandatory (minimal) number of busy servers for queue length b. We can write
8>0; (b) = <M; >:maxfi : qi b = 0, b qM , bg, otherwise.
De ne '(x) by '(x) =
1, (the minimal element of F (x), if F (x) 6= ?, otherwise.
If there are idle servers in the system, a task will be assigned to server S'(x).
Let us de ne now the transition rate q(x; x0) from state x 2 X to state x0 2 X . Each transition is associated with an event in the system, there are two types of events. 1. A job arrives and splits into d tasks (a) if b qM , (1) (2) (3) (4) (b) if b < qM , q (x; (r + 1; n0; n1; : : : ; nM )) = ;
q(x; x0) = ; where x0 = x(d) can be obtained from the following recurrence relation x(i+1) = ( r(b(i) + 1); n0(b(i) + 1); n(1i); : : : ; n(Mi) ; x(i) + e2+'(x(i)); '(x(i)) > (b(i) + 1), otherwise, with the initial value x(0) = x, i = 0; : : : ; d 1.
Here, x(i) = r(i); n(0i); : : : ; n(Mi) and b(i) = dr(i) + n(0i); ej denotes the vector of the appropriate dimension with all components equal to 0, except the jth, which is 1. 2. A task nishes its service at server Si (ni = 1) (a) if b < qi, (b) if n0 > 0, fi 2 F (x) : b i2F(x): b qi i; (c) if r > 0, n0 = 0, fi 2 F (x) : b q(x; (r 1; d
Let state space X be lexicographically ordered. The subset Xl is called level l, l = 0; 1; : : : , and de ned as
Xl = f(r; n0; n1; : : : ; nM ) 2 X : r = lg: The cardinality L of X0 is
L = 2M + (q2 q1)2M 1 + (q3 q2)2M 2 + + (d q 0 )2M 0 ; where 0 = (d 1).
Let r be the minimal number r 2 f1; 2; : : : g such that rd nalities of Xl, l r are d.
The cardinalities of Xl, 0 < l < r are Kl = 2M
l (q l +1 where ld) + 2M + 2M l 1(q l++1(q + l l +2
q l +1) + q l+ 1) + 2M + + l (ld + d q + ); l l = (ld); l+ = (ld + d 1): The system states are presented in Table 1.
qM . The cardi
It is easily shown that for Xl, l > 0, there are transitions to Xl 1 and Xl+1. Thus, the Markov chain fx(t); t 0g is a quasi-birth-and-death (QBD) process, the generator matrix Q of the process has the following form where blocks A2, A1, A0 are square matrices of order d, B00 is the square matrix of order L, blocks B01, B10 are L K1, K1 L matrices respectively, Bl;l, l = 1; : : : ; r, are square matrices of order Kl (we set Kr = d), blocks Bl;l 1, l = 2; : : : ; r, are Kl Kl 1 matrices, and blocks Bl;l+1, l = 1; : : : ; r 1, are Kl Kl+1 matrices.
The elements of matrices B01, Bl;l+1, l = 1; : : : ; r 1, and A0 are determined by (1) and (2). The elements of matrices B10, Bl;l 1, l = 2; : : : ; r, and A2 are determined by (5). Note that A0 = I, where I is an identity matrix of the appropriate order; A2 is the square matrix of order d, where the (1; d)th element of the matrix is equal to PM
i=1 i, and other elements are zero.
The non-diagonal elements of matrices B00, Bl;l, l = 1; : : : ; r, and A1 are determined by (2){(4); the diagonal elements of these matrices are determined from conditions (we set Br;r+1 = A0): where 1 is an ones column vector of the appropriate order. Note that A1 is the bidiagonal square matrix of order d, where the (j; j)th element of the matrix is equal to ( + PiM=1 i), and the (j; j 1)th element is equal to PiM=1 i.
It is known [22], that the QBD process is ergodic if and only if AA01 < AA21, where AA = 0, A1 = 1, A = A0 + A1 + A2. The condition implies d < 1 + +
M :
The stationary distribution = ( 0; 1; : : : ) of the QBD process can be computed using the matrix-geometric method [22]. The row vector l, l = 0; 1; : : : , de nes probabilities of states for level l, according to the lexicographic order, l = ( (x) : x 2 Xl).
We solve linear system Q = 0 and 1 = 1 to nd the stationary probabilities. Taking the advantage of the block structure in Q, we obtain 0B00 +
1B10 = 0; 0B01 + 1B12 + 1B11 + 2B22 + 2B21 = 0; 3B32 = 0; : : : : : : : : : : : : : : : : : : i 1Bi 1;i + iBi;i +
i+1Bi+1;i = 0; : : : : : : : : : : : : : : : : : : We know [22], the solution of (6) has the matrix-geometric form given by r+l =
l rR ; l = 1; 2; : : : ; where R is the minimal non-negative solution to equation A0+RA1+R2A2 = 0, vectors 0; 1; : : : ; r satisfy ( 0; : : : ; r) BBB 0
B B@ 0
0 0B00 B01 0 BB10 B11 B12
B21 B22 where V is the average job service time, which is de ned as the average total time required to process all of the tasks associated with the job once the rst task is assigned to a server.
The average number N of jobs in the system is
To obtain the average job service time, we consider the service process of all d tasks of an arbitrarily chosen \tagged" job. There are two cases considered. 1. We assume that when the rst task is assigned, the queueing system is in a state x such that r > r. Then all servers are busy, and tasks of the tagged job sequentially occupy available servers.
The service process of the tagged job is described by an absorbing Markov chain = f (t); t 0g. Denote the state of chain by (k; S), where k denotes the number of tasks of the tagged job in the queue, S denotes the set of indices for busy servers that process tasks of the tagged job. State (0; ?) is absorbing. The state space N of Markov chain is given by d N = [ j=1
N j [f(0; ?)g; where
N j = f(k; S) : k 2 f0; 1; : : : ; d Sj denotes the set of all j-element subsets of f1; : : : ; M g, j ; jg; S 2 S g jN j =
d X j j=1 d
M j + 1 + 1: The initial probability distribution de ned on state space N is given by the vector ( 0; ), where 0 = 0(0; ?) = 0, = ( (k; S) : (k; S) 2 N n f(0; ?)g), (d 1; fig) = M
P i i=1
i ; i = 1; : : : ; M; and other initial probabilities are zero.
Markov chain is determined by generator matrix Q elements q ((k; S); (k0; S0)) with non-diagonal q ((k; S); (k0; S0)) = >8 i; >>< i;
P > > >:0; if k0 = k = 0; S0 = S n fig; i 2 S; if k0 = k 1
0; S0 = S Sfig; i 2= S; i2S i; if k0 = k 1
0; S0 = S; otherwise: We denote by T the square matrix of order jN j 1 which is a submatrix of matrix Q and contains transition rates among the transient states. The absorption time for Markov chain is a random variable which has a PH-distribution with PH-representation ( ; T ) [22]. The expected absorption time is
E[ ] =
T 11: 2. We assume that when the rst task is assigned, the queueing system is in a state x such that 0 r r. Then service of the tagged job starts right after the events: { the job arrives, { a task nishes and leaves the system, { a job arrives and this leads to a task of the job is assigned to an idle server.
In this case, the service process of the tagged job is described by an absorbing Markov chain = f (t); t 0g. Denote the state of chain by (k; S; x), where k denotes the number of tasks of the tagged job in the queue, S denotes the set of indices for busy servers that process tasks of the tagged job, x denotes the system state, x 2 X^, X^ = fx 2 X : r rg. States (0; ?; x), x 2 X^ are absorbing. The state space Z of Markov chain is given by where
d 1 Z = [ Zk;
k=0 Z0 = [ f(0; S; x) : S 2 S(x; 0)g ; x2X^ Zk =
[ x2X^ : n0=k f(k; S; x) : S 2 S(x; k)g ; k = 1; : : : ; d 1; S(x; k) =
S
F (x) : jSj + k d : The initial probability distribution de ned on state space Z is given by the vector ( 0; ), where 0 = ( 0(0; ?; x) : x 2 X^) = 0, = ( (k; S; x0) : (k; S; x0) 2 Z n Z0):
0
X x2A(x0)
M (x) + X i=1 i
X x2Di(x0)
1 (x)A G 1; x 2 X presents states from which the system moves to state x0 as a result of a job arrival (x 2 A(x0)), or as a result of a task completion at server Si (x 2 Di(x0)), i = 1; : : : ; M ; G denotes the normalizing constant. The Markov chain is determined by generator matrix Q with non-diagonal elements q ((k; S; x); (k0; S0; x0)).
Suppose there is a transition from x to x0 as a result of an event described in Section 3. So we have the corresponding transition from (k; S; x) to (k0; S0; x0), where k0 and S0 will be described below.
Assume the system moves from state x to state x0 as a result of a job arrival, we denote by H(x; x0) = F (x0) n F (x) the index set of idle servers which will be busy right after the event. Let H(x; x0) = fi1; i2; : : : ; img, i1 < i2 < < im, then Hj (x; x0) H(x; x0) denotes the j-element set
(a) A job arrives
Hj (x; x0) = fi1; : : : ; ij g: q ((k; S; x); (k0; S0; x0)) = ; where k0 = max fk jH(x; x0)j; 0g, S0 = S S Hk k0 (x; x0), (b) A task nishes its service at Si i. if k > 0, n0i = 1, i 2= S, ii. if k > 0, iii. if k > 0, n0i = 0, iv. if k = 0, q ((k; S; x); (k
1; S [ fig; x0)) = i; q ((k; S; x); (k 1; S; x0)) =
X i2S:n0i=1
i; q ((k; S; x); (k; S n fig; x0)) = i; q ((0; S; x); (0; S n fig; x0)) = i: We denote by the absorption time for Markov chain . The expected absorption time E[ ] is computed similarly to E[ ].
where c1 = !1, c2 = 1G,
V =
E[ ]c1 + E[ ]c2 c1 + c2 ; (!1; : : : ; !d) = r(I
R) 1 r r+1
M X i:
Consider a fork-join queueing system which consists of M = 3 heterogeneous servers, where 1 = 5, 2 = 2, 3 = 1.
The performance measures depend on threshold levels qi, i = 2; : : : ; M . Let qi be the optimal threshold levels with respect to the minimization of the average response time T . They can be obtained by the exhaustive search method. Assume that = 1 and d = 3, then the optimal threshold levels are q2 = 2, q3 = 8, and T = 0:838.
To illustrate the advantages of the threshold control policy, we consider the fastest free server policy with qi = 1, i = 1; : : : ; M . Figure 2 presents the average response times for the optimal threshold control policy and the fastest free server policy for several values of the arrival rate .
Threshold control policy Fastest free server policy Threshold control policy Fastest free server policy 1.5 T 0.5 1 0 6 4 T 2 0 0.5 1 2
2.5 (a) λ 1.5 0.5 1 2
2.5 λ
1.5 (b)
It may be seen that the optimal threshold control policy provides lower values of the average response time T . When the arrival rate is quite large, the di erence between the policies can be neglected. As increases, the threshold levels decrease that leads to the fastest free server policy is near optimal one in this case. 6
We studied a Markovian fork-join queueing system with heterogeneous servers and threshold control policy. Applying a matrix-geometric approach, we obtained the stationary distribution of the system and performance measures. The results can be used for the performance analysis of multiprocessor systems and other modern distributed systems. An interesting topic for future research is to obtain the optimal threshold control policy which minimizes the long-run average number of jobs in the system or the average response time. 17. Rykov, V.V., Efrosinin, D.V.: On the slow server problem. Automation and Remote
Control 70(12), 2013{2023 (2009). https://doi.org/10.1134/S0005117909120091 18. Rykov, V.: Monotone control of queueing systems with heterogeneous servers.
Queueing Sys. 37(4), 391{403 (2001). https://doi.org/10.1023/A:1010893501581 19. Efrosinin, D., Breuer, L.: Threshold policies for controlled retrial queues with heterogeneous servers. Ann. Oper. Res. 141, 139{162 (2006). https://doi.org/10.1007/s10479-006-5297-5 20. Ozkan, E., Kharoufeh, J.: Optimal control of a two-server queueing system with failures. Probability in the Engineering and Informational Sciences 28(10), 489{527 (2014). https://doi.org/10.1017/S0269964814000114 21. Legros, B., Jouini, O.: Routing in a queueing system with two heterogeneous servers in speed and in quality of resolution. Stochastic Models 33(3), 392{410 (2017). https://doi.org/10.1080/15326349.2017.1303615 22. He, Q.-M.: Fundamentals of Matrix-Analytic Methods. Springer, New York (2014). https://doi.org/10.1007/978-1-4614-7330-5