We consider the so-called N -model which contains two pools of servers and two classes of external customers following independent Poisson inputs. Service times are class-depend and, in each pool, are i.i.d. Pool 1 consists of N1 servers and pool 2 consists of one server. When all servers of pool 1 are occupied, and there are waiting customers in the queue of pool 1, then a class-1 customer jumps to server of pool 2, becoming a class-(1,2) customer. We consider a non-preemptive service priority: a class-(1,2) customer starts service in the server of pool 2, when an ongoing customer service, if any, is completed. The purpose of the research is to deduce explicit stationary distribution of number of customers at the 1st pool, and to verify stability conditions of the model. Moreover, we simulate a model with one server in the 1st pool, N1 = 1, in which class-1 customers jump to pool 2 provided the queue at pool 1 exceeds a positive threshold C. In this setting we verify by simulation that (i) for each xed C, the stationary idle probability P0 of server 1 attains minimum when the 2nd server is always busy with class2 customers (saturated regime) and (ii) P0 decreases as the threshold C increases.
This work continues the study of the so-called N -model considered earlier in [4], and which, in turn, is a variation of the model studied in [8]. This model belongs to a class of network models with so-called Skills-Based Routing which describes the routing of customers. This routing can be dynamic, depending on the state of the system. In the opposite case, this routing is prede ned in advance, say by assignment of the servers among customers depending on their priority. The latter routing is called static. The design of Skills-Based Routing is an actual and challenging problem. A multi-server pool is equivalent to multiple equally-skilled single servers, see for instance, [3,9].
For instance, N -model means that in the two-pool system, each server of
the 1st pool serves only the customers of class-1 customers, while each server
of the 2nd pool can serve both class-1 and class-2 customers. In this model,
there are two independent Poisson inputs of class-i customers, where class-i
customers join the queue or occupy the available server of pool i = 1; 2. At
that, a class-1 customer meeting all servers in pool 1 busy (or when queue-size
in pool 1 exceeds a threshold C > 0) jumps to pool 2 to be served as a
class(
In some situation, service capacity may be transferred between servers for optimization of service process. Also one of possible applications of the model is the so-called cognitive radio, where a dynamic management is applied for using the best wireless channels in its neighborhood to avoid congestion. Such a radio can detect currently unused frequency bands and switch between such free channels without interruption of data transmission.
The contribution of this work is as follows. First of all, for exponential service times, that is for pure Markovian model, we construct Kolmogorov equations and derive the stationary distribution of the number of customers in the 1st pool with N1 1 servers, provided the 2nd pool (server) is always busy by class2 customers. We call this system saturated. Moreover, using approach from [11], we prove the following intuitive continuity property of the model: if the queue size in pool 2 increases (in probability) then the stationary distribution of the 1st pool approaches the corresponding stationary distribution of the 1st pool with initially saturated pool 2. Evidently, each class-1 customer, before jumping to pool 2, must wait a time until class-2 customer, being served, departs server. (We recall that class-1 customers have non-preemptive priority.) It indicates that the stationary idle probability P0 of the 1st pool (that is the probability that all N1 servers are idle) must attained minimum in the saturated system. In this work we verify this property by simulation for the system with threshold C > 0, and it is another contribution of the research. (In previous paper [4] we studied the system in which C = 0.) Finally, we verify by simulation that the probability P0 decreases as the threshold C increases.
The paper is organized as follows. We describe the model in Section 2. Section 3 contains the main mentioned above theoretical results: solution of Kolmogorov equations and the proof of convergence queue-size distribution in pool 1 to distribution for the model with saturated pool 2. Section 4 contains simulation results. 2
Description of the model
We study a Markovian queueing model containing two pools of servers with
in nite-capacity bu ers. The 1st pool consists of N1 servers working in parallel,
while the 2nd pool contains only one server. Thus the rst pool is a N1-server
queueing system, while the second pool is a single-server system. It is worth
mentioning that even in this relatively simple setting the analytic solution is
available only in a special case, when service rate of class-(
The choice of such con guration of the pools is also caused by the following reason: in this case we are able to solve the corresponding Kolmogorov equations to nd stationary distribution of the state of the rst pool explicitly.
It is assumed that pool i is fed by a Poisson input with rate i; i = 1; 2.
Class-1 customers can be served in both pools, while class-2 customers can be
accommodated by pool 2 only. Moreover, provided the number of waiting in the
queue (in pool 1) class-1 customers exceeds a given threshold C, an arbitrary
class-1 customer waiting in the 1st queue, can jump to pool 2, becoming
class(
We assume that the service times of class-i customers fSk(i); k 1g are independent, exponential with rate i = 1=ES(i) 2 (0; 1); i = 1; 2; (1; 2). (In what follows, we omit the serial index to denote a generic element of an i.i.d sequence.) All sequences are assumed to be independent.
We denote Qi(t) the summary number of customers (including waiting in the queue) in pool i at instant t , i = 1; 2. We assume an arbitrary workconserving service discipline in each pool, in particular, an arbitrary waiting class-1 customer may jump to the server of pool 2, provided Q1(t) > N1 + C and pool 2 is idle, because performance analysis and stability/instability does not depend on the order of customers, which (in each class) are stochastically undistinguishable. 3
Theoretical results In this section, we deduce explicit formulas for the 1st pool stationary probabilities. Then we formulate and verify a condition implying convergence of the queue-size distribution in original pool 1 with increasing class-2 customers to stationary distribution of the 1st pool with initially saturated (by class-2 customers) pool 2.
A key assumption is that 12 = 2, in which case class-2 and class-(
Recall that the 1st pool consists of N1 servers and the 2nd pool contains only one server. It is easy to verify that service rate of class-1 customers, at instant t, is de ned as 1(t) =
N1 X P(Q2(t) > 0; Q1(t) = k)( 1k + 2) k=0 + P(Q2(t) > 0; Q1(t) > N1)( 1N1 + 2)
N1 + X P(Q2(t) = 0; Q1(t) = k) 1k:
k=0 Our main assumption is that the 2nd pool approaches saturated regime, that is the queue size in the 2nd pool increases unlimitedly in distribution:
Q2(t) ) 1; t ! 1: Then it easily follows that, as t ! 1,
N1 X P(Q2(t) = 0; Q1(t) = k) ! 0; k=0 P(Q2(t) > 0; Q1(t) > N1) ! P(Q1 > N1) =: P>N1 ; 0: P(Q2(t) > 0; Q1(t) = k) ! P(Q1 = k) =: Pk; k
N1 X P(Q2(t) > 0; Q1(t) = k) ! k=0
N1
X Pk:
k=0
(
N1 X Pk( 1k + 2) + P>N1 ( 1N1 + 2) =: : k=0 Now we construct Kolmogorov equations for the stationary probabilities of the state of the 1st queue, provided the 2nd queue is overloaded. Introduce tra c intensities and, for k = 2; : : : ; N1, 1 = 1 ; 1 k = 1PN1 = (N1 1 + 2)PN1+1;
N1 PN1+1 = Y 1
i N1 P0: 1PN1+k = (N1 1 + 2)PN1+k+1;
N1 PN1+k+1 = Y 1 i[ N1 ]k+1P0: Using normalization condition Pk1=0 Pk = 1, we obtain
N1 l 1 = P0 + P0 X Y
1 N1 i + P0 X Y
i[ N1 ]k: It is easy to check that the following balance relations for stationary distribution of the process fQ1(t)g hold true: (8) (9) (10) (11) (12) Thus, the stationary probabilities Pk in (7) satisfy relations (8)-(13).
Our next goal is to show the following intuitive continuity result, which
however needs to be strongly proved below. It is expected that, under main
assumption (
First of all we note that it has been proved in [5] that the 1st pool is stationary if the following su cient condition holds: 1N1 + 2 1 1 > 0: Note, that this condition guarantees stability of the 1st pool regardless of the threshold C, when class-1 customers may jump to pool 2. The strong proof of the mentioned continuity property is based on a condition from [11] which is formulated below for the birth-and-death process fQ1(t); t 0g with birth (input) rates (k) and death (service) rates (k), where k is the current state of the process Q1. It is easy to see that in our setting (14) (15) (k) = (k) = (k) = 1; 1k + 2; k
N1; 1N1 + 2; k > N1: The condition we must verify is as follows [11]: inf k 0 (k) + (k + 1) dk 1 (k) dk dk+1 (k + 1) > 0; dk where constants dk must be positive. We take the following constants: dk = 1; k = 1; ; N1
1; dN1+k = dN1 = 1 + k+1; k = ; 1; where > 0 will be selected below. For k = 0; condition (15) indeed holds: ; N1
1 + 1(k + 1) + 2 1k 2 1 = 1 > 0: For k=N1
1, we have 1 + 1N1 + 2 1(N1 1) 2 (1 + ) 1 = 1 1 > 0; if we take < 1= 1: For k=N1 it follows that Collecting all requirements to , we conclude that condition (15) is satis ed if we select in such a way that the following inequality holds: 0 < < min 1 ; 1N1 + 2 1 1 It remain to note that > 0, satisfying (16) exists by condition (14).
Denote EX1 the mean stationary number of busy servers in the 1st pool (provided the 2nd pool is overloaded). It has been proved in [8], that if 1 1EX1 + 12 2 < 1; 2 then the system is stable. Using obtained above explicit expressions (11), (12) for stationary distribution of the 1st pool, we calculate that
EX1 =
N1 X Pkk + N1P>N1 k=1
N1 k = P0 X k Y i + N1P0 X1 kN1 YN1
i = P0 k=1 i=1
N1 k X Y i + N1 In the following experiments, we demonstrate a monotonicity property of the estimate P^0 of the stationary idle probability in original system with xed value (16) (17) of the threshold C > 0. We emphasize that these experiments have been started in previous paper [4] where we shown, for the system with threshold C = 1, that the estimate P^0 of the stationary idle probability attains minimum in the saturated system.
Let P^(o) be the estimate of stationary idle probability P0 (of the 1st server) 0 in the saturated system. Denote the di erence d^ = P^0 - P^0(o). We show that the minimum of estimate P^0 is P^(o) (when the 2nd server is permanently busy), 0 implying d^ 0, provided the number of observations is large enough. For the system with exponential service time and the following parameters 1 = 7; 2 = 1; 1 = 10; 12 = 5; 2 = 5; the property is con rmed for C = 5 and C = 10, see Fig. 1 and Fig. 2, that illustrate convergence of d^ to 0:008 and 0:001, respectively.
d e l b a i r a v f o e u l a V
Fig. 1. Estimate d^ for exponential service times, C=5 d e l b a i r a v f o 1e+03 5e+03 5e+04 5e+05
5e+06
Finally, we demonstrate that increasing C implies decreasing estimate P^0. We demonstrate it for the original model and model with the 2nd server overloaded by class-2 customers. Intuitively, this property is clear, because, when C increases, then class-1 customers in general wait more time in the 1st queue before jumping to pool 2. This property for 100000 arrivals, is con rmed for i) exponential service time with parameters 1 = 7, 2 = 1, 1 = 10, 12 = 5, 2 = 5 (Fig. 5); and ii) for Pareto service time with parameters 1 = 0:5; 2 = 0:4; k1 = 3; k12 = k2 = 5 (Fig. 6).
e t a m it s e y liit b a b o r p e l d I Fig. 5. The monotonicity of P^0 and P^0(o) for exponential service times as C increases e t a m it s e y ilit b a b o r p e l d I ACKNOWLEDGEMENTS The study was carried out under state order to the Karelian Research Centre of the Russian Academy of Sciences (Institute of Applied Mathematical Research KRC RAS). The research is partly supported by Russian Foundation for Basic Research, projects 18-07-00147, 18-07-00156.