# Analysis of a Priority Queue with Phase-Type Service and Failures

Authors: Alexander Dudin; Sergei Dudin
Journal: International Journal of Stochastic Analysis
 (2016)

---

## Abstract

We consider a single server queue with two types of customers. We propose a discipline of flexible priority in access that combines the features of randomization and the threshold type control. We introduce a new class of distributions, phase-type with failures (P
H
F) distribution, that generalizes the well-known phase-type (PH) distribution to the case when failures can occur during service of a customer. The arrival flow is described by the marked Markovian arrival process. The service time distribution is of PHF type with the parameters depending on the type of a customer. Customers of both types can be impatient. Behavior of the system is described by the multidimensional Markov chain. Problem of existence and computation of the stationary distribution of this Markov chain is discussed in brief as well as the problem of computation of the key performance measures of the system. Numerical examples are presented that give some insight into behavior of the system performance measures under different values of the parameters defining the strategy of customers access to service.


---

## Body

## 1. Introduction

In this paper, we consider a single server queueing model of information transmission system with two types of customers. Type-1 customers can be queued into the buffer having an infinite capacity. The buffer for type-2 customers has a finite capacity. Such kind of systems quite often describes behavior of various telecommunication systems where type-1 customers are interpreted as delay tolerant and type-2 customers are interpreted as loss tolerant; see, for example, [1]. Existence of two types of customers causes the necessity of managing the discipline of customers access to the server. Popular disciplines are priority (preemptive or nonpreemptive) disciplines in which a priority is given to one of types and customers of another type have a chance to enter service only when the priority customers are absent in the system.However, such disciplines are not appropriate when it is necessary to provide more fair access of customers to the server. In particular, in some real world systems, for example, the vehicular ad hoc networks (VANET) that use the IEEE 802.11p protocol, it is necessary to share the available access time between a Control Channel and Service Channels. The Control Channel is used for the periodical dissemination of control information (beaconing) and traffic safety related information event messages. The Service Channels are used to disseminate noncritical information for infotainment applications; see, for example, [2]. So it is necessary to alternate access to the server by two types of customers, which cannot be achieved via the classical priority discipline.Aiming to provide more fairness in access of customers of different type to the server, in this paper, we do not assume existence of an explicit priority given to one of the types. Instead, we suggest randomized choice of a customer for service when both queues are not empty at a service completion epoch. Priority can be given to one of types implicitly by means of fixing higher probability of a choice for service. If we set equal probabilities of the choice of customers of different types for service, in probabilistic sense, we create good conditions for frequent alternation of the type of a customer in service. However, equal probabilities may be not reasonable when the intensities of two flows are quite different. So it is important to optimally choose the probability defining the randomized access. The problem becomes even more complicated if impatience of customers should be taken into account and customers of one type are more impatient than the customers of another type.In the model under study, we account impatience of customers. Because type-2 customers can be dropped (lost) also due to their buffer overflow, additionally we assume that randomization does not work and type-2 customer is always chosen for service if the number of type-2 customers in the buffer exceeds some predefined threshold. To the best of our knowledge such type of mechanisms of customers access to service was not considered in the literature.One of the popular distributions of service time in queueing literature (and information transmission time in telecommunications literature) is so-called phase-type (PH) distribution. The class of PH distributions is dense (in the sense of a weak convergence) in the set of all probability distributions of nonnegative variables. Thus, the PH distribution is very general and can be used for approximation of an arbitrary distribution; see [3]. However, in real life systems during some phases of service (information transmission), the server may fail. The failure occurrence implies the loss of a customer or the necessity of complete repetition of its service or resuming service from the phase at which the failure occurred. The use of the classical PH distribution does not allow taking into account the failures during the service process effectively. In this paper, we introduce and apply extension of the PH distribution, which we call PHF (phase-type with failures) distribution, that allows taking the failures into account.Last but not least, we consider the model with quite complicated marked Markovian arrival process (MMAP); see [4]. Such arrival process of heterogeneous customers is much more complicated than the superposition of the stationary Poisson processes. But it allows taking into account the bursty correlated nature of information transmission processes in modern telecommunication networks.The rest of the paper is organized as follows. ThePHF distribution is introduced and briefly analyzed in Section 2. Mathematical model of the queueing system under study is described in Section 3. Process of the system states is defined in Section 4. Its generator as a block matrix is written down. The problem of ergodicity of this process is discussed in brief and the algorithm for computation of stationary distribution of the system states is chosen. In Section 5, expressions for computation of various performance measures of the system based on the known stationary distribution of the system states are derived. In Section 6, results of numerical experiments are presented. Section 7 concludes the paper.


## 2. Phase-Type with Failures (PHF) Distribution

