# Analysis of Multiserver Queueing System with Opportunistic Occupation and Reservation of Servers

Authors: Bin Sun; Moon Ho Lee; Sergey A. Dudin; Alexander N. Dudin
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We consider a multiserver queueing system with two input flows. Type-1 customers have preemptive priority and are lost during arrival only if all servers are occupied by type-1 customers. If all servers are occupied, but some provide service to type-2 customers, service of type-2 customer is terminated and type-1 customer occupies the server. If the number of busy servers is less than the thresholdM during type-2 customer arrival epoch, this customer is accepted. Otherwise, it is lost or becomes a retrial customer. It will retry to obtain service. Type-2 customer whose service is terminated is lost or moves to the pool of retrial customers. The service time is exponentially distributed with the rate dependent on the customer’s type. Such queueing system is suitable for modeling cognitive radio. Type-1 customers are interpreted as requests generated by primary users. Type-2 customers are generated by secondary or cognitive users. The problem of optimal choice of the threshold M is the subject of this paper. Behavior of the system is described by the multidimensional Markov chain. Its generator, ergodicity condition, and stationary distribution are given. The system performance measures are obtained. The numerical results show the effectiveness of considered admission control.


---

## Body

## 1. Introduction

Multiserver queueing system considered in this paper can be applied for modelling various real life systems. But the primary motivation of its consideration was potential applicability for modelling, performance evaluation, capacity planning, and optimizing cognitive radio systems. Recently, the technology of cognitive radio has attracted considerable attention of many researchers as a promising technology for optimization of the utilization of scare radio frequency spectrum. Dynamic spectrum access allows effective use of radio frequency and prevents its underutilization in many real world networks. It enables unlicensed users to temporarily “borrow” unused spectrum while ensuring that the rights of the incumbent license holders are respected [1]. Problems of optimization of joint access of the primary and secondary users can be effectively solved by means of queueing theory. So, although the term cognitive radio was first introduced in [2] only recently (in 1999), the literature devoted to application of queueing theory to cognitive radio is already extensive. A comprehensive survey [3] devoted to cognitive radio was published in 2006. A search in the database Scopus (using the key words “cognitive radio queue”) gives today (the end of November, 2013) 143 references since 2007 including 31 references to papers published in 2013 and 44 published in 2012. Thus, in this paper we will not try to give more or less detailed survey of the existing results. The reader may get some knowledge about the state of the art in this field, for example, from the papers [1, 3–5].As a rule, it is suggested in the considered models that the primary customers have preemptive priority over the secondary customers. A primary customer is lost during its arrival epoch only if all servers are occupied by primary customers. If all servers are occupied, but at least one of them provides service to the secondary customer, service of one secondary customer is terminated and the primary customer occupies the server. The forced termination of service of the secondary customers may imply at least two negative consequences: dissatisfaction of the secondary customers by the quality of service and wasting the throughput (bandwidth) due to the loss of some already done work. So, it is desirable to introduce some kind of control by admission of the secondary customers. For example, it sounds reasonable to stop admission of the secondary customers when the number of busy servers is large (more than some threshold) and, correspondingly, the risk of the forced termination of service of the secondary customers is high.Such a kind of admission control was offered, for example, in [6]. It was shown in [6] that the appropriate choice of the threshold may lead to maximization of the throughput of the system. In the model considered in our paper, we apply essentially the same strategy of admission control as the one in [6]. If the total number of servers is equal to N, we fix the threshold M,  0<M≤N. We assume that the secondary customer is accepted for service in the system only if the number of busy servers during its arrival epoch is less than M. The case M=N corresponds to the system without restriction of access. As disadvantage of our model comparing to the one considered in [6] we may mention our assumption that both types of the customers need for their processing exactly one server, while it is assumed in [6] that a primary customer occupies a whole group of servers (channel) and a secondary customer occupies one server (subchannel). The advantages of our model comparing to the one considered in [6] and to the overwhelming majority of the papers devoted to analysis of cognitive radio by means of queueing theory are as follows.(i)
We assume that arrival flow of primary and secondary customers is described by the marked Markovian arrival process (MMAP). This process is the generalization of well-known Markovian arrival process (MAP) to the case of heterogeneous customers. The MAP arrival process was introduced as a versatile Markovian point process (VMPP) by M.F. Neuts in the 70th. The original development of the VMPP contained extensive notations; however these notations were greatly simplified in [7] and ever since this process bears the name Markovian arrival process. The class of MAPs includes many input flows considered previously, such as stationary Poisson (M), Erlangian (Ek), hyper-Markovian (HM), phase-type (PH), and Markov modulated Poisson process (MMPP). Generally speaking, the MAP is correlated, so it is ideal to model correlated and or bursty traffic in the modern telecommunication networks; see, for example, [8, 9]. In [6] and practically all other papers, it is assumed that the arrival flows of primary and secondary customers are stationary Poisson. The stationary Poisson arrival process is the simplest case of the MAP. If one tries to describe some real life flow based on its traces by means of the stationary Poisson arrival process, he or she is able to fit only the mean arrival rate, but not the variance or higher moments of interarrival times and possible correlation between these times. Analysis of the systems with the MAP is much more complicated comparing to analysis of the system with the stationary Poisson arrival process. It is not possible to get simple formulas for the performance measures of the system. Instead, numerical algorithms should be developed. However, careful account of the correlation and possible high variability in the arrival process is necessary to get satisfactory prediction of values of performance measures. So, the MAP is now popular in the literature.(ii)
We assume that the secondary customer, which is not granted immediate access to the system during its arrival epoch, has options to leave the system permanently or to go to some virtual place called in the literature as orbit and retry to get access to the system after a random amount of time. We do not know papers where effect of retrials is taken into account for the secondary customers, while the retrials are a typical feature of many telecommunication networks. It is worth to mention here good survey of research in retrial queues given by A. Gomez-Corral in [10].(iii)
We allow the secondary customers to be nonpersistent (to leave the system after some unsuccessful retrial) and (or) nonpatient (to leave the system after some random period of staying in orbit).The mentioned above disadvantage of our model consisting of assumption that both types of the customers need for processing one server, while in some systems another number of servers can be required, can be eliminated by means of considering generalization of our model to the case of the batch marked Markovian arrival process (BMMAP). Technique of analysis will be essentially the same with larger blocks of generator of the underlying Markov chain.The rest of the paper is organized as follows. In Section2, the model under consideration is described in detail. In Section 3, the behavior of the system under study is described by the level dependent multidimensional continuous-time Markov chain and the generator of this Markov chain is written down. In Section 4, the ergodicity condition of this Markov chain is derived and the stationary distribution of the system states is calculated. The expressions for key performance measures of the system are presented in Section 5. The numerical results showing reasonability of restriction of access of the secondary customers are given in Section 6. The importance of account of the correlation in the arrival process is clarified. Finally, Section 7 concludes the paper.


