Analysis of a queue with two priority classes and feedback controls

The preemptive queue with two priority classes has been treated in earlier works [10, 11, 13] because it can be used for the performance evaluation of practical systems. Customers of two classes (high and low priority) arrive into the system. A server has a service capacity of multiple identical service units. Each high-priority customer requires a single service unit. The system works under the preemptive discipline, i.e. an admitted high-priority customer immediately gets service upon his arrival either by getting an idle service unit or by occupying service unit being used by low-priority customers. High-priority customers are served according to the first in first out (FIFO) and low-priority customers are served according to the processor sharing (PS) principle. Furthermore, the service capacity for low-priority customers depends on the number of high-priority customers in the system.

To take into account practical aspects, buffers of finite size for both two classes of customers are assumed in this paper. Furthermore, a proposed queue includes a congestion control mechanism. Once the number of low-priority customers in the system reaches the first control threshold, the arrival rate of low-priority customers is reduced to a guarantee arrival rate. If the number of low-priority customers is above the second control threshold, each arriving batch of low-priority customers will be discarded with a certain probability. Therefore, the proposed queue can be used to model Differentiated Service Architecture [14] in IP networks.

We show that this queue can be analyzed within the framework of Quasi Birth and Death (QBD) processes [4, 5, 7, 8]. Closed-form expressions are given for the mean number of customers of each class, the batch and the customer loss probability of each class and the mean system time of customers.

The rest of the paper is organized as follows. In Sect. 2, a queue with two priority classes is discussed in details. Finally, numerical results illustrating the operation of the system are presented in Sect. 3. The paper ends with some conclusions in Sect. 4.

The system consists of a server and two finite queues. The service capacity of the server is assumed to be composed of \(N\) service units. There are two categories of customers: high priority (HP) and low priority (LP).

We assume that the interarrival times of batches of HP customers follow an exponential distributions with parameter \(\lambda _{\mathrm{HP}}\). The size of the buffer for storing HP customers is \(K_{\mathrm{HP}}\). The batch size is upper-bounded by \(H\) (note that \(K_{\mathrm{HP}} \ge H\)). A batch of \(b,\,1\le b \le H\), HP customers occurs with probability \(h_{b}\), where \(\sum _{b=1}^{H}h_{b}=1\). Each HP customer requires a single service unit. The service time of a HP customer has an exponential distribution with rate \(\mu _{\mathrm{HP}}\). High-priority customers are served according to the FIFO principle.

Let \(I(t)\) denote the number of high-priority customers in the system at time \(t,\,0 \le I(t) \le {\mathcal {N}}=N+K_{\mathrm{HP}}\). Upon the arrival of a batch of \(b\) HP customers at time \(t\),Two admission rules can be considered for the placement of customers into the buffer: whole batch acceptance (WBA) or partially batch acceptance (PBA). WBA means that the whole batch will be dropped if the system is not able to accept the whole batch. Under PBA only the part of batch is dropped, for which available room cannot be assured.

Batches of low-priority customers arrive according to a Poisson process. The batch size is upper-bounded by \(L\). A batch of \(b\), \(1\le b \le L\), LP customers occurs with probability \(l_{b}\), where \(\sum _{b=1}^{L}l_{b}=1\). The service discipline of LP customers is processor sharing, a low-priority batch will get service immediately if there is service capacity not used by HP customers. Otherwise the batch is put into a buffer of size \(K_{\mathrm{LP}}\). Due to the preemptive nature of the system, low-priority customers under service may be pushed back into waiting room by high-priority customers. It is highly recommended that once a customer has been accepted into system, it will not be lost because of the aforementioned push-back mechanism. Therefore, at any time we require that no more than \(K_{\mathrm{LP}}\) of low-priority customers (either being in service or waiting in queue) are in the system. Let \(J(t)\) be the number of low-priority customers in the system, \(0\le J(t) \le K_{\mathrm{LP}}\). If there are \(i\) high-priority and \(j\) low-priority customers in the system (\(0 \le i \le N+K_{\mathrm{HP}},\,j \ge 1\)), then each of the low-priority customers receives service at rate \(\frac{\max (N-i,0)}{j}\mu _{\mathrm{LP}}\).

It is assumed that batches of low-priority customers arrive at rate \(\lambda _{LP,j}\) for level \(j\,(0\le j < m_{1}\)). When the number of low-priority customers in the system reaches the level \(m_{1}\), its (batch) arrival rate is forced to reduce from \(\lambda _{L,j}\) to the guarantee value \(\lambda _{\mathrm{LP}}\). From the context of congestion control, it is natural to assume \(\lambda _{\mathrm{LP},0} \ge \lambda _{\mathrm{LP},1} \ge \cdots \ge \lambda _{\mathrm{LP}}\).

The second control level is set to \(j=K_{\mathrm{LP}}-m_2\). That means whenever the difference between the number of low-priority customers and the waiting room’s capacity drops below \(m_{2}\), each low-priority arrival batch will be discarded with the pre-defined probability \(p_{\mathrm{dropp}}\). The main parameters of the queue are summarized in Table 1.