In this paper, we consider the queueing model of information transmission system. We assume that errors can occur during the transmission (service of a customer), which can cause the loss of information (customer) or necessity of retransmission (repetition, in full or partial extent, of customer’s service). Thus, to formally describe the service process of an arbitrary customer with account of possible errors, we introduce essential extension of well-knownPH distribution; see, for example, [5]. We call this new distribution PHF (phase-type with failures) distribution. In defining PH distribution, Neuts has interpreted the time having such a distribution as some sequence of random times called phases, durations of which have an exponential distribution. By analogy, we define PHF distribution as some sequence of random times called stages each of which, in turn, consists of a random number of phases. PHF distribution can characterize different positive random variables, for example, interarrival, interretrial, and service times, in some queueing system. Because in this paper we will use this distribution to model the service time in the queueing model described in the next section, for easier interpretation, we will speak here about the PHF type distribution of a service time.ThePHF type distribution of a service time is defined by the continuous-time Markov chain m
t
,
t
≥
0, with a finite state space 1
,
…
,
M
,
M
+
1
,
M
+
2. The states 1
,
…
,
M are assumed to be transient. The initial state of the process m
t at the service beginning moment (which coincides with the moment of the first stage beginning) is chosen among the transient states with probabilities defined by the entries of the stochastic row vector β
=
(
β
1
,
…
,
β
M
)
. The sojourn time of the chain m
t in the state m
,
m
=
1
,
M
¯, is exponentially distributed with the parameter μ
m
. After this time expires, with probability p
m
,
m
′, m
=
1
,
M
¯, m
′
=
1
,
M
+
2
¯, m
′
≠
m, ∑
m
′
=
1
,
m
′
≠
m
M
+
2
‍
p
m
,
m
′
=
1, the process m
t transits to the state m
′. The intensities of the transition between transient states of the process m
t are defined by the subgenerator S that is defined by its entries as follows: (1)
S
m
,
m
=
-
μ
m
,
m
=
1
,
M
¯
,
S
m
,
m
′
=
μ
m
p
m
,
m
′
,
m
=
1
,
M
¯
,
m
′
=
1
,
M
¯
,
m
′
≠
m
.The statesM
+
1 and M
+
2 are the absorbing states transition which corresponds to the end of the current stage of the service. The transition to the absorbing state M
+
1 means the end of the stage and successful completion of customer’s service. The intensities of the transition to the absorbing state M
+
1 are defined by the entries of the column vector S
1: (2)
S
1
m
=
μ
m
p
m
,
M
+
1
,
m
=
1
,
M
¯
.The transition to the absorbing stateM
+
2 means the end of the stage of the service due to a failure occurrence. The intensities of the transition to the absorbing state M
+
2 are defined by the entries of the column vector S
2: (3)
S
2
m
=
μ
m
p
m
,
M
+
2
,
m
=
1
,
M
¯
.Note that S
2
=
-
S
e
-
S
1
. After the transition to the absorbing state M
+
2, the following three scenarios are possible: (i) with probability q
1, service of a customer is completed and this customer leaves the system permanently without successful service (is lost); (ii) with probability q
2, the next stage of service starts and the initial state of the process m
t
,
t
≥
0, is again chosen among the transient states with probabilities defined by the vector β; (iii) with probability 1
-
q
1
-
q
2, the next stage of service starts and the initial state of the process m
t is chosen as the state from which the transition to the absorbing state M
+
2 occurred. In both scenarios (ii) and (iii), the intensities of transition of the process m
t within the set 1
,
…
,
M of the transient states and to the absorbing states are the same as at the first stage of service.So service of a customer finishes when either the processm
t transits to the absorbing state M
+
1 (this customer is considered as successfully served) or the process m
t transits, after some stage, to the absorbing state M
+
2 and scenario (i) is realized (the customer is lost). In interpretation of the service time as transmission time of some information unit (e.g., a file), scenario (ii) means the necessity of complete retransmission of the unit while scenario (iii) means its retransmission from some point where the error occurs.Thus, thePHF distribution is defined by the set consisting of the row vector β, the matrix S, the column vector S
1, and the probabilities q
1 and q
2, while the classical PH distribution is defined only by the row vector β and the matrix S. The pair (
β
,
S
) is called in [5] an irreducible representation of PH distribution. PH distribution can be treated as the special case of PHF when p
m
,
M
+
2
=
0
,
m
=
1
,
M
¯
. By analogy with [5] we call the set (
β
,
S
,
S
1
,
q
1
,
q
2
) an irreducible representation of PHF distribution.Let us describe some properties ofPHF distribution.Leth
(
u
) be Laplace-Stieltjes Transform (LST) of PHF distribution with an irreducible representation (
β
,
S
,
S
1
,
q
1
,
q
2
)
.Lemma 1.
The LSTh
(
u
) is defined by formula (4)
h
u
=
β
h
u
,
Re
⁡
u
>
0
,where the column vector function h
(
u
) is defined by formula (5)
h
u
=
u
I
-
A
-
1
A
0
,where (6)
A
=
S
+
q
2
S
2
β
+
1
-
q
1
-
q
2
diag
⁡
S
2
,
A
0
=
-
A
e
=
S
1
+
q
1
S
2
,where diag
⁡
S
2 means the diagonal matrix with the diagonal entries defined by the entries of the vector S
2, where S
2
=
-
S
e
-
S
1
.Proof of Lemma1 is implemented based on the known probabilistic interpretation of LST. Let us assume that, independently of the system operation, some virtual stationary Poisson flow of some virtual events, sometimes called catastrophes, arrives. Let u be the intensity of this flow.We defineh
(
u
) as the column vector entries, of which (
h
(
u
)
)
m have the meaning of the probability that catastrophe will not arrive during the rest of the time having PHF distribution with an irreducible representation (
β
,
S
,
S
1
,
q
1
,
q
2
) conditioned on the fact that at the given moment the underlying Markov chain m
t of this distribution stays at the state m
,
m
=
1
,
M
¯
.Using this probabilistic interpretation and formula of total probability, it is easy to derive formula(7)
h
u
=
∫
0
∞
e
-
u
I
+
S
t
S
1
+
diag
⁡
S
2
q
1
e
+
q
2
e
β
h
u
+
1
-
q
1
-
q
2
h
u
d
t
=
-
u
I
+
S
-
1
S
1
+
diag
⁡
S
2
q
1
e
+
q
2
e
β
h
u
+
1
-
q
1
-
q
2
h
ufrom which and formula of total probability the statement of Lemma 1 immediately follows.Remark 2.
It can be noted thatLST of PHF distribution with an irreducible representation (
β
,
S
,
S
1
,
q
1
,
q
2
) coincides with LST of a classical PH distribution with an irreducible representation (
β
,
A
)
. It is well known for the classical PH distribution that its LST is easily calculated given the irreducible representation. However, the inverse problem, to restore the irreducible representation given the values of LST, is very complicated and does not have a unique solution, while, namely, the components of the irreducible representation are necessary to write down the generator of the Markov chain describing behavior of the states of some queueing system with PH service process. Analogously, the noted coincidence of LST of PHF distribution with an irreducible representation (
β
,
S
,
S
1
,
q
1
,
q
2
) with LST of a classical PH distribution with an irreducible representation (
β
,
A
) does not imply that we can avoid introduction of PHF distribution and substitute this distribution by the classical PH distribution.Corollary 3.
The momentsW
k of P
H
F distribution with an irreducible representation (
β
,
S
,
S
1
,
q
1
,
q
2
) are calculated by formula (8)
W
k
=
k
!
β
-
A
-
k
e
,
k
≥
1
.In particular, the expectation is given by W
1
=
β
(
-
A
)
-
1
e.Leth
1
(
u
) be LST of the distribution of the service time which is finished successfully (probability that the service time is finished successfully and no catastrophe arrives during this time) and let h
2
(
u
) be LST of the distribution of the service time that is finished by a customer loss (probability that the service time is finished by a customer loss and no catastrophe arrives during this time).Lemma 4.
TheL
S
Ts h
1
(
u
) and h
2
(
u
) are defined by formulas (9)
h
1
u
=
β
u
I
-
A
-
1
S
1
,
Re
⁡
u
>
0
,
h
2
u
=
q
1
β
u
I
-
A
-
1
S
2
,
Re
⁡
u
>
0
.Proof of Lemma4 uses similar arguments as the proof of Lemma 1.Corollary 5.
The probabilityP
s
u
c
c
e
s
s that an arbitrary service will be finished successfully and the probability P
f
a
i
l
u
r
e that an arbitrary service will be finished by a customer’s loss are given by (10)
P
s
u
c
c
e
s
s
=
h
1
0
=
β
-
A
-
1
S
1
,
P
f
a
i
l
u
r
e
=
h
2
0
=
q
1
β
-
A
-
1
S
2
.Corollary 6.
The average service timesW
1
s
u
c
c
e
s
s (W
1
f
a
i
l
u
r
e) of an arbitrary customer conditioned on the fact that it is known that service is finished successfully (is failed) are computed as follows: (11)
W
1
s
u
c
c
e
s
s
=
β
-
A
-
2
S
1
β
-
A
-
1
S
1
,
W
1
f
a
i
l
u
r
e
=
β
-
A
-
2
S
2
β
-
A
-
1
S
2
.


