We consider a modi ed multiserver Erlang loss system with two-priority classes of customers: the rst priority customers (class-1) are lost if nd all servers busy, while the second priority customers (class-2) join an in nite capacity queue if nd all servers busy. A new feature of this system is that a multi-type servers assignment for the rst priority customers is allowed. We assume Poisson inputs and general service times for both classes. We show how the product form of class-1 stationary probabilities can be used to obtain the stability condition of the whole system. Also we perform simulation to con rm theoretical results.
Internet tra c has been explosively increased in recent years and the most likely it will grow in a future. Increased using of the smartphones, tablet and laptop computers, smart watches etc. causes a spectrum shortage problems in wireless networks. One of the way to solve this problem is to use cognitive wireless networks [3]. There can be two classes of users in these networks: primary (licensed) users and secondary (un-licensed) users. Secondary users may use the bandwidths only if they do not interfere primary users and, in particular, if primary users are not present. Primary users can interrupt transmissions of secondary users, if there are no free channels. In this case secondary user evacuates to the head of the bu er. When one of the channels becomes available, secondary users can resume transmissions. We also assume that di erent channels in general have di erent transmission rates and can accept a limited set of classes of the primary users. This assumption is related to the notion of exible servers [9,10]. This notion means that some service capacity can be transferred from one pool of servers to another to satisfy di erent requirements. We also mention the concept of cross-trained servers [11,12,13], where one pool of servers can serve a limited set of customer types, while a second pool has been trained to serve all types of customers. Models with exible servers and multiclass multiserver setting often use for the purpose of nding an optimal allocation by minimizing a cost function [14,9,15].
Based on this motivation we will study the following queueing system. First, following work [1], we consider a modi ed Erlang loss system with c identical servers and two classes of customers: the rst priority customers (class-1) are lost if nd all servers busy, while the second priority customers (class-2) join an in nite capacity queue if nd all servers busy. Class-1 customers have absolute priority over class-2 customers meaning that the transmission of a class-2 customer might be interrupted by a class-1 customer. Interrupted class-1 customers evacuate to the head of the bu er and resume their transmission as soon as a server is available.
In the present research we study an extension of this system which in fact is a
combination of described modi ed Erlang system and another multi-class
multiserver Erlang-type system introduced and studied in the paper [2]. In this system
each server is served by only a limited set of customer classes and di erent classes
of customers in general have di erent arrival rates. Also each server in general
has di erent service rates. The customer assignment probabilities appear in this
system: for each customer class and for each set of idle servers the assignment
probability of this class customers to each available server must be given. The
analysis performed in the work [2] shows that one can choose the assignment
probabilities in such a way that the system becomes reversible (that is described
by a reversible Markov process) and in this case the stationary probabilities fPig
can be found in an explicit form. These stationary probabilities will appear in
stability condition of our system (
In this work we combine these systems in such a way that the rst priority
customers (class-1) considered in the work [1] are divided into I subclasses which
are the classes of customers in the paper [2]. We note that the stationary
probabilities in this system are the same as in [2], since the second priority customers
do not a ect the assignment and the service of the rst priority customers. We
show that stability condition of the system described in [1] is also the stability
condition of our extended system provided the service rates are the same for
all servers, as in classical multi-server systems (identical servers). In this case
one can use found stationary probabilities fPig to obtain stability condition (
A similar model was studied by Akutsu and Phung-Duc [3] where primary customer rst sense the channels before occupying them. In this work Poisson arrivals and exponential service times of all classes of users are assumed. The stability condition is suggested and veri ed by simulation in [3]. Other queueing models of cognitive radio networks could be found in the papers [4,6,7,8].
The rest of paper is the following. In Section 2 we describe an extended system and show the stability condition of this system. In Section 3 we present some preliminary results from the work [2]. In Section 4 we construct an example of the extended system to show in detail how to nd the assignment probabilities (which must satisfy some balance equations) and then calculate the required stationary probabilities fPig. In Section 5 we perform simulation to demonstrate the stability/instability of the system depending on whether the conditions on the assignment probabilities are met or violated the mentioned balance equations. 2
In this work we study the extension of the following system with J identical
servers and two-priority classes of customers: the rst priority customers
(class1) are lost if nd all servers busy, while the second priority customers
(class2) join an in nite capacity queue if nd all servers busy. Customers of class-i
follow Poisson input with rate (i). The service discipline for class-2 customers
is assumed to be FCFS ( rst-come- rst-served). Also we assume that class-i
customers have independent identically distributed (iid) service times fSn(i)g
with generic element S(i). Denote by 2 = (
J X iPi < J: i=1 A new distinctive feature of the modi ed system is that a multi-type server assignment for the priority customers is assumed. Each server can serve only a limited set of subclasses of class-1 customers and di erent subclasses of customers in general have di erent arrival rates. We assume Poisson inputs and serverdependent service rates for the sets of priority subclasses. At the same time, class-2 customers belong to only one type and can be served by any server.
More exactly, we assume J numbered servers f1; :::; J g and the rst priority (class-1) customers are multi-class divided on subclasses f1; :::; Ig. Subclass customer i can be served by servers from a set S(i), and server j can serve customers from subclasses C(j), for each i = 1; :::; I and j = 1; :::; J . Customers of subclass i arrive at rate i, and in general, server j has rate j .
Now we show that condition (
X i1(Q1(u) = i)du; t
0 i=1
0;
(
J X 1(fonly the i-th server is busy at instant tg); i=1 :::
X i;j2f1;::;Jg; i6=j 1(fonly the i-th and the j-th servers
are busy at instant tg); 1(Q1(t) = J ) = 1(fall servers are busy at instant tg): Then we can obtain the corresponding stationary probabilities as in relations (21) in the paper [1]. We denote by V^1(t) the work of class-1 customers accepted by the system in time interval [0; t]. Note that V^1(t) does not include the lost work. Let W1(t) be the workload (the remaining work to be done) of class-i customers at instant t . It is easy to see that,
V^1(t) =
Z t J
X[i1(Q1(u) = i)]du + W1(t); t
0 i=1
0:
(
EV^1(t) t
1 Z t J = lim X[iP(Q1(u) = i)]du =
t!1 t 0 i=1
J = X i lim i=1 t!1 t 0 1 Z t
J
X iPi:
i=1
P(Q1(u) = i)du =
(
Now we present some results from paper [2]. We denotes by X(t) the set of numbers of servers which are not busy by class-1 customers at time t. The state space of the process fX(t)g is S f1; :::; J g, and is all possible combinations of the numbers of servers. When the system is in state S an arriving class1 customer of subclass i selects a server j 2 S with the probability Pi;j (S). These assignment probabilities are the control parameters that we can choose to obtain the stationary distribution of the system. If i 2= C(j) then Pi;j (S) = 0. If S = fkg and i 2 C(k) then Pi;k(S) = 1 for all k 2 f1; :::; J g. We note that class2 customers do not a ect the assignment and the service of class-1 customers. Therefore all results obtained in the paper [2] for the loss system with multi-class customers and multi-class servers and brie y presented below are applicable for our extended system.
We assume Poisson input and exponential service times for all of customer
subclasses. Under this assumption the process fX(t)g is a continuous-time Markov
chain. If we have arbitrary service time distribution, we obtain the same
stationary distribution. See the proof of this in Proposition 7 in the paper [2]. Now we
show that one can choose the assignment probabilities in such a way that one
can obtain the stationary distribution of the process fX(t)g (as in the paper [2])
and also obtain probabilities Pi in (
Now we assume that the process fX(t)g is reversible. Actually, in the paper
[2] this statement is claimed but not shown in details (see Section 3 in [2]),
and we check it for our example by conducting simulation in Section 5. Because
fX(t)g is reversible, then the following detailed balance equations hold:
(S) j (S) = (Snfjg) j
for all subset S
f1; :::; J g and j 2 S;
(
j1 j2 j3 j1 (fj1g) j2 (fj1; j2g) j3 (fj1; j2; j3g) jm ; jm (S) where (;) normalizes the sum to 1. Further we denote = (S); (k) = (Snfkg);
(fj;kg) = (Snfj; kg); j = j (S) and (k) = j (Snfkg) j for all S
f1; :::; J g and j; k 2 S.
Proposition 1. If detailed balance equations (
j (j) (j) = k (fj;kg) j ; (fj;kg) k; j 6= k; j 6= k; (k) = j (j) = k (fj;kg) j =
(k) (fj;kg) k = (j) (fj;kg) j k ;
k
(fj;kg) j k :
j
(
We denote by (S) the rate at which one of the idle servers becomes busy when the system is in state S. It is clear that the following relations holds for all S f1; :::; J g: (S) = X j (S) = j2S
X
i2C(S)
i:
Proposition 2. The equations (
(j) X k
(k) : k2Snfjg j The proof is by induction on size of S (see Proposition 1 in the paper [2]).
This result shows that the stationary probabilities (
Proposition 3. There exist assignment probabilities Pi;j (S), for all S j 2 S, and i 2 C(S), which satisfy the following relations:
X
i2C(j)
j (S) =
iPi;j (S):
The proof of this statement can be found in Propositions 2-6 in the [2]. It is
important to note that if we choose the assignment probabilities satisfying (
To obtain the probabilities in stability condition (
Pk =
X
j1;:::;jJ k2f1;:::;Jg
(fj1; :::; jJ kg)
for all k 2 f1; :::; J g:
(
In this Section, we consider an example of the new system to show in detail how to nd stationary and assignment probabilities.
Fig.1. Example
Let J = 3, I = 2, C(
2 3 (f2;3g) = (;) 2(f2g) 3(f2;3g);
1 2 3 (f1;2;3g) = (;) 1(f1g) 2(f1;2g) 3(f1;2;3g):
1(f1g) = 1 + 2; 2(f2g) = 1 + 2; 3(f3g) = 1: (f1;2g) = 1 + 2; (f2;3g) = 1 + 2; (f1;3g) = 1 + 2; (f1;2;3g) = 1 + 2:
Similarly, we obtain:
Now we can write down the stationary probabilities (S) by substituting the
obtained above rates i(S) in expression (
P3 = (;):
where, recall, we use normalization condition to nd (;). Now, using (
To check theoretical results presented above, we conduct discrete-event simulation of the system described in Example 1. In addition, we assume that and T (S; t) is the time, in interval [0; t), when the system is in the state S. Also we introduce l(t) (loss rate), the number of customer losses per time unit in interval [0; t).
Fig. 3. Number of losses per time unit in interval [0; t) (Sample mean l(t)): case a) corresponds to row 4 in Table 1; case b) corresponds to row 3 in Table 1; case c) corresponds to row 1 in Table 2; case d) corresponds to row 2 in Table 1.
We obtain the sample mean based on 100 paths of (t) and present their stationary values in Tables 1 and 2. We consider some di erent sets of assignment probabilities: 4 cases violate equation system (16) (see Table 1) and 9 cases satisfy it (see Table 2). To satisfy equation system (16) we can vary P1;1(f1; 2g) and P1;1(f1; 2; 3g) (free variables, marked columns) while other probabilities depend on free variables or are uniquely determined. It is easy to see that (t) in Table 1 is much larger than in Table 2, that con rms that stationary probabilities (17) are found correctly (for cases in Table 2) and the process is reversible. One can see on Fig.2 that (t) converges for both in the cases when the system (16) is satis ed and in the cases when it is violated. We also show that number of customer losses l(t) also converges but for the cases when the system (16) is violated l(t) is not much larger than for the cases when the system (16) is satis ed (see Fig.3). Moreover, case d) shows that we can obtain l(t) less than for the cases when the system (16) is satis ed. This example shows that product form distribution is not optimal to minimize losses.
Finally, we calculate the stability condition (
We consider a modi ed Erlang loss system with multi-class multi-server rst priority customers and a queue for second priority customers. In this work we show that the stationary distribution describing this system has the product form and is the same as in the system considered in the paper [2]. Furthermore, we use these stationary probabilities to calculate the stability condition of the entire system expressed as the upper bound for the tra c intensity generated by the second priority customers. Simulation illustrates that the assignment probabilities, satisfying conditions in the considered example, indeed imply the product form of the stationary distribution. Moreover, we show that the stability condition holds for the example studied in Section 4. On the other hand, simulation also shows that the product form distribution setting is not optimal to minimize the losses in the system. 7
The authors thanks his adviser Prof. Evsey Morozov for help and useful comments.