The system is two-dimensional Markov process \((I(t),\) \(J(t))=(i,j)\) with the state space \(\{(i,j): 0 \le i \le K_{\mathrm{HP}}+N, \; 0 \le j \le K_{\mathrm{LP}}\}\). Let \(p_{i,j}\) denote the steady state probability of the state \((i,j)\) asWe introduce the following vectorsIn what follows, we provide an analysis for the WBA rule. Note that the analysis for the PBA rule can be performed in the same way. For the WBA rule, the generator matrix of this process will have the form shown in Fig. 1.

For \(0 \le j \le K_{\mathrm{LP}}\), we define the following matrix \(\mathcal {A}_{j}=A_j-D^{A_j}-C_{j}- \sum _{s=1}^{L}B_{j-s,s}\), where \(D^{A_j}\) is matrix whose diagonal elements are the sum of the elements in the corresponding row of \(A_j\).

The balance equations of the system are written asand the normalization equation iswhere \({\mathbf {e}}\) is the unit vector.

For \(M_1=m_1+ L \le j \le M_2=\min (K_L-1,K_L-m2)\), the Eq. (1) include only \(j\)-independent coefficient matrices and have a common formThe examples of these matrices are shown in Fig. 2.

In the literature so far, attention is mainly focused on the steady-state analysis of infinite QBD-M processes [1, 3, 9] performed by a direct approach with spectral expansion method proposed in [3] or an indirect approach with reblocking technique applied in [12].

To cope with the numerical problem, we apply the theory of generalized invariant subspace [2]. Recall that with the theory of generalized invariant subspace, we are able to compute matrices \(U = [\begin{array}{ll} U_1&U_2 \end{array}]\) and \(V=[\begin{array}{ll} V_1&V_2 \end{array}]\), which makes the following decomposition possiblewhere matrices \(E\) and \(G\) are constructed from the QBD-M process as followsmatrix \(D_i\) (\(i=0,1,\ldots , L+1\)) is the coefficient matrix of v \(_{j-L+i}\) in the balance equations.

Let \(m_{s}\) and \(m_{u}\) denote the number of singularities of matrix pencil \(\lambda E -G\), which lie inside and outside the open unit disk, respectively. Note that the singularities of the matrix pencil \(\lambda E-G\), i.e. the roots of \(det(\lambda E-G)=0\) are exactly the roots of the equation \(det(D(\lambda ))=0\), where \( D(\lambda )= D_{0}+D_{1}\lambda +\ldots +D_{L+1}{\lambda }^{L+1}\). As a consequence, we have \(m_{s} +m_{u}=m=(L+1)\times ({\mathcal {N}}+1)\). Matrices \(U_{1},V_1\) are of size \(m \times m_{u}\), matrices \(U_{2},V_{2}\) are of size \(m\times m_{s}\), matrices \(E_{11},G_{11}\) are of size \(m_u \times m_u\) and matrices \(E_{22},G_{22}\) are of size \(m_s \times m_s\), respectively.

Let define the following partition and matricesmatrices \(F_1\) and \(F_2\) are of size \(m_{u} \times m_{u}\) and \(m_{s}\times m_{s}\), respectively. Let define the groupingfor \(0 \le k \le K=M_2-M_1+1\) andThe vectors \({\mathbf {p}}_{k}\) and \({\mathbf {q}}_k\) (\(0\le k \le K\)) are of size \(m_u\) and \(m_s\), respectively. It can be easily checked thatBy post-multiplying the Eq. (9) by matrix \(V\) and combining with Eq. (4), we obtain two un-couple generalized difference equations for \({\mathbf {p}}_{k}\) and \({\mathbf {q}}_{k}\) This follows that the next two expression holdWe are now able to express the level probability vectors asandWith the Eqs. (13) and (14), the unknown probability vectors we have to compute now are \({\mathbf {v}}_{0},\ldots ,{\mathbf {v}}_{M_1-L-1},\,{\mathbf {p}}_{K},{\mathbf {q}}_{0}\) and \({\mathbf {v}}_{M_2+2},\,\ldots ,{\mathbf {v}}_\mathcal {K}\), i.e. there are \((M_1-L)+y+(\mathcal {K}-M_2-1)\,=M_1+\mathcal {K}-M_2\) unknown vectors, each of size \({\mathcal {N}}+1\). To get these unknown vectors, we have vector Eq. (1) for \(j=0,\ldots ,M_1-1\) (the first \(M_1\) equations) and for \(j=M_2+1,\ldots , \mathcal {K}\) (the last \(\mathcal {K}-M_2\) equations). However, only \(M_1+\mathcal {K}-M_2-1\) of these equations are linearly independent due to the fact that the generator matrix of the Markov process is singular. This means one equation must be replaced by the normalized Eq. (2). Using Eqs. (13) and (14), the equivalent form of (2) isWhat remains to be clarified is how to determine the values of \(m_u\) and \(m_s\). For this aim, we take a corresponding infinite QBD-M process, which possesses the same balance equations (3) with the same level-independent coefficient matrices \(\mathcal {A}\), \(B_i\) (\(1\le i\le L\)).