## 3. Mathematical Model

We consider a single server queueing system with an infinite buffer and a finite buffer of capacityN, the structure of which is presented in Figure 1.Figure 1
Queueing system under study.Arrival of two types of customers is defined by theMMAP. This process is defined by the irreducible continuous-time Markov chain ν
t
,
t
≥
0, having a finite state space 0,1
,
…
,
W. The sojourn time of the chain ν
t in the state ν is exponentially distributed with the parameter λ
ν. After this time expires, with probability p
ν
,
ν
′
(
0
) the chain ν
t jumps to the state ν
′ without generation of customers, ν
,
ν
′
=
0
,
W
¯
,
ν
≠
ν
′, or with probability p
ν
,
ν
′
(
r
) it jumps to the state ν
′ with generation of type-r customer, r
=
1,2, ν
,
ν
′
=
0
,
W
¯. Here notation ν
=
0
,
W
¯ means that ν takes the values in the set 0,1
,
…
,
W.It is reasonable to store the set of numerous parameters, which characterize theMMAP, as the entries of the square matrices D
0
,
D
r
,
r
=
1,2, defined as follows. The entry (
D
r
)
ν
,
ν
′
=
λ
ν
p
ν
,
ν
′
(
r
), ν
,
ν
′
=
0
,
W
¯, r
=
1,2, of the matrix D
r defines the intensity of transition of the process ν
t from the state ν to the state ν
′ which is accompanied by arrival of type-r customer. The modulus of the diagonal entry (
D
0
)
ν
,
ν of the matrix D
0 defines intensity of departure of the process ν
t from the state ν
:
(
D
0
)
ν
,
ν
=
-
λ
ν
,
ν
=
0
,
W
¯. The nondiagonal entry (
D
0
)
ν
,
ν
′
=
λ
ν
p
ν
,
ν
′
(
0
), ν
,
ν
′
=
0
,
W
¯, ν
≠
ν
′, of the matrix D
0 defines the intensity of transition of the process ν
t from the state ν to the state ν
′ which is not accompanied by arrival of any customer.The matrixD
(
1
)
=
D
0
+
D
1
+
D
2 is the generator of the Markov chain ν
t
,
t
≥
0. The average intensity of customers arrival (fundamental rate) λ is defined by the formula λ
=
θ
(
D
1
+
D
2
)
e, where θ is the row vector of the stationary probabilities of the Markov chain ν
t. This vector is the unique solution to the system θ
D
(
1
)
=
0, θ
e
=
1
. Here and throughout this paper e is a column vector of appropriate size consisting of 1’s, and 0 is a row vector of appropriate size consisting of zeroes. The average intensity of type-r customers arrival λ
r is defined by the formula λ
r
=
θ
D
r
e
,
r
=
1,2.We assume that the service times of type-1 and type-2 customers havePHF distribution with the parameters depending on the type of a customer. Namely, we assume that parameters of PHF distribution of service time of type-r, r
=
1,2, customers are given by the irreducible representation (
β
(
r
)
,
S
(
r
)
,
S
1
(
r
)
,
q
1
(
r
)
,
q
2
(
r
)
)
. Let M
r
,
r
=
1,2, be the number of transient states of underlying Markov chain of PHF service process of type-r customers.If the server is idle during an arbitrary customer arrival epoch, the customer immediately starts service. If the server is busy during an arbitrary type-1 customer arrival epoch, this customer goes to the infinite buffer. If the server is busy during an arbitrary type-2 customer arrival epoch, this customer goes to the finite buffer of capacity N. If this buffer is full, the customer is lost.We assume the following strategy of choosing the customers for service. Let some probabilityp
,
0
≤
p
≤
1, and threshold K
,
0
≤
K
≤
N, be fixed. If, during the service completion epoch, there are customers in both buffers and the number of type-2 customers is less than or equal to K, then type-1 customer is chosen for service with probability p or type-2 customer occupies the server with the complimentary probability. If, during the service completion epoch, the number of type-2 customers is greater than K, then type-2 customers are chosen for service. If one of the buffers is empty at the service completion epoch, service is provided to the customer from another buffer, if any, without randomization. Note that if p
=
0 or K
=
0, then type-1 customer can be chosen for service only if type-2 customers are absent in the system. This means that type-2 customers have nonpreemptive priority over type-1 customers. If p
=
1, then type-2 customers are chosen for service only if the number of such customers in the buffer exceeds the value K. In other words, if the number of type-2 customers in the buffer does not exceed the threshold K, type-1 customers have nonpreemptive priority over type-2 customers. Thus, the considered admission strategy is essentially more flexible than the strategy with nonpreemptive priority.The customers in the buffers are assumed to be impatient; for example, each type-r customer leaves the buffer after an exponentially distributed, with the parameter α
r
,
α
r
≥
0
,
r
=
1,2, amount of time due to the lack of service.Let us analyze the stochastic process defining behavior of the described queueing model.