## 2. Mathematical Model

We consider the queueing system havingN identical servers without a waiting space (buffer). Arrival of two types of customers is defined by the MMAP—marked Markovian arrival process. This process is defined by the irreducible continuous-time Markov chain νt, t≥0, having a finite state space {0,…,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}.The MMAP is completely characterized by the square matricesD0, D1(r),  r=1,2, defined as follows: (D1(r))ν,ν′=λνpν,ν′(r),ν,ν′=0,W¯, r=1,2,(D0)ν,ν=-λν,ν=0,W¯, (D0)ν,ν′=λνpν,ν′(0), and ν,ν′=0,W¯, ν≠ν′.The matrixD(1)=D0+D1(1)+D1(2) is the generator of the Markov chain νt, t≥0. The average intensity of customers arrival (fundamental rate) λ is defined by the formula λ=θ(D1(1)+D1(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=θD1(r)e,  r=1,2.The squared coefficient of variationcvar of intervals between successive arrivals is defined by cvar=2λθ(-D0)-1e-1. The coefficient of correlation ccor of two successive intervals between arrivals is defined by ccor=(λθ(-D0)-1(D(1)-D0)(-D0)-1e-1)/cvar.Methods of the estimation ofMMAP parameters using a finite set of observed data, such as a set of customer arrival times recorded at a real world system, are presented, for example, in the paper [11].The service time distribution of type-r customers is exponentially distributed with the rate μr,  r=1,2.We assume that type-1 customers have preemptive priority over type-2 customers. Type-1 customer is always accepted to the system except the situation when, during its arrival moment, all servers are occupied by type-1 customers. In this situation, type-1 customer leaves the system without service (is lost). If all servers are occupied, but at least one of them provides service to type-2 customer during type-1 customer arrival epoch, service of one type-2 customer is terminated and type-1 customer occupies the corresponding server.Admission to the system of type-2 customers is restricted via the threshold mechanism. Some preassigned thresholdM,  0<M≤N, is fixed. The incoming secondary customer is accepted for service in the system only if the number of busy servers during its arrival moment is less than M. This is equivalent to reservation of N-M servers exclusively for service of type-1 customers. The case M=N corresponds to the system without reservation (without restriction of access of type-2 customers). If type-2 customer is admitted to the system, it occupies an arbitrary free server and starts service. If type-2 customer does not get permission to enter the system, with probability 1-q, 0≤q≤1, it leaves the system permanently (is lost). With the complementary probability, type-2 customer decides to retry to get access later. We say that this customer goes to a virtual place called orbit. A customer in orbit repeats the attempts to get access, independently of other customers from orbit, after a time interval having an exponential distribution with the parameter α, α>0. An attempt will be successful if the number of busy servers during the moment of this attempt is less than M. If the attempt is successful, the customer immediately occupies a free server and starts processing. If the attempt is not successful; with probability 1-q the customer leaves the system permanently. With the complementary probability, type-2 customer returns into orbit.Service of any type-2 customer may be terminated by the arrival of type-1 customer. In this situation, type-2 customer leaves the system with probability1-p, 0≤p≤1, or moves into orbit. The customers staying in orbit may be impatient and leave the system after a random amount of time having an exponential distribution with the parameter γ, γ>0. If the customers are patient, we set γ=0.As it was already noted above, the described queueing system is suitable, for example, for modeling, performance evaluation, capacity planning, and optimizing cognitive radio systems. Type-1 customers are interpreted as requests generated by the primary users, while type-2 customers are interpreted as requests generated by the secondary users. The imposed restriction of access of type-2 customers may not look very reasonable because type-1 customers have preemptive priority anyway. But, as it was shown in [6] and will be shown for more complicated models in our paper, under the suitable choice of the threshold, in some situations the restriction may decrease the probability of loss and forced termination of service of type-2 customers and increase the throughput of the system.In the rest of this paper, we will analyze stationary distribution of the system states and performance measures of the system under various fixed values of the thresholdM and solve optimization problem.We assume that the quality of operation of the system is evaluated by cost criterion:(1)J(M)=aλout(2)-λ2(c1P(ent-loss)+c2P(ent-to-orbit)+c3P(termination-loss)+c4P(termination-to-orbit)+c5P(loss-from-orbit)),
where λout(2) is the intensity of the flow of type-2 customers that receive successful service in the system, a is the profit, which earns the system by successful service of each type-2 customer, P(ent-loss) is the loss probability of type-2 customer at the entrance to the system due to the imposed restriction on access, P(ent-to-orbit) is the probability that, due to the restriction, type-2 customer goes into orbit, P(termination-loss) is the probability that service of type-2 customer is terminated and it is lost, P(termination-to-orbit) is the probability that service of type-2 customer is terminated and it moves into orbit, P(loss-from-orbit) is the loss probability of a customer from orbit, and cl,  l=1,5¯, are the charges which should be paid for the corresponding losses.It is necessary to find the valueM* of the threshold M which maximizes cost criterion (1). To this end, we have to have an opportunity to compute the values of all performance measures of the system, which appear at the right-hand side of (1), for any fixed value of the threshold M. In the next two sections we assume that the threshold M, 0<M≤N, is fixed.


## 3. Process of the System States

Let(i)
it,  it≥0, be the number of customers in orbit,(ii)
nt, nt=0,N¯, the number of busy servers,(iii)
lt, lt=0,min⁡⁡{nt,M}¯, the number of type-2 customers in service,(iv)
νt, νt=0,W¯, the state of underlying process of the MMAP during the moment t, t≥0.It is easy to see that the four-dimensional process(2)ξt={it,nt,lt,νt},t≥0,
is an irreducible continuous-time multidimensional Markov chain.Let us enumerate the states of the chainξt in lexicographic order of the components (i,n,l,ν). The set of the states having value (i,n) of two first components will be called as a macrostate (i,n).LetQ be the generator of the Markov chain ξt,  t≥0, consisting of the blocks Qi,j, which, in turn, consist of the matrices (Qi,j)n,n′ of the intensities of the transitions of the chain ξt from the macrostate (i,n) to the macrostate (j,n′), n,n′=0,min⁡⁡{i,N}¯. The diagonal entries of the matrices Qi,i are negative. The modulus of the diagonal entry defines intensity of departure from the corresponding state of the Markov chain.To write down the expression for the generatorQ, we need some notation.Let(i)
I be the identity matrix, and let O be a zero matrix. If the dimension of a matrix is not clear from context, it is indicated by the suffix. For example, IW¯ is an identity matrix of size W¯=W+1;(ii)
⊗ indicate the Kronecker product of matrices; see [12];(iii)
Cl=diag⁡{0,1,…,l}, C¯l=diag⁡{l,l-1,…,0}, l=0,M¯,C~l=diag⁡{l,l-1,…,l-M+1,l-M},  l=M,N¯;(iv)
diag⁡{A1,…,Al} a block-diagonal matrix with the diagonal blocks A1,…,Al;(v)
El+, E^l+, l=0,M-1¯, the matrices of size (l+1)×(l+2), defined as
(3)El+=(010⋯00001⋯00⋮⋮⋮⋱⋮⋮000⋯01);E^l+=(10⋯0001⋯00⋮⋮⋱⋮⋮00⋯10);(vi)
El-, E^l-, l=1,M¯, the matrices of size (l+1)×l, defined as
(4)El-=(10⋯001⋯0⋮⋮⋱⋮00⋯100⋯0),E^l-=(000⋯0100⋯0010⋯0⋮⋮⋮⋱⋮000⋯1);(vii)
I~ the diagonal matrix of size (M+1)(N+1-M/2) with the diagonal entries defined as follows: {0,…,0︸(M+1)M/2,1,…,1};(viii)
E-,I^ the square matrices of size M+1 defined by formulas:
(5)E-=(000⋯00100⋯00010⋯00⋮⋮⋮⋱⋮⋮000⋯10),I^=(10⋯000⋯0⋮⋮⋱⋮00⋯0).Lemma 1.
GeneratorQ of the Markov chain ξt has the following block-tridiagonal structure:
(6)Q=(Q0,0Q0,1OO⋯Q1,0Q1,1Q1,2O⋯OQ2,1Q2,2Q2,3⋯⋮⋮⋮⋮⋱),
where nonzero blocks Qi,j, i,j≥0, are defined as follows:
(7)Qi,i=(Ai(0)Bi(0)O⋯OOF(1)Ai(1)Bi(1)⋯OO⋮⋮⋱⋱⋮⋮OOO⋱Ai(N-1)Bi(N-1)OOO⋯F(N)Ai(N))+(1-q)I~(M+1)(N-M/2+1)⊗D2+I(M+1)(N-M/2+1)⊗D0,i≥0,Qi,i+1=Q+=diag⁡{H(0),…,H(N)},i≥0,Qi,i-1=(Li(0)B~i(0)O⋯OOOLi(1)B~i(1)⋯OOOOLi(2)⋯OO⋮⋮⋱⋱⋮⋮OOO⋱Li(N-1)B~i(N-1)OOO⋯OLi(N)),hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhi≥1,
where
(8)Ai(n)={-(μ2Cn+μ1C¯n+i(α+γ)In+1)⊗IW¯,n<M,i≥0,-(μ2CM+μ1C~n+i((1-q)α+γ)IM+1)⊗IW¯,M≤n<N,i≥0,-(μ2CM+μ1C~n+i((1-q)α+γ)IM+1)⊗IW¯+(1-p)E-⊗D1+I^⊗D1,n=N,i≥0;B(n)={En+⊗D2+E^n+⊗D1,n<M,IM+1⊗D1,M≤n<N;F(n)={(μ2CnE^n-+μ1C-nEn-)⊗IW¯,n≤M,(μ2CME-+μ1C~n)⊗IW¯,M<n≤N;H(n)={O,n<M,qIM+1⊗D2,M≤n<N,pE-⊗D1+qIM+1⊗D2,n=N;B~i(n)={iαEn+⊗IW¯,n<M,i≥0,O,n≥M,i≥0;Li(n)={iγIn+1⊗IW¯,n<M,i(γ+(1-q)α)IM+1⊗IW¯,M≤n≤N.Proof of the lemma is implemented by careful analysis of the intensities of the transitions of the Markov chainξt during an interval of time having an infinitesimal length and is omitted here.Remark 2.
It can be verified that the following limits exist:(9)Y0=lim⁡i→∞Ri-1Qi,i-1,Y1=lim⁡i→∞Ri-1Qi,i+I,Y2=lim⁡i→∞Ri-1Qi,i+1,
where the matrix Ri is a diagonal matrix with diagonal entries defined as the moduli of the corresponding diagonal entries of the matrix Qi,i, i≥0.It is easy to check that here the matrixRi is the block-diagonal matrix with the diagonal blocks Ti(n), n∈{0,…,N}, i≥0, defined as follows:
(10)Ti(n)={-Ai(n)+In+1⊗Λ,n=0,M-1¯,-Ai(n)-(1-q)IM+1⊗Σ2+IM+1⊗Λ,n=M,N-1¯,(μ2CM+μ1C~N+i((1-q)α+γ))⊗IW¯-I^⊗Σ1-(1-q)IM+1⊗Σ2+IM+1⊗Λ,n=N,
where Σ1,  Σ2, and Λ are the diagonal matrices, the diagonal entries of which are defined as the corresponding diagonal entries of the matrices D1, D2, and -D0, respectively.Existence of the limitsYk,  k=0,1,2, implies that the Markov chain ξt, t≥0, belongs to the class of continuous-time asymptotically quasi-Toeplitz Markov chains (AQTMC); see [13]. So, results from [13] can be used to derive the ergodicity condition for the Markov chain ξt and compute its stationary distribution.


## 4. Ergodicity Condition and Stationary Distribution of the Markov Chain

Theorem 3.
Ifq≠1 or γ≠0, then the Markov chain ξt is ergodic for any set of parameters of the queueing system under study.
Ifq=1 and γ=0, then the Markov chain ξt is ergodic if the following condition is fulfilled:
(11)xM(μ2CM+μ1C¯M)e>λ2+pλ1xNe^,
where e^ is the column vector of size M+1 having first zero component and other components equal to 1 and the vector x=(xM,…,xN), xn=(x(n,0),…,x(n,M)), n=M,N¯, is the unique solution to the system
(12)xA=0,xe=1.
Here the matrix A is defined by formulas
(13)A=(A~(M)λ1IM+1O⋯OOOF~(M+1)A~(M+1)λ1IM+1⋯OOO⋮⋮⋮⋱⋮⋮⋮OOO⋯F~(N-1)A~(N-1)λ1IM+1OOO⋯OF~(N)A~(N)),(14)A~(n)={-μ1C~M(I-EM-EM-1+)-λ1IM+1,n=M<N,-μ1C~M(I-EM-EM-1+)-λ1(I-E--I^),n=M=N,-μ2CM-μ1C~n-λ1IM+1,M<n<N,-μ2CM-μ1C~N-λ1(I-E--I^),n=N>M,
and F~(n)=(μ2CME-+μ1C~n), n=M+1,N¯.Proof.
It follows from [13], that sufficient condition for ergodicity of the AQTMC ξt, t≥0, is the fulfillment of the inequality
(15)yY0e>yY2e,
where the row vector y is the unique solution to the system of linear algebraic equations:
(16)y(Y0+Y1+Y2)=y,ye=1.
Let us separately consider two cases. Let firstq≠1 or γ≠0.
In this case, it can be verified that the matricesY0, Y1, and Y2 are defined by expressions(17)Y0=(γγ+αIW¯αγ+αE0+⊗IW¯⋯OOO⋯O⋮⋮⋱⋮⋮⋮⋱⋮OO⋯γγ+αIMW¯αγ+αEM+⊗IW¯O⋯OOO⋯OI(M+1)W¯O⋯O⋮⋮⋱⋮⋮⋮⋱⋮OO⋯OOO⋯OOO⋯OOO⋯I(M+1)W¯),Y1=O,Y2=O.
It is evident that in this case inequality (15) and system (16) can be rewritten as yY0e>0, yY0=y,  ye=1. So inequality (15) is equivalent to the inequality yY0e=ye=1>0 that trivially holds true for all values of the parameters of the system under study.
Let nowq=1 and γ=0, then the matrices Y0, Y1, and Y2 are defined by expressions(18)Y0=T-1(OE0+⊗IW¯O⋯O⋯O⋮⋮⋮⋱⋮⋱⋮OOO⋯EM-1+⊗IW¯⋯OOOO⋯O⋯O⋮⋮⋮⋱⋮⋱⋮OOO⋯O⋯O);Y1=I~⊗IW¯+T-1(O⋯OOO⋯OO⋮⋱⋮⋮⋮⋱⋮⋮O⋯OOO⋯OOO⋯F(M)A(M)B(M)⋯OOO⋯OF(M+1)A(M+1)⋯OO⋮⋱⋮⋮⋮⋱⋮⋮O⋯OOO⋯A(N-1)B(N-1)O⋯OOO⋯F(N)A(N)),Y2=T-1diag⁡{OW¯,O2W¯,…,OMW¯,H(M),H(M+1),…,H(N)},where
(19)T=diag⁡{IW¯,I2W¯,…,IMW¯,T(M),T(M+1),…,T(N)},T(n)={(μ2CM+μ1C~n)⊗IW¯+IM+1⊗Λ,M≤n<N,(μ2CM+μ1C~N)⊗IW¯-I^⊗Σ1+IM+1⊗Λ,n=N,A(n)={-(μ2CM+μ1C~n)⊗IW¯+IM+1⊗D0,M≤n<N,-(μ2CM+μ1C~n)⊗IW¯+I^⊗D1+(1-p)E-⊗D1+IM+1⊗D0,n=N.
MatrixY=Y0+Y1+Y2 has a form
(20)Y=I~⊗IW¯+T-1G,
where the matrix G has a structure
(21)G=(G11G12G21G22),where(22)G11=(OE0+⊗IW¯O⋯O⋮⋮⋮⋱⋮OOO⋯EM-2+⊗IW¯OOO⋯O),G12=(OO⋯O⋮⋮⋱⋮EM-1+⊗IW¯O⋯O),G21=(O⋯OF(M)O⋯OO⋮⋱⋮⋮O⋯OO),G22=(A(M)+H(M)B(M)O⋯OOF(M+1)A(M+1)+H(M+1)B(M+1)⋯OO⋮⋮⋮⋱⋮⋮OOO⋯A(N-1)+H(N-1)B(N-1)OOO⋯F(N)A(N)+H(N)).
Let us represent the solutiony of system (16) as y=(y0,y1,…,yN). Taking into account the structure of the matrix G, it is easy to see that y0=y1=…=yM-2=0. So, the vector y is defined as
(23)y=(0,…,0,yM-1,z),
where z=(yM,…,yN).
Having in mind this form of the vectory, system (16) can be rewritten in the form
(24)yM-1=zT~-1F,zZ=0,ze+yM-1e=1,
where
(25)F=(F(M),O(M+1)W¯,…,O(M+1)W¯︸N-M)T,Z=T~-1×(G22+I^⊗F(M)EM-1+)T~=diag⁡{T(M),…,T(N)}.
Let us analyze equation zZ=0 taking into account more explicit forms of the matrix Z:(26)0=zZ=zT~-1×[(-μ1C~M(I-E~)O⋯OOF~(M+1)-μ2CM-μ1C~M+1⋯OO⋮⋮⋱⋮⋮OO⋯-μ2CM-μ1C~N-1OOO⋯F~(N)-μ2CM-μ1C~N)⊗IW¯+(IM+1⊗(D0+D2)IM+1⊗D1⋯OOOI⊗(D0+D2)⋯OO⋮⋮⋱⋮⋮OO⋯I⊗(D0+D2)I⊗D1OO⋯OI⊗(D0+D2)+(I^+E-)⊗D1)],where E~=EM-EM-1+.
By postmultiplying (26) by e(N-M+1)(M+1)⊗IW¯ we obtain the following equation:
(27)zT~-1(e(N-M+1)(M+1)⊗(D0+D1+D2))=0.
It follows from (27) that the vector zT~-1 can be represented in the form
(28)zT~-1=ϕ⊗θ,
where ϕ is some row vector of size (N-M+1)(M+1) and θ is the invariant probability vector of the underlying Markov chain of the MMAP.
By substituting the vectorzT~-1 in form (28) into (26), postmultiplying this equation by I(N-M+1)(M+1)⊗eW¯ and taking into account relations θD1e=λ1,  θ(D0+D2)e=θ(-D1)e=-λ1, and θe=1, we conclude that the unknown vector ϕ is the solution of the system
(29)ϕA=0,
where the matrix A is given in the statement of Theorem 3 under proof.
It can be verified that the matrixA is the generator of two-dimensional Markov chain {nt,lt} defining the number of busy servers nt, nt=M,N¯, and the number of servers occupied by type-2 customers lt, lt=0,M¯, in the situation when the system is overloaded; that is, the number of customers in orbit is huge. It follows from (29) that the vector ϕ defines, up to the normalizing factor c, the joint stationary distribution of the Markov chain {nt,lt}. So, the vector ϕ can be represented in the form
(30)ϕ=cx,
where the vector x is given in the statement of Theorem 3.
Thus, the vectorzT~-1 is defined by
(31)zT~-1=cx⊗θ
and, using the so called mixed product rule for Kronecker product of matrices, see [12]; the left-hand side of inequality (15) can be rewritten as
(32)yY0e=yM-1(EM+⊗IW¯)e=zT~-1F(EM+⊗IW¯)e=cx⊗θFe=c(xM⊗θ)((μ2CME^M-+μ1C¯MEM-)⊗IW¯)e=c(xM(μ2CME^M-+μ1C¯MEM-))⊗(θIW¯)e=c(xM(μ2CME^M-+μ1C¯MEM-))e⊗1=cxM(μ2CME^M-+μ1C¯MEM-)e=cxM(μ2CM+μ1C¯M)e.
The right-hand side of inequality (15) can be rewritten as follows:
(33)yY2e=zT~-1diag⁡{HM,HM+1,…,HN}=c(∑n=MN-1(xn⊗θ)(IM+1⊗D2)e+(xN⊗θ)(pE-⊗D1+IM+1⊗D2)e∑n=MN-1(xn⊗θ)(IM+1⊗D2)e)=c(λ2∑n=MNxne+pλ1xNe^)=c(λ2+pλ1xNe^).
Then, inequality (15) can be rewritten as follows:
(34)xM(μ2CM+μ1C¯M)e>λ2+pλ1xNe^.
Theorem is proved.Remark 4.
Condition (11) is intuitively clear. In the overloaded system, a customer may leave orbit only in the situation when the number of busy servers becomes less than M. The components x(M,l), l=0,M¯, of the vector xM define the probability that, at an arbitrary time, M servers are busy and l of them provide service to type-2 customers. So, the left-hand side of inequality (11) defines intensity of the service completions when M servers are busy. This intensity coincides with the intensity of customers’ departure from orbit. The right-hand side of inequality (11) defines the intensity of type-2 customers’ arrival into orbit. It is equal to the sum of the intensity λ2 of customers’ arrival from outside and the intensity pλ1xNe^ of customers’ arrival due to force termination.Thus, ergodicity condition (11) requires that, in the situation when the system is overloaded, the intensity of customers’ arrival into orbit is less than the intensity of customers’ departure from orbit.Further, we assume that condition (11) is fulfilled. Then the following limits (stationary probabilities) exist:
(35)π(i,n,l,ν)=lim⁡t→∞P{it=i,nt=n,lt=l,νt=ν},i≥0,n=0,N¯,l=0,min⁡⁡{n,M}¯,ν=0,W¯.Let us form the row vectors of the stationary probabilitiesπi as follows:
(36)π(i,n,l)=(π(i,n,l,0),π(i,n,l,1),…,π(i,n,l,W)),hhhhhhhhhhhhhhhhhhhhhhhhhhhl=0,min⁡⁡{n,M}¯,π(i,n)=(π(i,n,0),π(i,n,1),…,π(i,n,min⁡⁡{n,M})),hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhn=0,N¯,πi=(π(i,0),π(i,1),…,π(i,N)),i≥0.It is well known that the probability vectorsπi,i≥0, satisfy the following system of linear algebraic equations:
(37)(π0,π1,…)Q=0,(π0,π1,…)e=1,
where Q is the generator of the Markov chain ξt, t≥0.Note that in the caseq=0, p=0 we get the model where retrials are not taken into account. In this case, the generator Q reduces to the finite block Q0,0 and system (37) is finite. The probability vectors can be computed by the direct solution of system (37) on computer or by means of the numerically stable algorithms developed in [14, 15]. In general case, system (37) is infinite and cannot be directly solved on computer. It can be solved by means of the numerically stable algorithm developed in [13]. The algorithm presented in [13] is oriented to more general forms of the generator Q (blocks above the off-diagonal blocks can be not equal to zero). Variant of the algorithm exactly oriented to a block-tridiagonal form of the generator Q can be found, for example, in [16].


## 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 distribution of the number of the customers in orbit is(38)lim⁡t→∞P{it=i}=πie,i≥0.The average number of customers in orbit is(39)Lorbit=∑i=1∞iπie‍.The average number of customers in the system is(40)L=∑i=0∞∑n=0N(i+n)π(i,n)e‍‍.The average number of busy servers is(41)Nserver=∑i=0∞∑n=1Nnπ(i,n)e‍.The average number of busy servers providing service to type-1 customers is(42)Nserver(1)=∑i=0∞∑n=1N∑l=0min⁡⁡{n,M}(n-l)π(i,n,l)e‍‍.The average number of busy servers providing service to type-2 customers is(43)Nserver(2)=∑i=0∞∑n=1N∑l=1min⁡⁡{n,M}lπ(i,n,l)e=Nserver-Nserver(1).The intensity of output of type-1 customers is(44)λout(1)=μ1Nserver(1).The intensity of output of type-2 customers is(45)λout(2)=μ2Nserver(2).The intensity of output of customers from the system is(46)λout=λout(1)+λout(2).The blocking (loss) probability of type-1 customers is(47)P1(loss)=λ1-1∑i=0∞π(i,N,0)D1e‍=1-λout(1)λ1.The blocking (loss) probability of type-2 customers is(48)P2(loss)=1-λout(2)λ2.The blocking (loss) probability of an arbitrary customer is(49)P(loss)=1-λoutλ.The probability of type-2 customer loss due to the imposed restriction (type-2 customer is not granted access to the system if the number of busy servers is greater or equal toM) is
(50)P(ent-loss)=(1-q)λ2-1∑i=0∞∑n=MNπ(i,n)(IM+1⊗D2)e.The probability that type-2 customer will go into orbit due to the imposed restriction is(51)P(ent-to-orbit)=qλ2-1∑i=0∞∑n=MNπ(i,n)(IM+1⊗D2)e‍.The probability that an arbitrary type-2 customer will be forced to terminate service and go into orbit is(52)P(termination-to-orbit)=pλ2-1∑i=0∞∑l=1Mπ(i,N,l)D1e.The probability that an arbitrary type-2 customer will be forced to terminate service and will be lost is(53)P(termination-loss)=(1-p)λ2-1∑i=0∞∑l=1Mπ(i,N,l)⊗D1e.The probability of an arbitrary type-2 customer loss from orbit is(54)P(loss-from-orbit)=P2(loss)-P(ent-loss)-P(termination-loss).The probability that an arbitrary customer from orbit will make an attempt to receive service when the number of busy servers is greater or equal toM and return to orbit is
(55)P(return-to-orbit)=qα~-1∑i=1∞∑n=MNiαπ(i,n)e,
where α~=αLorbit.The probability that an arbitrary customer from orbit will make an attempt to receive service when the number of busy servers is greater or equal toM and leave the system without service is
(56)P1(loss-from-orbit)=(1-q)α~-1∑i=1∞∑n=MNiαπ(i,n)e.


## 6. Optimization Problem and Numerical Examples

As it was mentioned in the description of the mathematical model, our goal is to find the valueM* of the threshold M, 1≤M≤N, which provides the maximal value of cost criterion (1). Analytical results presented in the previous sections allow us to compute the performance measures involved in cost criterion (1) under any fixed value of M, 1≤M≤N. So, the problem of finding the optimal value of M in the finite set 1≤M≤N can be solved.As one of the advantages of our model comparing to other models existing in the literature, we mentioned in Section1 that we use the MMAP instead of the stationary Poisson processes of customers. This allows taking into account possible correlation in the arrival process. To illustrate the importance of account of impact of correlation, let us consider three different arrival processes having the same intensity of arrival of each type of customers, but different coefficients of correlation of successive interarrival times in the arrival process.For this purpose, let us introduce three MMAPs defined by the matricesD0,  D1(1), and D1(2). All these MMAPs have the same average total arrival rate λ=4, the average intensity of priority customers λ1=4/3, and the average intensity of nonpriority customers λ2=8/3, but different coefficients of correlation. MMAPa denotes the MMAP arrival process with coefficient of correlation ccor=a.The first process coded asMMAP0 is defined by the matrices D0=-4, D1(1)=4/3, and D1(2)=8/3. It has the coefficient of correlation ccor=0 and the coefficient of variation cvar=1. In this case, the arrival processes of priority and nonpriority customers are defined as the stationary Poisson processes.The second processMMAP0.2 is defined by the matrices
(57)D0=(-5.40800-0.1755),D1(1)=(1.79060.0120.032570.02593),D1(2)=(3.58140.0240.065150.05185)
and has the coefficient of correlation ccor=0.2, and the coefficient of variation cvar=12.35.The third processMMAP0.4 is defined by the matrices
(58)D0=(-13.7750.0810.004-0.444),D1(1)=(4.5440.0210.0160.1305),D1(2)=(9.0880.0410.03250.261).
It has the coefficient of correlation ccor=0.4, and the coefficient of variation cvar=12.35.The rest of the parameters of the queueing model are assumed to be as follows:(i)
the number of servers isN=30;(ii)
the service intensity of type-1 customers isμ1=0.08;(iii)
the service intensity of type-2 customers isμ2=0.2;(iv)
the intensity of impatience of customers from orbit isγ=0.005;(v)
the intensity of retrials isα=0.15;(vi)
the probabilitiesq and p are equal to 0.9 and 0.1, correspondingly.Let us vary the thresholdM in the interval [1,N], compute, and analyze dynamics of key performance measures of the system.First of all, it is worth to note the evident fact that, because type-1 customers have preemptive priority, the probabilityP1(loss) of type-1 customer loss and the average number Nserver(1) of busy servers providing service to type-1 customers do not change when the threshold M varies. The values of these performance measures for arrival flows with the same mean arrival rate but different coefficient of correlation are given in Table 1.Table 1
ProbabilityP1(loss) of type-1 customer loss and the average number Nserver(1) of busy servers providing service to type-1 customers for various correlations in the arrival process.
c
cor
P
1
(
loss
)
N
server
(
1
)
0
0.000986
16.65
0.2
0.011974
16.4337
0.4
0.205498
13.2389It is evidently seen from this table that the correlation in the arrival process may drastically change the performance measures of the queueing model. If an arrival process in some real life system is correlated while one will try to model the arrival process by the stationary Poisson process, he or she will get too optimistic forecasting of the system performance. In our example, for the stationary Poisson process the predicted value of the probabilityP1(loss) of type-1 customer loss is less than 10-3. But if the correlation in the real arrival process is equal to 0.2, the probability P1(loss) is more than 10 times higher and, if correlation in the arrival process is equal to 0.4, the probability P1(loss) is more than 200 times higher.Note that this result does not sound very surprising because service of type-1 customers may be described by Erlang loss modelMAP/M/N/N and analogous effect for this model was previously reported in [14]. Intuitive explanation of this effect is the following. Arrivals of customers in the stationary Poisson process are more or less uniformly distributed in time and the servers of corresponding queueing system are loaded more or less uniformly. Positive correlation in the arrival process implies that customers arrive rarely during some time intervals, while a lot of customers arrive in other intervals. It is said that such a process is “bursty.” This nonuniform arrival of customers implies that during some time intervals the system starves, many servers are idle, while during some other intervals a lot of customers is lost due to the system overflow.Concerning the behavior of the majority of characteristics of processing type-2 customers when the thresholdM varies, it is quite predictable. When the number M increases, the probabilities P(ent-loss) and P(ent-to-orbit) decrease, while the probabilities P(termination-loss) and P(termination-to-orbit) increase. Because the probability P2(loss) of type-2 customer loss is the sum of the probabilities P(ent-loss), P(termination-loss), and P(loss-from-orbit), some of them having an opposite dynamics, behavior of the probability P2(loss) is more complicated. This probability decreases with increase of M until the threshold reaches some critical value. Then the probability P2(loss) starts sharply increasing. Correspondingly, the intensity λout(2) of the flow of type-2 customers that received successful service in the system, which is the most important performance measure of the system, has maximum at some point inside the region [1,N].The cost criterion (1), which is the weighted sum of λout(2) and loss probabilities, also reaches the maximum at some point. To demonstrate this, let us fix the following values of the cost coefficients a=20,  c1=3,  c2=1,  c3=20, c4=10, and c5=3. Dynamics of cost criterion (1) for three MMAPs, defined above, having the same mean arrival rate but different correlation is presented in Figure 1.Figure 1
Dynamics of the cost criterionJ(M) for three MMAPs arrival processes with different coefficients of correlation.In Table2, we present the optimal values M* of the threshold and cost criterion J(M*), the value of cost criterion for the system without admission control J(N), the absolute value of the profit gained by control J(M*)-J(N), and the relative value of the gain (J(M*)-J(N))/J(N)×100% for various correlations in the arrival process.Table 2
Information about the optimal values of the threshold, cost criterion, and profit in comparison to the system without admission control for various correlation in the arrival process.
c
cor
M
*
J
(
M
*
)
J
(
N
)
J
(
M
*
)
-
J
(
N
)
J
(
M
*
)
-
J
(
N
)
J
(
N
)
×
100
%
0
29
38.5723
35.1728
3.3995
9.66
0.2
28
27.9364
19.9398
7.9986
40.10
0.4
27
20.8424
12.2544
8.5880
70.08It follows from this table that higher correlation in arrival process implies necessity of more strict restriction of access of secondary customers and higher profit obtained via the optimal control by admission of secondary customers.


## 7. Conclusion

We analyzed the multiserver queueing model of theMMAP/M2/N/N type suitable for modeling systems of cognitive radio. Primary customers have preemptive priority. Access of the secondary customers is restricted via threshold mechanism aiming to provide maximally effective processing of secondary customers. The secondary customers have the option to retry for service later in the case of access deny. Under the fixed value of the threshold, behavior of the queueing system is described by the level dependent multidimensional Markov chain. Sufficient condition for ergodicity of this chain in simple analytically tractable form is derived. The expressions for the main performance measures of the system are derived. Optimization problem is considered. Provided results of the numerical experiments illustrate high effectiveness of the used strategy of the restriction of access of the secondary customers and necessity of careful account correlation in arrival process.



---

*Source: 178108-2014-05-07.xml*