Using the interpretation of stability formulated in previous works (see [3, 6]), stability condition of the corresponding infinite QBD-M process is checked by evaluating the inequalitywhere v is a vector of size \({\mathcal {N}} +1\) and is the solution of the equationsIf the inequality (16) is fulfilled, then it is known from [3] that the \(det(D(\lambda ))=0\) equation has exactly \(L*({\mathcal {N}} +1)\) roots inside the unit disk. In this case, we have \(m_u=({\mathcal {N}}+1)\) and \(m_s=L*({\mathcal {N}}+1)\). Also from [3], the case in which the inequality does not hold implies that \(m_u=({\mathcal {N}}+1)+1\) and \(m_s=L*({\mathcal {N}}+1)-1\).

In what follows, unless otherwise stated, the parameter set \(N=10, \mu _{\mathrm{LP}}=1, \lambda _{\mathrm{LP}}=2,\mu _{\mathrm{HP}} = 2, \lambda _{\mathrm{HP}}=4, K_{\mathrm{LP}}=50, H=L=2\) is applied. The distribution of batch sizes is assumed to be uniform.

The impact of the dropping probability (\(p_{\mathrm{dropp}}\)) on performance measures related to the low-priority class is shown in Figs. 3 and 4 for \(m_1=3,K_{\mathrm{HP}}=10\). In Fig. 3, both the blocking and the overall loss probability are plotted as a function of the dropping probability. The first observation is that increasing the dropping probability of arriving batches increases slightly the overall and at the same time reduces significantly the blocking probability. The later performance measure is in connection with the mean queue length, which decreases with the dropping probability as shown in Fig. 4.

The second observation from the figures is that the smaller the control level \(K_{\mathrm{LP}}-m_{2}\) is chosen, the better performance is obtained from the aspect of the mean queue length and the blocking probability, at the same time, the worse the performance becomes from the aspect of overall loss probability. A trade-off between the increase of overall customer loss probability and the reduction of mean queue length (and through it, the mean system time) should be carefully considered when choosing an appropriate control level \(K_{\mathrm{LP}}-m_{2}\).

Figures 5 and 6 illustrate the effect of buffer size (\(K_{\mathrm{HP}}\)) for customers of high priority on the queueing performance. The system parameters are \(N=5,m_1=5,m_2=8,p_{\mathrm{dropp}}=0.01\). The maximum size of arriving batches is chosen in sequence to be \(2\), \(4\) and \(8\). Obviously, increasing the buffer size reduces the batch loss probability as well as customer loss probability as Fig. 5 shows. The decreasing rate is quite fast when the maximum batch size is small (corresponding to small offered traffic) and seems to slow down when the maximum batch size (so as the offered traffic) becomes greater. Note that if reducing the batch (customer) loss probability is performed by increasing the storage requirement then it also implies the increasing of mean queue length and through it the mean queueing delay, especially in the case of heavy traffic load. This situation is depicted in Fig. 6.

Now we discuss the influence of offered traffic on the queueing performance with respect to interaction between two classes. The system parameters are \(m_1=5,m_2=8,K_{\mathrm{HP}}=10,p_{\mathrm{dropp}}=0.01,\mu _{\mathrm{LP}}=1\). The offer traffic is increased by varying \(\lambda _{\mathrm{HP}}/\mu _{\mathrm{HP}}\) meanwhile \(r_{\mathrm{LP}}=\lambda _{\mathrm{LP}}/\mu _{\mathrm{LP}}\) is fixed. Figures 7 and 8 clearly indicate the impact of the preemptive principle. As high-priority customers have the right to occupy service capacity over low-priority customers, the offered traffic of high priority first forces more customers of low priority to disclaim their service capacity and return to waiting condition. Until a certain value of \(\lambda _{\mathrm{HP}}/\mu _{\mathrm{HP}}\), there is no customer of the high-priority class in the queue and no high-priority customer loss at all. Further the increase of the offered traffic of high-priority customers causes the occupancy of buffers and initiates lost events relating to both two classes. However, due to the preemptive service discipline, the mean number of low-priority customers in the queue, as well as the customer loss probability of the low-priority class are increasing at a greater rate than the corresponding ones for the high-priority class. It is also worth emphasizing that the offered load of the low-priority class (expressed by parameter \(r_L\)) does not have any effect on the performance of the high-priority class. That is why for different values of \(r_L\), the mean number and the loss probability of high-priority customers remains the same as plotted in Figs. 7 and 8.

In this paper, the steady-state analysis of a queue with two priority classes has been performed. To model some practical problems, additional extensions have been considered, such as finite capacity of buffers, batch arrival condition and level-dependent feedback control.

We have shown that the steady-state probabilities can be computed using the theory of generalized invariant subspace. Using the presented methodology, a performance trade-off can be achieved regarding the application of congestion control for networks.