## 4. Process of System States and Its Stationary Distribution

Let, during the epocht
,
t
≥
0,(i)
i
t
,
i
t
≥
0, be the number of type-1 customers in the buffer;
(ii)
n
t
,
n
t
∈
0,1
,
2, be the state of the server (n
t
=
0 when the server is idle, n
t
=
1 when the server is occupied by type-1 customer, and n
t
=
2 when the server provides service to type-2 customer);
(iii)
k
t
,
k
t
=
0
,
N
¯, be the number of type-2 customers in the buffer;
(iv)
ν
t
,
ν
t
=
0
,
W
¯, be the state of the underlying process of the MMAP;
(v)
η
t be the state of PH service process, η
t
=
1
,
M
n
t
¯.The Markov chainξ
t
=
i
t
,
n
t
,
k
t
,
ν
t
,
η
t
,
t
≥
0, is the regular irreducible continuous-time Markov chain.The Markov chainξ
t
,
t
≥
0, has the following state space: (12)
0,0
,
0
,
ν
∪
i
,
n
,
k
,
ν
,
η
,
i
≥
0
,
n
=
1,2
¯
,
k
=
0
,
N
¯
,
η
=
1
,
M
n
¯
,
ν
=
0
,
W
¯
.Let us introduce the following notations:(i)
I is the identity matrix and O is a zero matrix of appropriate dimension. If it is necessary, dimension of the matrix is indicated by the suffix.
(ii)
N
¯
=
N
+
1, W
¯
=
W
+
1.
(iii)
C is the square matrix of size N
¯ defined as follows: C
=
diag
⁡
0,1
,
…
,
N; that is, C is the diagonal matrix with the diagonal entries 0,1
,
…
,
N.
(iv)
E
- is the square matrix of size N
¯ with all zero entries except the entries (
E
-
)
k
,
k
-
1
,
k
=
1
,
N
¯, which are equal to 1.
(v)
E
1
- is the square matrix of size N
¯ with all zero entries except the entries (
E
1
-
)
k
,
k
-
1
,
k
=
1
,
K
¯, which are equal to 1.
(vi)
E
2
- is the square matrix of size N
¯ with all zero entries except the entries (
E
2
-
)
k
,
k
-
1
,
k
=
K
+
1
,
N
¯, which are equal to 1.
(vii)
E
+ is the square matrix of size N
¯ with all zero entries except the entries (
E
+
)
k
,
k
+
1
,
k
=
0
,
N
-
1
¯, and (
E
+
)
N
,
N which are equal to 1.
(viii)
e
~ is the column vector of size N
¯ with all zero entries except the entry e
~
0 which is equal to 1.
(ix)
I
^
l
,
l
=
0
,
K, is the square matrix of size N
¯ with all zero entries except the entries (
I
^
l
)
k
,
k
=
1
,
k
≤
l.
(x)
⊗ is the symbol of the Kronecker product of matrices; see, for example, [6].Let us enumerate the states of the Markov chainξ
t in the lexicographic order and refer to the set of states of the chain having value i of the first components of the Markov chain aslevel
i
,
i
≥
0
.LetQ be the generator of the Markov chain ξ
t
,
t
≥
0
.Lemma 7.
The generatorQ has the following block-three-diagonal structure: (13)
Q
=
Q
0,0
Q
0,1
O
O
O
⋯
Q
1,0
Q
1,1
Q
+
O
O
⋯
O
Q
2,1
Q
2,2
Q
+
O
⋯
⋮
⋮
⋮
⋮
⋮
⋱
.
The nonzero blocksQ
i
,
j
,
i
,
j
≥
0, containing the intensities of the transitions from level i to level j have the following form: (14)
Q
0,0
=
Q
0,0
Q
0,1
Q
0,2
Q
1,0
Q
1,1
Q
1,2
Q
2,0
O
Q
2,2
,where (15)
Q
0,0
=
D
0
,
Q
0
,
r
=
e
~
T
⊗
D
r
⊗
β
r
,
r
=
1,2
,
Q
1,1
=
I
N
¯
⊗
D
0
⊕
S
1
+
E
+
⊗
D
2
⊗
I
M
1
+
1
-
α
2
C
I
N
+
1
-
E
-
⊗
I
W
¯
M
1
+
1
+
q
2
1
I
N
¯
W
¯
⊗
S
2
1
β
1
+
1
-
q
1
1
-
q
2
1
I
N
¯
W
¯
⊗
diag
⁡
S
2
1
l
,
l
=
1
,
M
1
¯
,
Q
r
,
0
=
e
~
⊗
I
W
¯
⊗
q
1
r
S
2
r
+
S
1
r
,
r
=
1,2
,
Q
1,2
=
E
-
⊗
I
W
¯
⊗
q
1
1
S
2
1
+
S
1
1
β
2
,
Q
2,2
=
I
N
¯
⊗
D
0
⊕
S
2
+
E
+
⊗
D
2
⊗
I
M
2
+
1
-
α
2
C
I
N
+
1
-
E
-
⊗
I
W
¯
M
2
+
1
+
q
2
2
I
W
¯
⊗
S
2
2
β
1
+
1
-
q
1
2
-
q
2
2
I
W
¯
⊗
diag
⁡
S
2
2
l
,
l
=
1
,
M
2
¯
+
E
-
⊗
I
W
¯
⊗
q
1
2
S
2
2
+
S
1
2
β
2
;
Q
i
,
i
=
Q
i
,
i
1,1
Q
0
1,2
O
Q
i
,
i
2,2
,
i
>
0
,where (16)
Q
i
,
i
1,1
=
I
N
¯
⊗
D
0
⊕
S
1
+
E
+
⊗
D
2
⊗
I
M
1
+
1
-
α
2
C
I
N
+
1
-
E
-
+
i
α
1
I
N
¯
⊗
I
W
¯
M
1
+
1
+
q
2
1
I
N
¯
W
¯
⊗
S
2
1
β
1
+
1
-
q
1
1
-
q
2
1
I
W
¯
N
¯
⊗
diag
⁡
S
2
1
l
,
l
=
1
,
M
1
¯
,
Q
i
,
i
2,2
=
I
N
¯
⊗
D
0
⊕
S
2
+
E
+
⊗
D
2
⊗
I
M
2
+
1
-
α
2
C
I
N
+
1
-
E
-
+
i
α
1
I
N
¯
⊗
I
W
¯
M
2
+
1
+
q
2
2
I
N
¯
W
¯
⊗
S
2
2
β
1
+
1
-
q
1
2
-
q
2
2
I
N
¯
W
¯
⊗
diag
⁡
S
2
2
l
,
l
=
1
,
M
2
¯
+
1
-
p
E
1
-
+
E
2
-
⊗
I
W
¯
⊗
q
1
2
S
2
2
+
S
1
2
β
2
,
Q
0
1,2
=
1
-
p
E
1
-
+
E
2
-
⊗
I
W
¯
⊗
q
1
1
S
2
1
+
S
1
1
β
2
;
Q
0,1
=
O
W
¯
×
N
¯
W
¯
M
1
+
1
O
W
¯
×
N
¯
W
¯
M
2
+
1
I
N
¯
⊗
D
1
⊗
I
M
1
+
1
O
O
I
N
¯
⊗
D
1
⊗
I
M
2
+
1
;
Q
+
=
I
N
¯
⊗
D
1
⊗
I
M
1
+
1
O
O
I
N
¯
⊗
D
1
⊗
I
M
2
+
1
;
Q
1,0
=
O
N
¯
W
¯
M
1
+
1
×
W
¯
Q
1,0
1,1
Q
-
1,2
O
N
¯
W
¯
M
2
+
1
×
W
¯
O
Q
1,0
2,2
,
Q
i
,
i
-
1
=
Q
i
,
i
-
1
1,1
O
Q
-
2,1
Q
i
,
i
-
1
2,2
,
i
>
1
,where (17)
Q
i
,
i
-
1
1,1
=
i
α
1
I
N
¯
W
¯
M
1
+
1
+
I
^
0
+
p
I
^
K
-
I
^
0
⊗
I
W
¯
⊗
q
1
1
S
2
1
+
S
1
1
β
1
,
i
>
0
,
Q
i
,
i
-
1
2,2
=
i
α
1
I
N
¯
W
¯
M
2
+
1
,
i
>
0
,
Q
-
2,1
=
p
I
^
K
-
I
^
0
+
I
^
0
⊗
I
W
¯
⊗
q
1
2
S
2
2
+
S
1
2
β
1
.Proof of the lemma is performed by means of analysis of the intensities of all possible transitions of the Markov chainξ
t during the time interval having infinitesimal length.Remark 8.
The Markov chainξ
t
,
t
≥
0, belongs to the class of continuous-time asymptotically quasi-Toeplitz Markov chains (AQTMC); see [7]. This is easily verified by means of checking all points of definition of AQTMC given in [7].Using results from [7], it is possible to show that if α
1
>
0, the Markov chain ξ
t is ergodic for any set of the system parameters.Let us consider the caseα
1
=
0. In this case, the matrices Q
i
,
i
-
1 and Q
i
,
i for i
>
1 do not depend on i and have the following form: (18)
Q
i
,
i
-
1
=
Q
-
=
I
^
0
+
p
I
^
K
-
I
^
0
⊗
I
W
¯
⊗
q
1
1
S
2
1
+
S
1
1
β
1
O
p
I
^
K
-
I
^
0
+
I
^
0
⊗
I
W
¯
⊗
q
1
2
S
2
2
+
S
1
2
β
1
O
,
Q
i
,
i
=
Q
0
=
Q
0,0
1,1
Q
0
1,2
O
Q
0,0
2,2
.Thus, in the caseα
1
=
0, the Markov chain ξ
t
,
t
≥
0, belongs to the class of continuous-time quasi-Toeplitz Markov chains (QTMC) or quasi-birth-and-death processes; see [5].It follows from [5] that the necessary and sufficient ergodicity condition of the quasi-birth-and-death process is the fulfillment of the inequality (19)
y
Q
-
e
>
y
Q
+
e
,where the row vector y is the unique solution to the following system of linear algebraic equations: (20)
y
Q
-
+
Q
0
+
Q
+
=
0
,
y
e
=
1
.The ergodicity condition for the considered model is easily verified algorithmically. Finite system (20) of linear algebraic equation is solved on computer. Then, fulfillment of inequality (19) is checked.If the ergodicity condition is fulfilled, then the following limits (stationary probabilities) exist:(21)
π
i
,
n
,
k
,
ν
,
η
=
lim
t
→
∞
⁡
P
i
t
=
i
,
n
t
=
n
,
k
t
=
k
,
ν
t
=
ν
,
η
t
=
η
,
i
≥
0
,
n
=
0,2
¯
,
k
=
0
,
N
¯
,
ν
=
0
,
W
¯
,
η
t
=
1
,
M
n
¯
.Let us form the row vectorsπ
(
i
,
n
,
k
), π
(
i
,
n
), π
i of these probabilities as follows: (22)
π
0,0
,
0
=
π
0,0
,
0,0
,
π
0,0
,
0,1
,
…
,
π
0,0
,
0
,
W
,
π
i
,
n
,
k
,
ν
=
π
i
,
n
,
k
,
ν
,
1
,
π
i
,
n
,
k
,
ν
,
2
,
…
,
π
i
,
n
,
k
,
ν
,
M
n
,
ν
=
0
,
W
¯
,
π
i
,
n
,
k
=
π
i
,
n
,
k
,
0
,
π
i
,
n
,
k
,
1
,
…
,
π
i
,
n
,
k
,
W
,
k
=
0
,
N
¯
,
π
i
,
n
=
π
i
,
n
,
0
,
π
i
,
n
,
1
,
…
,
π
i
,
n
,
N
,
n
=
1,2
,
π
0
=
π
0,0
,
π
0,1
,
π
0,2
,
π
i
=
π
i
,
1
,
π
i
,
2
,
i
>
0
.It is well known that the probability vectorsπ
i
,
i
≥
0, satisfy the following system of linear algebraic equations: (23)
π
0
,
π
1
,
…
Q
=
0
,
π
0
,
π
1
,
…
e
=
1
, called equilibrium or Chapman-Kolmogorov equations. This system is infinite and the generator Q, generally speaking, does not possess Toeplitz-like property. So the system cannot be directly solved on computer. Such type of equations arises quite often in analysis of queues with impatient customers and retrial queueing systems. Usually in the literature they are solved by means of various truncation methods. Indeed, this system can be effectively solved by means of the numerically stable algorithm that is presented in [8].


## 5. Performance Measures of the System

Having computed the vectors of the stationary probabilitiesπ
i
,
i
≥
0, it is possible to compute a variety of the performance measures of the system.The average number of customers in the system is computed by(24)
L
=
∑
i
=
0
∞
∑
n
=
1
2
∑
k
=
0
N
k
+
i
+
1
π
i
,
n
,
k
e
.The probabilityP
busy that the server is busy at an arbitrary moment is computed by (25)
P
busy
=
∑
i
=
0
∞
∑
n
=
1
2
π
i
,
n
e
.The probabilityP
busy-
l that, at an arbitrary moment, the server provides service to type-l customer is computed by (26)
P
busy-
l
=
∑
i
=
0
∞
π
i
,
l
e
,
l
=
1,2
.The probabilityP
idle that the server is idle at an arbitrary moment is computed by (27)
P
idle
=
π
0,0
e
.The average numberN
buffer
type-
1 of type-1 customers in the buffer is computed by (28)
N
buffer
type-
1
=
∑
i
=
1
∞
i
π
i
e
.The average numberN
buffer
type-
2 of type-2 customers in the buffer is computed by (29)
N
buffer
type-
2
=
∑
i
=
0
∞
∑
n
=
1
2
∑
k
=
1
N
k
π
i
,
n
,
k
e
.The intensityλ
out
type-
l
,
l
=
1,2, of the output flow of successfully served type-l customers is computed by (30)
λ
out
type-
l
=
∑
i
=
0
∞
π
i
,
l
e
N
+
1
W
¯
⊗
S
1
l
,
l
=
1,2
.The intensityλ
failure-loss
type-
l
,
l
=
1,2, of the flow of type-l customers that leave the system due to the failure occurrence is computed by (31)
λ
fail
type-
l
=
q
1
l
∑
i
=
0
∞
π
i
,
l
e
N
+
1
W
¯
⊗
S
2
l
,
l
=
1,2
.The loss probabilityP
ent-loss
type-
2 of an arbitrary type-2 customer upon arrival due to the buffer overflow is computed by (32)
P
ent-loss
type-
2
=
1
λ
2
∑
i
=
0
∞
∑
n
=
1
2
π
i
,
n
,
N
D
2
⊗
I
M
n
e
.The loss probabilityP
imp-loss
type-
1 of an arbitrary type-1 customer due to impatience is computed by (33)
P
imp-loss
type-
1
=
α
1
N
buffer
type-
1
λ
1
=
1
λ
1
∑
i
=
1
∞
∑
n
=
1
2
∑
k
=
0
N
i
α
1
π
i
,
n
,
k
e
.The loss probabilityP
imp-loss
type-
2 of an arbitrary type-2 customer due to impatience is computed by (34)
P
imp-loss
type-
2
=
α
2
N
buffer
type-
2
λ
2
=
1
λ
2
∑
i
=
0
∞
∑
n
=
1
2
∑
k
=
1
N
k
α
2
π
i
,
n
,
k
e
.The probabilityP
failure-loss
type-
l of an arbitrary type-l customer loss due to a failure occurrence is computed by (35)
P
failure-loss
type-
l
=
λ
fail
type-
l
λ
l
,
l
=
1,2
.The probabilityP
loss
type-
l of an arbitrary type-l customer loss is computed by (36)
P
loss
type-
l
=
1
-
λ
out
type-
l
λ
l
,
l
=
1,2
.


## 6. Numerical Example

In the numerical example we assume that the finite buffer capacity isN
=
10. The value of the threshold K is set to be equal to 8.TheMMAP arrival process has the coefficient of correlation c
cor
=
0.2 and the coefficient of variation c
v
a
r
=
12.3 and is defined by the matrices (37)
D
0
=
-
6.759
0
0
-
0.21941
,
D
1
=
4.476
0.03
0.08144
0.06483
,
D
2
=
2.238
0.015
0.04072
0.03242
.The average arrival rate of this process isλ
=
5, the average arrival rate of type-1 customers is λ
1
=
3.33, and the average arrival rate of type-2 customers is λ
2
=
1.67.The intensities of impatience of type-l customers, l
=
1,2, are α
1
=
0.02 and α
2
=
0.05.To illustrate importance of taking into account possible failures in the service process, let us consider two cases of service processes. In the first case, coded asPH, we assume that service of the customers is modelled by two phase-type service processes. Namely, we assume that the service time of type-1 customers is defined by the vector β
(
1
)
=
(
0.8,0.2
) and the matrix S
(
1
)
=
-
12
9
0
-
12. The mean service time is equal to 0.13333
. The service time of type-2 customers is defined by the vector β
(
2
)
=
(
0.6,0.1,0.3
) and the matrix S
(
2
)
=
-
10
4
3
3
-
10
5
1
1
-
10. The mean service time is equal to 0.21582.In the second case, coded asPHF, we assume that the service times of the customers have PHF distributions with irreducible representations (38)
β
l
,
S
l
,
S
1
l
,
q
1
l
,
q
2
l
,
l
=
1,2
,where β
(
l
) and S
(
l
)
,
l
=
1,2, are the same as in the first case and (39)
S
1
1
=
2.6,11.2
T
,
S
1
2
=
2.7,1.7,7.3
T
,
q
1
1
=
0.1
,
q
1
2
=
0.3
,
q
2
1
=
0.05
,
q
2
2
=
0.4
.Let us vary the parameterp from 0 to 1 with the step 0.01.Figures2 and 3 illustrate the dependence of the loss probabilities P
loss
type-
1 and P
l
o
s
s
t
y
p
e
-
2 on the parameter p.Figure 2
Dependence of the loss probabilityP
loss
type-
1 on the parameter p.Figure 3
Dependence of the loss probabilityP
loss
type-
2 on the parameter p.The quite essential difference between values of the loss probabilityP
loss
type-
l,  l
=
1,2, for case 1 when the service time has PH distribution and case 2 when the service time has PHF distribution is worth noting, while the differences between the average service times are not so essential. For type-1 customer the average value of the service time having PH distribution is equal, as mentioned above, to 0.13333. The average value of the service time having PHF distribution is equal to 0.14143 (the probability P
success that an arbitrary service will be finished successfully is equal to 0.9914). For type-2 customer the average value of the service time having PH distribution is equal, as mentioned above, to 0.21582. The average value of service time having PHF distribution is equal to 0.2307 (the probability P
success that an arbitrary service will be finished successfully is equal to 0.9688).Now, let us illustrate the dependence of the main performance measures of the system on the parametersK and p that define the strategy of customers access to the server. To this end let us consider the system with PHF service time distribution of type-1 and type-2 customers defined above and vary the parameter p from 0 to 1 with step 0.01 and the parameter K from 1 to 10 with step 1.Figures4 and 5 illustrate the dependence of the loss probabilities P
loss
type-
1 and P
loss
type-
2 on the parameters K and p.Figure 4
Dependence of the loss probabilityP
loss
type-
1 on the parameters K and p.Figure 5
Dependence of the loss probabilityP
loss
type-
2 on the parameters K and p.Figures6 and 7 illustrate the dependence of the loss probabilities P
failure-loss
type-
1 and P
failure-loss
type-
2 on the parameters K and p.Figure 6
Dependence of the loss probabilityP
failure-loss
type-
1 on the parameters K and p.Figure 7
Dependence of the loss probabilityP
failure-loss
type-
2 on the parameters K and p.Figures8 and 9 illustrate the dependence of the loss probability P
ent-loss
type-
2 and the probability P
busy on the parameters K and p.Figure 8
Dependence of the loss probabilityP
ent-loss
type-
2 on the parameters K and p.Figure 9
Dependence of the probabilityP
busy on the parameters K and p.As it is seen from Figures4 and 5, the loss probability of type-1 customers decreases and the loss probability of type-2 customers increases with growth of the parameters p and K. This finding can be explained as follows. With increasing of p and K, type-1 customers are more often chosen for service, so they obtain the better conditions and the probability of their loss decreases. Since type-2 customers are competing for the server with type-1 customers, their loss probability grows. However we can see the opposite trend in Figures 6 and 7: the loss probability P
failure-loss
type-
1 increases and the loss probability P
failure-loss
type-
2 decreases with increasing of K and p. This can be explained as follows. When p and K are small, type-1 customers are rarely chosen for service and they are lost, basically, due to impatience before service. So the probability of an arbitrary type-1 customer loss due to a failure occurrence during its service is small. When the parameters p and K grow, the chance to start service for type-1 customer increases and the probability P
failure-loss
type-
1 also increases. For type-2 customers, we see the opposite situation and the loss probability P
failure-loss
type-
2 decreases with increasing of K and p.As it is seen from Figure8 the loss probability P
ent-loss
type-
2 of an arbitrary type-2 customer upon arrival due to the buffer overflow essentially increases with increase of K and p. Due to this fact, the probability P
busy that the server is busy at an arbitrary moment that is presented in Figure 9 decreases with growth of K and p.Let us introduce the value(40)
E
=
λ
1
P
loss
type-
1
+
λ
2
P
loss
type-
2
.This value has the meaning of an average number of customers lost in the system per unit of time and may be considered as some kind of cost criterion of quality of the system operation. It is obvious that the value E depends on the probability p and the threshold K that defines the strategy of customers access to the server; that is, E
=
E
(
K
,
p
).Figure10 illustrates the dependence of the values of the cost criterion E
(
K
,
p
) on the parameters K and p.Figure 10
Dependence of the cost criterionE
(
K
,
p
) on the parameters K and p.The minimal valueE
∗
(
K
,
p
) of the cost criterion E
(
K
,
p
) is E
∗
(
6,0.8
)
=
0.447533. So the admission control of customers can bring some profit even in terms of this trivial cost criterion. Note that variety of various optimization problems where the weighted sum of some performance measures should be minimized or maximized under restrictions imposed on the values of other performance measures can be formulated and solved based on the results of probabilistic analysis presented in this paper.


## 7. Conclusion

We analyzed a queueing model with a single server which provides service for two types of customers. The system has a finite buffer for one type of customers and an infinite one for another type. Service to customers of the same type is provided according to first in-first out discipline. If both buffers are not empty at the moment of the service completion, a type of the next customer, which will be picked up for service, is defined randomly, if the number of customers in a finite buffer does not exceed some preassigned threshold. Errors can occur during service of customers. To simplify account of these errors, which may lead to a customer loss, repeated service, or partial repeated service, notion of phase-type distribution with failures (PHF) was introduced in this paper. Customers of both types are impatient. This queueing model can be used, for example, for approximating the process of information transmission using the protocol of time division between Control Channel and Service Channels. The stationary distribution of five-dimensional Markov chain defining the dynamics of the system is computed and expressions for the key performance measures of the system are derived. Results of numerical examples illustrating effect of parameters of customer’s admission strategy are presented.



---

*Source: 9152701-2016-07-17.xml*