Keywords

1 Introduction

Processor sharing technology is very popular in computer systems and telecommunications networks. It can be found a number of examples of real processor sharing systems and their mathematical models in the literature , see, e.g. the papers [1,2,3,4,5,6,7,8]. Most often, it is assumed that the processor can be used by an unlimited number of users, the input flow is stationary Poisson, and the service times are distributed exponentially. More general systems have been considered in the papers [9, 10] where it was assumed that customers arrive into the system according to Markovian arrival process (MAP) and service times have a phase type distribution. In these papers, homogeneous traffic is assumed, which is not always suitable for describing next-generation wireless communication networks, implying, in particular, the use of the Internet of Things and the presence of interaction between H2H users and M2M devices, see, e.g. [6,7,8]. The presence of heterogeneous requests gives rise to the need to develop new mechanisms to maintain the specified quality of service parameters for both H2H users and M2M devices. At the same time, with an increase in the intensity of the proposed load, the planners at the base station of the LTE network must determine the optimal strategy for the allocation of radio resources based on the established restrictions, for example, the probability of loss of requests from H2H users and the average transmission time of data blocks from M2M devices.

The queueing system considered in this paper significantly expands the capabilities of modeling real systems with processor sharing. We believe that there are restrictions on the number of users of different types simultaneously in service, and we do not introduce restrictive assumptions such as the homogeneity and uncorrelated nature of the customers flow, as well as the exponential distribution of service times for customers of different types. We assume that the input flow to the system is correlated and described by the marked Markov arrival process (MMAP) introduced in the paper [11]. For a more adequate description of the service process, we use a phase type distribution (PH) which is successfully used to approximate an arbitrary distribution.

Thus, in this paper we consider a queueing system with processor sharing which receives two types of customers arriving according to a MMAP. If at the moment of a customer arrival the number of customers of this type on the server is greater than a predetermined threshold, then the customer leaves the system un-handled, it is considered lost. Otherwise, the customer takes up part of the throughput of the channel and is serviced for a period of time having a PH distribution, the parameters of which differ for customers of different types.

2 Mathematical Model

We consider a queueing system with two type of customers and processor sharing. Customers of different types arrive into the system according to the MMAP under control of the irreducible Markov chain \(\nu _{t}\), \(t \ge 0 \), which takes values in the set \( \{0,1,2, \ldots , W \}\) and is called as an underlying process of the MMAP. The transitions of the underlying process accompanied by an arrival of a customer of type k are stored as entries of the matrix \(D_k\), \( k=1,2, \) of order \(\bar{W}\times \bar{W}\) where \(\bar{W}=W+1\) and idle transitions of this process are described by the matrix \( D_0\).

The arrival rate of customers of type k in the MMAP is given by \( \lambda _{k}=\boldsymbol{\theta }D_{k}{} \mathbf{e}, k=1,2, \) where the vector \( \boldsymbol{\theta }\), is defined as the unique solution of the system \( \boldsymbol{\theta }D(1)=\mathbf{0}, \boldsymbol{\theta }{} \mathbf{e}=1. \) The total arrival rate is \(\lambda =\lambda _1+\lambda _2.\)

The variance of inter-arrival times of customers of type k is calculated by the formula

$$ v_k = \frac{2\boldsymbol{\theta }(-D_0- \sum \limits _{l=1, l\ne k}^2 D_l)^{-1}{} \mathbf{e}}{\lambda _k} - \biggl (\frac{1}{\lambda _k}\biggr )^2,\; k=1,2. $$

The coefficient of correlation of the lengths of two adjacent intervals between the arrivals of customers of type k is calculated by

$$ c_{cor}^{(k)}=\biggl [\frac{\boldsymbol{\theta }(D_0+ \sum \limits _{l=1, l\ne k}^2 D_l)^{-1}}{\lambda _k} D_k(D_0+\sum \limits _{l=1, l\ne k}^2 D_l)^{-1}\mathbf{e}-\biggl (\frac{1}{\lambda _k}\biggr )^2\biggr ]v_k^{-1},\; k=1,2. $$

A detailed description of the MMAP can be found, for example, in [11].

In this paper we assume that the server can simultaneously serve up to N customers of type 1 and up to R customers of type 2. If only one customer of the kth type is serviced on the server, then its service time has the PH distribution given by the irreducible representation \((\boldsymbol{\beta }_k, S_k) \) and the underlying process \(m_{t}^{(k)},\, t\ge 0, \) with the state space \(\{1, \dots , M_{k}, M_{k} +1\}, \) where the state \(M_k+1 \) is absorbing. The intensities of transitions to the absorbing state are determined by the column vector \({\boldsymbol{S}}^{(k)}_0 =-S_k \mathbf{e}\). The service rate of a customer of type k is calculated as \(\mu _k=(\boldsymbol{\beta }_k(-S_k)^{-1}{} \mathbf{e})^{-1}.\)

The customers of each type divide the throughput of the server allocated to them equally. If the server simultaneously serves \(n_k\) customers of the kth type, then the service time of any of these customers has the PH distribution given by the irreducible representation \((\boldsymbol{\beta }_k, \frac{1}{n_k} S_k) \) and the underlying process \(m_{t}^{(k)}, \, t\ge 0, \) with the state space \(\{1, \dots , M_k, M_k+1\}, \) where the state \( M_k+1 \) is absorbing. The intensities of transitions to the absorbing state are determined by the column vector \( \frac{1}{n_k}{\boldsymbol{S}}^{(k)}_0 \).

If an incoming customer of type 1 finds \( n<N \) customers on the server, then it is sent for service. In this case, the throughput of the server allocated to customers of the 1st type is divided equally between \( n+1 \) customers. Otherwise, the customer leaves the system un-handled, it is considered lost. Similarly, if a customer of the 2nd type finds \(r<R \) customers on the server, then it is sent for service. The throughput of the server allocated to customers of type 2 is divided equally between \(r+1 \) customers. Otherwise, the customer is lost.

3 Process of the System States

The operation of the system is described by the regular irreducible Markov chain

$$ \xi _t= \{n_t, r_t, \eta _t^{(1)}, \eta _t^{(2)},\ldots , \eta _t^{(M_1)}, \tau _t^{(1)}, \tau _t^{(2)},\ldots , \tau _t^{(M_2)}, \nu _t\}, $$

where at the moment t

  • \(n_t\) is the number of customers of type 1 on the server, \(n_t=\overline{0, N};\)

  • \(r_t\) is the number of customers of type 2 on the server, \(r_t=\overline{0,R};\)

  • \(\eta _t^{(m^{(1)})}\) is the number of customers of type 1 that are served in the phase \(m^{(1)}\), \(\eta _t^{(m^{(1)})}=\overline{0, n_t},\) \(m^{(1)}=\overline{1,M_1};\)

  • \(\tau _t^{(m^{(2)})}\) is the number of customers of type 2 that are served in the phase \(m^{(2)}\), \(\tau _t^{(m^{(2)})}=\overline{0, r_t},\) \(m^{(2)}=\overline{1,M_2};\)

  • \(\nu _t\) is the state of underlying process of the MMAP, \(\nu _t=\overline{0,W}\),

In the following we will also use the processes

$$ \mathbf{u}_t^{(1)}=\{\eta _t^{(1)}, \eta _t^{(2)},\ldots , \eta _t^{(M_1)}\};\,\, \mathbf{u}_t^{(2)}=\{\tau _t^{(1)}, \tau _t^{(2)},\ldots , \tau _t^{(M_2)}\}. $$

Let us arrange the states of the considered Markov chain \(\xi _t, t\ge 0,\) as follows. We enumerate the components \(n_t, r_t\) in the direct lexicographic order and, for fixed values of these components, we renumber the states of the processes \( \mathbf{u}_t^{(1)} \) and \( \mathbf{u}_t^{(2)} \) in the reverse lexicographic order.

To further describe the transition rates of the chain, we need the matrices \(P_i(\cdot ),\,A_i(\cdot ,\cdot ),\) and \(L_{i}(\cdot , \cdot ), \) which have the following probabilistic sense: the matrix \( L_l (n, \tilde{S}_k) \) contains the transition rates of the process \(\mathbf{u}^{(k)}_t\), leading to the end of servicing of one of \(n-l\) customers of the kth type; the matrix \(P_{n}(\boldsymbol{\beta }_k) \) contains the transition probabilities of the process \( \mathbf{u}^{(k)}_t \) leading to an increase in the number of customers of the kth type on the server from n to \(n+1\); the matrix \(A_{n}(l, \tilde{S}_k) \) contains the transition rates of the process \(\mathbf{u}^{(k)}_t \) in its state space without increasing or decreasing the number of customers of the kth type. Here \( \tilde{S}_k = \left( \begin{array}{cc} 0&{}O \\ {\boldsymbol{S}}_0^{(k)}&{} S_l \\ \end{array}\right) , \,k=1,2. \) Algorithm for calculating matrices \(P_i(\cdot ), \, A_i(\cdot , \cdot ),\) and \( L_{i}(\cdot , \cdot ) \) follows from the results of V. Ramaswami and D. Lucantoni published in the papers [12, 13].

Let us introduce the notation \(Q_{n, n'}\) for the matrices of transition rates of the chain from the states corresponding to the value n of the first component to the states corresponding to the value \(n'\) of this component, \(n, n'=\overline{0, N }.\) We also introduce the following notation:

  • \(C_n^m=\left( \begin{array}{c} n\\ m \\ \end{array}\right) =\frac{n!}{m!(n-m)!};\)

  • \(diag\{a_1, a_2,..., a_n\}\) is a block diagonal matrix in which the diagonal blocks are equal to the elements listed in brackets, and the other blocks are zero;

  • \(diag^{+}\{a_1, a_2,..., a_n\}\,\,(diag^{-}\{a_1, a_2,..., a_n\})\) is a square block matrix in which the off-diagonal (below-diagonal) blocks are equal to the elements listed in brackets, and the other blocks are zero.

Lemma 1

The infinitesimal generator Q of a Markov chain \(\xi _t, t\ge 0,\) has the block three-diagonal structure

$$ Q= \left( \begin{array}{cccccc} Q_{0,0} &{} Q_{0,1} &{} O &{} \ldots &{} O &{} O\\ Q_{1,0}&{} Q_{1,1} &{} Q_{1,2} &{} \ldots &{} O &{} O\\ O &{} Q_{2,1} &{} Q_{2,2}&{} \ldots &{} O &{} O\\ \vdots &{} \vdots &{} \vdots &{} \ddots &{} \vdots &{} \vdots \\ O &{} O &{} O &{} \ldots &{}Q_{N-1, N-1} &{}Q_{N-1, N} \\ O &{} O &{} O &{} \ldots &{} Q_{N, N-1} &{} Q_{N, N}\end{array}\right) , $$

where

$$\begin{aligned} \begin{array}{c} Q_{0,0}=diag^{-}\{\frac{1}{r}L_{R-r}(R, \tilde{S}_2), r=\overline{1,R}\}\otimes I_{\bar{W}}\\ +\,diag\{0, \frac{1}{r}A_r(R, S_2), r=\overline{1,R} \}\oplus D_0 + diag\{O_{\sum \limits _{r=0}^{R-1}C_{r+M_2-1}^{M_2-1}}, I_{C_{R+M_2-1}^{M_2-1}}\}\otimes D_2\\ +\,diag^{+}\{P_r(\boldsymbol{\beta }_2), r=\overline{0, R-1}\}\otimes D_2+\varDelta _0;\\ Q_{n,n+1}=P_{n}(\boldsymbol{\beta }_1)\otimes I_{\sum \limits _{r=0}^{R}C_{r+M_2-1}^{M_2-1}}\otimes D_1,\, 0\le n\le N-1;\\ Q_{n,n-1}=\frac{1}{n} L_{N-n}(N, \tilde{S}_1)\otimes I_{\sum \limits _{r=0}^{R}C_{r+M_2-1}^{M_2-1}}\otimes I_{\bar{W}} ,\,\, 1\le n\le N;\\ Q_{n,n}=I_{C_{n+M_1-1}^{M_1-1}}\otimes diag^{-}\{ \frac{1}{r}L_{R-r}(R, \tilde{S}_2), r=\overline{1,R}\}\otimes I_{\bar{W}}\\ +\,\frac{1}{n}A_n(N, \tilde{S}_1)\oplus diag\{0, \frac{1}{r}A_r(R, S_2), r=\overline{1,R} \}\oplus (D_0+\delta _{n,N}D_1)\\ +\,I_{C_{n+M_1-1}^{M_1-1}}\otimes diag\{O_{\sum \limits _{r=0}^{R-1}C_{r+M_2-1}^{M_2-1}}, I_{C_{R+M_2-1}^{M_2-1}}\}\otimes D_2\\ +\,I_{C_{n+M_1-1}^{M_1-1}}\otimes diag^{+}\{P_r(\boldsymbol{\beta }_2), r=\overline{0, R-1}\}\otimes D_2+\varDelta _n, \, 1\le n\le N, \end{array} \end{aligned}$$

where \(\otimes (\oplus )\) denotes the Kronecker product (sum) of matrices, \(\delta _{n,N}\) is the Kronecker symbol, \(\varDelta _n, n=\overline{0, N},\) are diagonal matrices, which are constructed so that the equality \(Q\mathbf{e}=\mathbf{0}^T\) holds.

Proof

The generator block \(Q_{0,0}\) contains the transition rates in the set of states corresponding to the absence of customers of type 1. The corresponding transitions occur when

  1. a)

    one of the customers of type 2 finishes the service. The corresponding rates are given by the matrix \(diag^{-}\{\frac{1}{r}L_{R-r}(R, \tilde{S}_2), r=\overline{1,R}\}\otimes I_{\bar{W}}\);

  2. b)

    the number of customers of type 2 that are in a certain phase of servicing is changed or the MMAP underlying process makes an idle transition. The corresponding rates are given by the matrix \(diag\{0, \frac{1}{r}A_r(R, S_2), r=\overline{1,R} \}\oplus D_0;\)

  3. c)

    a customer of type 2 arrives and take place on the server (the matrix \(diag^{+}\{P_r(\boldsymbol{\beta }_2), r=\overline{0, R-1}\}\otimes D_2\)) or, if all places for customers of this type are occupied, the customer leaves the system un-handled (the matrix \( diag\{O_{\sum \limits _{r=0}^{R-1}C_{r+M_2-1}^{M_2-1}}, I_{C_{R+M_2-1}^{M_2-1}}\}\otimes D_2\).

Block \(Q_{n, n}, n=\overline{1, N} \), contains the transition rates in the set of states corresponding to the presence of n customers of type 1 in the system. The expression for this block differs from the expression for the block \(Q_{0,0}\) only in the second term, which in this case specifies the transition rates of the processes of servicing customers of types 1 and 2 in their sets of states without changing their numbers or the MMAP idle transition, or the loss of customer of type 1.

Block \(Q_{n, n+1}, n=\overline{0, N-1} \), contains the rates of transitions accompanied by the arrival of a customer of type 1 which takes up place on the server.

Block \(Q_{n, n-1}, n=\overline{1, N} \), contains the rates of transitions accompanied by the departure of the serviced customer of type 1 from the system.

All other blocks of the generator are zero matrces, since they consist of the rates of two or more transitions of the considered Markov chain on an infinitely small time interval.

4 Stationary Distribution. Performance Measures

In accordance with the described ordering of the states of the Markov chain \(\xi _t\), we form the row vectors \(\mathbf{p}_n, n=\overline{0, N},\) of the stationary probabilities of the states of the chain corresponding to the value n of the first component \(n_t\). Let \(\mathbf{p}=(\mathbf{p}_0, \mathbf{p}_1, \ldots ,\mathbf{p}_N)\) be the vector of steady state probabilities of the chain. This vector is the unique solution to the system of linear algebraic equation \(\mathbf{p}Q=\mathbf{0}, \mathbf{p}{} \mathbf{e}=1.\) If the dimension of this system is large, the solution can be calculated using the algorithm developed in [14].

Based on the stationary distribution, we can obtain formulas for calculating a number of stationary performance characteristics of the system. Below we present some of them.

  • Joint distribution of the number of type 1 customers on the server, the number of type 1 customers in different service phases, and the states of the MMAP

    $$ \mathbf{p}_n^*= \mathbf{p}_n (I_{C_{n+M_1-1}^{M_1-1}}\otimes \mathbf{e}_{\sum \limits _{r=0}^{R}C_{r+M_2-1}^{M_2-1}}\otimes I_{\bar{W}}),\,n=\overline{0,N}. $$

  • Distribution of the number of customers of type 1 in the system \( p_n=\mathbf{p}_n^*\mathbf{e}, \,n=\overline{0,N}. \)

  • Joint distribution of the number of type 2 customers on the server, the number of type 2 customers in different service phases, and the states of the MMAP

    $$ \mathbf{q}_r^*= \sum \limits _{n=0}^N \mathbf{p}_n (I^{(n,r)}\otimes I_{\bar{W}}), r=\overline{0,R}, $$

    where

    $$ I^{(n, r)}=\left( \begin{array}{ccc} O_{C_{n+M_1-1}^{M_1-1} \sum \limits _{m=0}^{r-1}C_{m+M_2-1}^{M_2-1}\times C_{r+M_2-1}^{M_2-1}}\\ \mathbf{e}_{C_{n+M_1-1}^{M_1-1}}\otimes I_{C_{r+M_2-1}^{M_2-1}}\\ O_{C_{n+M_1-1}^{M_1-1} \sum \limits _{m=r+1}^R C_{m+M_2-1}^{M_2-1}\times C_{r+M_2-1}^{M_2-1}}\\ \end{array} \right) . $$

  • Distribution of the number of customers of type 2 in the system \(\, q_r= \mathbf{q}_r^* \mathbf{e}, r=\overline{0,R}. \)

  • The probability of losing a customer of the kth type

    $$ P_{loss,k}=\frac{\lambda _k-\varphi _k}{\lambda _k}, \,k=1,2, $$

    where \(\lambda _k\) is the arrival rate of customers of kth type, \(\varphi _k\) is the output rate of customers of kth type. The value of \(\varphi _k\) is calculated as

    $$\begin{aligned} \begin{array}{c} \varphi _1=\sum \limits _{n=1}^N \mathbf{p}_n^*( I_{C_{n+M_1-1}^{M_1-1}}\otimes \mathbf{e}_{\bar{W}})\frac{1}{n}L_{N-n}(N, \tilde{S}_1)\mathbf{e},\\ \varphi _2=\sum \limits _{r=1}^R \mathbf{q}_r^*( I_{C_{r+M_2-1}^{M_2-1}}\otimes \mathbf{e}_{\bar{W}})\frac{1}{r} L_{R-r}(R, \tilde{S}_2)\mathbf{e}. \end{array} \end{aligned}$$

5 Sojourn Time Distribution

Denote by \(v_n^{(1)}(\eta ^{(1)}, \eta ^{(2)}, \ldots , \eta ^{(M_1)}, \tilde{\eta }, \nu , s)\) the Laplace-Stieltjes transform (LST) of the virtual sojourn time distribution of a customer of type 1 for which service began with the phase \(\tilde{\eta },\) and which found n customers of the first type in the system, the number of customers in phase \(m^{(1)}\) equal to \(\eta ^{(m^{(1)})},\) and the underlying process of the MMAP in the state \(\nu \), \(n=\overline{0, N-1},\) \(\eta ^{(m^{(1)})}=\overline{0, n},\) \(m^{(1)}=\overline{1, M_1},\) \(\nu =\overline{0, W}\).

Similarly, let \(v_r^{(2)}(\tau ^{(2)}, \ldots , \tau ^{(M_2)}, \tilde{\tau }, \nu , s) \) be the Laplace-Stieltjes transform of the virtual sojourn time distribution of a customer of type 2 for which service began with the phase \(\tilde{\tau }, \) and which found in the system r customers of the second type, the number of customers in the phase \(m^{(2)}\) equal to \(\tau ^{(m^{( 2)})}, \) and the underlying process of the MMAP in the state \(\nu \), \(r=\overline{0, R-1},\) \(\tau ^{(m^{(2)})}= \overline{0, r}, \, m^{(2)}=\overline{1, M_1},\) \(\nu =\overline{0, W} \). First we derive formulas of the conditional LSTs \(v_n^{(1)}(\eta ^{(1)}, \eta ^{(2)},\ldots , \eta ^{(M_1)}, \tilde{\eta }, \nu , s)\). Let us arrange these LSTs in the reverse lexicographic order of arguments \(\eta ^{(1)}, \eta ^{(2)},\ldots , \eta ^{(M_1)},\) in the direct lexicographic order of arguments \(\tilde{\eta }, \nu \) and form the column vectors

$$ \mathbf{v}_n^{(1)}( s),\, n=\overline{0,N-1}, \quad \mathbf{v}^{(1)}(s)=((\mathbf{v}_0^{(1)}(s))^T, (\mathbf{v}_1^{(1)}(s))^T, \ldots , (\mathbf{v}_{N-1}^{(1)}(s))^T)^T. $$

Similarly, for customers of type 2, we form the column vectors

$$ \mathbf{v}_r^{(2)}( s),\, r=\overline{0,R-1}, \quad \mathbf{v}^{(2)}(s)=((\mathbf{v}_0^{(2)}(s))^T, (\mathbf{v}_1^{(2}(s))^T, \ldots , (\mathbf{v}_{R-1}^{(2)}(s))^T)^T. $$

Theorem 1

The Laplace-Stieltjes transform vector \(\mathbf{v}^{(1)}(s)\) is calculated as follows:

$$\begin{aligned} \mathbf{v}^{(1)}(s)=(sI-A^{(1)})^{-1}{} \mathbf{b}^{(1)}, \end{aligned}$$
(1)

where

$$\begin{aligned} \begin{array}{c} A^{(1)}=diag\{[\frac{1}{n+1}A_{n}(N,S_1)+\varDelta _{n}]\oplus S_1\oplus (D_0+D_2), n=\overline{0,N-1}\}\\ +\,diag^-\{\frac{1}{n+1}L_{N-n}(N,\tilde{S}_1 )\otimes I_{M_1\bar{W}}, n=\overline{1,N-1} \}\\ +\,diag^+\{P_{n}({\boldsymbol{\beta }}_1)\otimes I_{M_1}\otimes D_1, n=\overline{0, N-2}\}\\ +\,diag\{O_{\bar{W}\sum \limits _{n=0}^{N-2}C_{n+M_1-1}^{M_1-1}}, I_{C_{N+M_1-2}^{M_1-1}}\}\otimes I_{M_1}\otimes D_1\},\\ \mathbf{b}^{(1)}=diag\{I_{C_{n+M_1-1}^{M_1-1}}\otimes \frac{1}{n+1} {\boldsymbol{S}}_0^{(1)}\otimes I_{\bar{W}}, n=\overline{0,N-1}\}{} \mathbf{e}. \end{array} \end{aligned}$$

Proof

Using the probabilistic interpretation of the Laplace-Stieltjes transform, we obtain the following equations for the vectors \(\mathbf{v}_n^{(1)}(s), n=\overline{0,N-1}:\)

$$\begin{aligned} \begin{array}{c} \mathbf{v}_n^{(1)}(s)=\\ \int \limits _0^\infty e^{-st}e^{[\frac{1}{n+1}A_{n}(N,S_1)+\varDelta _{n}]\oplus S_1t}(I_{C_{n+M_1-1}^{M_1-1}}\otimes \frac{1}{n+1} {\boldsymbol{S}}_0^{(1)})\otimes e^{(D_0+D_2)t} dt \mathbf{e}+\\ \int \limits _0^\infty e^{-st}e^{[\frac{1}{n+1}A_{n}(N,S_1)+\varDelta _{n}]\oplus S_1t}(L_{N-n}(N,\tilde{S}_1 )\otimes I_{M_1})\otimes e^{(D_0+D_2)t} dt \mathbf{e}{} \mathbf{v}_{n-1}^{(1)}(s)+\\ \int \limits _0^\infty (e^{-st}e^{[\frac{1}{n+1}A_{n}(N,S_1)+\varDelta _{n}]\oplus S_1t}\otimes e^{(D_0+D_2)t})(P_{n}({\boldsymbol{\beta }}_1)\otimes I_{M_1}\otimes D_1) dt \times \\ \mathbf{v}_{\min \{n+1, N-1\}}^{(1)}(s)\mathbf{e}. \end{array} \end{aligned}$$
(2)

Let us explain the meaning of the terms on the right-hand side of (2):

  • the first integral (first term) is the probability that the incoming virtual customer will be serviced before any of the n customers of type 1 that are already on the server at the time of the virtual customer arriving, and during the time of servicing the virtual customer there will be no catastrophe.

  • the integral in the second term is the vector of probabilities that after the arrival of the virtual customer one of the n customers of type 1 that are already on the server at the time of the arrival of the virtual customer will be served first, and no catastrophe will occur during the service of this first customer. After the first of the mentioned n customers is served, the server resource is redistributed between the remaining i customers, including the virtual one, and the further scenario of servicing the virtual customer up to the distribution of the MMAP states and service phases will be the same as at the moment of the arrival of a virtual customer that found \(n-1\) customers in the system. By definition, the corresponding vector of LSTs is \(\mathbf{v}_{n-1}^{(1)}(s)\) The product of the integral and \(\mathbf{v}_{n-1}^{(1)}(s)\) will give the required vector of LSTs of the service time distribution of the virtual customer.

  • when describing the third term, we will distinguish between the cases \(n<N-1\) and \(n=N-1.\) In both cases, the integral in the third term is a vector of probabilities that after the arrival of the virtual customer, the first event that entails a change in the number of customers on the server will be the arrival of a customer of type 1 and no catastrophe will occur in the time before it arrives. In the case \(n<N-1\), after this customer arrives, the server resource will be redistributed between \(n+2\) customers, including the virtual one, and the further scenario of servicing the virtual customer up to the distribution of the MMAP states and servicing phases will be the same as at the moment of arrival of the virtual customer that found \(n+1\) customers in the system. By definition, the corresponding vector of LSTs is \(\mathbf{v}_{n+1}^{(1)}(s).\) The product of the integral and \(\mathbf{v}_{n+1}^{(1)}(s)\) will give the required vector of LSTs of service time of the virtual customer. In the case \(n=N-1\) the received customer will be rejected, since the server already contains N customers, including the virtual one. Then the further scenario of servicing the virtual customer, up to the distribution of the states of the MMAP, will be the same as at the moment of the arrival of the virtual customer that found \(N-1\) customers in the system. By definition, the corresponding vector of LSTs is \(\mathbf{v}_{N-1}^{(1)}(s). \) The product of the integral and \(\mathbf{v}_{N-1}^{(1)}(s) \) will give the required vector of LSTs of service time of the virtual customer.

After calculating the integrals in (2) and a number of algebraic transformations, we obtain the required formula (1).

Corollary 1

The Laplace-Stieltjes transform vector \(\mathbf{v}^{(2)}(s)\) is calculated as follows:

$$ \mathbf{v}^{(2)}(s)=(sI_{\bar{W}}-A^{(2)})^{-1}{} \mathbf{b}^{(2)}, $$

where the matrix \(A^{(2)}\) and the vector \(\mathbf{b}^{(2)}\) are obtained from the matrix \(A^{(1)}\) and the vector \(\mathbf{b}^{(1)}\), respectively, by replacing N by R and permutation of indices 1 and 2.

Having known the Laplace-Stieltjes transforms defined in Theorem 1 and Corollary 1, we can find all the moments of the sojourn time, in particular, the mean and the variance of this time.

The corresponding mean (variance) for customers of type 1 we denote as \( \bar{v}_n^{(1)}(\eta ^{(1)}, \eta ^{(2)},\ldots , \eta ^{(M_1)}, \tilde{\eta },\nu )\) (\( d_n^{(1)}(\eta ^{(1)}, \eta ^{(2)},\ldots , \eta ^{(M_1)}, \tilde{\eta }, \nu )\)) and for customers of type 2 as \( \bar{v}_r^{(2)}(\tau ^{(1)},\ldots , \tau ^{(M_2)}, \tilde{\tau }, \nu )\) (\( d_n^{(2)}(\tau ^{(1)}, \tau ^{(2)},\) \( \ldots , \tau ^{(M_2)}, \tilde{\tau }, \nu )\)).

We renumber the values \(\bar{v}_n^{(1)}(\eta ^{(1)}, \eta ^{(2)},\ldots , \eta ^{(M_1)}, \tilde{\eta }, \nu ),\) \((\bar{v}_n^{(1)}(\eta ^{(1)}, \eta ^{(2)},\ldots , \) \(\eta ^{(M_1)}, \tilde{\eta }, \nu ))^2\) and \( d_n^{(1)}(\eta ^{(1)},\) \( \eta ^{(2)},\ldots , \eta ^{(M_1)}, \tilde{\eta }, \nu )\) in the lexicographic order described above and form the corresponding column vectors

$$ \bar{\mathbf{v}}^{(1)}_n,\,{\bar{\bar{\mathbf{v}}}^{(1)}}_n,\, \, \bar{\mathbf{d}}^{(1)}_n,\, n=\overline{0,N-1}. $$

In turn, from these vectors we form the column vectors

$$\begin{aligned} \begin{array}{c} \bar{\mathbf{v}}^{(1)}=((\bar{\mathbf{v}}^{(1)}_0)^T, (\bar{\mathbf{v}}^{(1)}_1)^T, \ldots , (\bar{\mathbf{v}}_{N-1}^{(1)})^T)^T,\,\,\, {\bar{\bar{\mathbf{v}}}^{(1)}}=(({\bar{\bar{\mathbf{v}}}^{(1)}}_0)^T, ({\bar{\bar{\mathbf{v}}}^{(1)}}_1)^T, \ldots , ({\bar{\bar{\mathbf{v}}}^{(1)}}_{N-1})^T)^T,\\ \mathbf{d}^{(1)}=((\mathbf{d}^{(1)}_0)^T, (\mathbf{d}^{(1)}_1)^T, \ldots , (\mathbf{d}^{(1)}_{N-1})^T)^T. \end{array} \end{aligned}$$

By analogy we introduce the column vectors \(\bar{\mathbf{v}}^{(2)}, {\bar{\bar{\mathbf{v}}}^{(2)}}, \mathbf{d}^{(2)}.\)

Corollary 2

The vector of conditional means, \(\bar{\mathbf{v}}^{(k)},\) and the vector of conditional variances, \(\mathbf{d} {(k)},\) of the sojourn times of a customer of type k are calculated by the following formulas:

$$ \bar{\mathbf{v}}^{(k)}=-(A^{(k)})^{-1}{} \mathbf{e},\,\, \mathbf{d}^{(k)}=2(A^{(k)})^{-2}{} \mathbf{e}-{\bar{\bar{\mathbf{v}}}^{(k)}},\,k=1,2. $$

To calculate the Laplace-Stieltjes transforms of the sojourn time distributions of the customers of type 1 and 2 admitted into the system, we introduce into consideration the vector \(\mathbf{p}^+\) (\( \mathbf{q}^+\)), the components of which define the joint distribution of the number of type 1 (type 2) customers that are in different service phases and the states of the MMAP immediately after the moment the customer of type 1 (type 2) has been admitted into the system. It is easy to see that these vectors are calculated as follows:

$$\begin{aligned} \begin{array}{c} \mathbf{p}^+= \lambda _1^{-1}(\mathbf{p}_0^*, \mathbf{p}_1^*,\ldots , \mathbf{p}_{N-1}^*)[diag\{{P_n({\boldsymbol{\beta }}_1}), n=\overline{0, N-1}\}\otimes D_1],\\ \mathbf{q}^+= \lambda _2^{-1}(\mathbf{q}_0^*, \mathbf{q}_1^*,\ldots , \mathbf{q}_{R-1}^*)[diag\{P_r({\boldsymbol{\beta }}_2), r=\overline{0, R-1}\}\otimes D_2]. \end{array} \end{aligned}$$

Theorem 2

The Laplace-Stieltjes transformations of the sojourn time distributions of the customers of type 1 and type 2 accepted to the system are calculated as

$$ v^{(1)}(s)=\mathbf{p}^+\mathbf{v}^{(1)}(s),\quad v^{(2)}(s)= \mathbf{q}^+\mathbf{v}^{(2)}(s). $$

Corollary 3

The means and variances of the sojourn times of customers of type 1 and type 2 accepted to the system are calculated using the following formulas:

$$ \bar{v}^{(1)}=\mathbf{p}^+\bar{\mathbf{v}}^{(1)},\,\, d^{(1)}= \mathbf{p}^+ \mathbf{d}^{(1)}; \quad \bar{v}^{(2)}=\mathbf{q}^+\bar{\mathbf{v}}^{(2)},\,\, d^{(2)}=\mathbf{q}^+ \mathbf{d}^{(2)}. $$

6 Numerical Results

In this section we conduct a number of numerical experiments aimed at studying the behavior of the performance characteristics of the system depending on its parameters and at solving optimization problems. To carry out the experiments, a computer program was written in Python using built-in packages for processing matrices, calculating complex mathematical formulas and executed in the PyCharm 2019.3.4 (Professional Edition) program.

In Experiment 1 we analyse the dependence of the loss probabilities, \(P_{loss,k}, k=1,2,\) and the mean sojourn times, \(\bar{v}^{(k)}, k=1,2,\) on the maximum number of channels allocated for customers of type k. In this experiment we used the following input data.

The MMAP is specified by the matrices \(D_0,\) \(D_1\), \(D_2\), where

$$ D_0 = \left( \begin{array}{cc} -86 &{} \,0.01 \\ 0.02 &{} \,-2.76 \end{array}\right) ,\quad D_1 = \left( \begin{array}{cc} 59.5 &{} \,0.693 \\ 0.14 &{} \,1.778 \end{array}\right) , \quad D_2 = \left( \begin{array}{cc} 25.5 &{} \,0.297 \\ 0.06 &{} \,0.762 \end{array}\right) . $$

With such matrices \(\lambda =12.43, \lambda _1=0.7\lambda \) and \(\lambda _2=0.3\lambda , \,c_{cor}^{(1)}=0.39,\, c_{cor}^{(2)}=0.33.\)

The PH distribution of the service time of a single customer of type 1 is given by the vector \(\boldsymbol{\beta }^{(1)}=(1,\,0)\) and the matrix \( S^{(1)}=\left( \begin{array}{cc} -80&{} \,80 \\ 0&{} \,-80 \end{array}\right) . \) This means that the service time has Erlang distribution of order 2 with parameter 80 and the service rate \(\mu _1 = 40.\)

Fig. 1.
figure 1

\(P_{loss,1}\) and \(P_{loss,2}\) vs N under fixed number of channels \(N+R=30\)

Full size image
Fig. 2.
figure 2

\(\bar{v}^{(1)}\) and \(\bar{v}^{(2)}\) vs N under fixed number of channels \(N+R=30\)

Full size image

The PH distribution of the service time of a single customer of type 2 is given by the vector \(\boldsymbol{\beta }^{(2)}=(1,\,0)\) and the matrix \( S^{(2)}=\left( \begin{array}{cc} -20&{} \,20 \\ 0&{} \,-20 \end{array}\right) . \) This means that the service time has Erlang distribution of order 2 with parameter 20 and the service rate \(\mu _2 = 10.\)

The total number of channels, into which the throughput of the servers is divided, is \(N+R=30\).

It is seen from Fig. 1 that \(P_{loss, 1}\) decreases and \( P_{loss, 2}\) increases. This is due to the fact that with an increase in N the possible number of type 1 customers in the system increases and the smaller part of the customers will be lost. Taking into account the equality \(N+R=30 \), with an increase in N the value of R decreases and more and more customers are lost.

Figure 2 shows that \(\bar{v}^{(1)}\) is an increasing function of N. This is due to the fact that with an increase in N the throughput allocated for a customer of type 1 decreases and hence the sojourn time increases. Due to the relation \(N+R=30\) when N increases then R decreases. That entails an increase in the throughput available for a customer of type 2 and a decrease in the time for servicing the customer.

Experiment 2. In this experiment, we solve numerically the optimization problem which consists in the optimal sharing of the throughput \(\mu =\mu _1+\mu _2 \) of the server between customers of types 1 and 2 and the optimal choice of the maximum numbers of simultaneously served customers of types 1 and 2 under the given restrictions on the minimum throughput allocated for each customer.

As a criterion for the quality of the operation of the system, we use the economic functional, which is the average penalty per unit of time

$$\begin{aligned} J= a{\bar{N}}+c_1\lambda _1P_{loss,1} +c_2\lambda _2P_{loss,2}, \end{aligned}$$
(3)

where a is the penalty charged per unit of time spent by one customer of type 1 in the system, \(c_k\) is the penalty charged for the lost customer of type k, \( k = 1,2. \)

The problem is to choose the parameters \( \mu _1\), N and R which provide the minimum to criterion (3) under the following conditions:

$$\mu _1+\mu _2=\mu =const,\,\, \gamma _1=\frac{\mu _1}{N}=const,\,\,\gamma _2=\frac{\mu _2}{R}=const.$$

Here \(\gamma _k\) is the minimum throughput of the server that can be used to provide service to a customer of type k.

Fig. 3.
figure 3

\(\bar{N}\) vs \(\mu _1\) under restrictions \(\mu =70, \gamma _1=2, \gamma _2=7\)

Full size image

In the experiment, we will use the MMAP specified in Experiment 1. The shape of service time distributions is the same as in Experiment 1. In the course of the current experiment, we will only change the service rates \(\mu _1\) and \(\mu _2\) multiplying the matrices \(S_1, S_2\) by the corresponding constants. We fix the values of \(\mu , \gamma _1, \gamma _2\) as \(\mu =70, \gamma _1 = 2, \gamma _2 = 7.\)

For these initial data, let us look at the graphs of the dependence of the mean number of customers of the type 1, \(\bar{N},\) and the probabilities of losses of customers of different types, \(P_{loss,1}, P_{loss,2}\), which are shown in Fig. 3 and 4.

Fig. 4.
figure 4

\(P_{loss,1}, P_{loss,2}\) vs \(\mu _1\) under restrictions \(\mu =70, \gamma _1=2, \gamma _2=7\)

Full size image
Fig. 5.
figure 5

J vs \(\mu _1\) for \(c_1=1\), \(c_2=20\), \(a = 1, 3, 7\) under restrictions \(\mu =70, \gamma _1=2, \gamma _2=7\)

Full size image

Having calculated the dependence of \(\bar{N},\) \(P_{loss,1}, P_{loss,2}\) on \(\mu _1\) we can calculate the dependence of the cost criteria J on \(\mu _1\) under different cost coefficients. Let us consider the following cost coefficients: \( a = 1, 3, 7, c_1 = 1, c_2 = 20. \) The results of calculation are presented in Fig. 5 and in Table 1.

Table 1. Values of N, R, J as functions of \(\mu _1\) for \(c_1=1\), \(c_2=20\), \(a=1, 3, 7\) under restrictions \(\mu =70, \gamma _1=2, \gamma _2=7\)
Full size table

It is seen from Fig. 5 and Table 1 that for input data under consideration the server throughput is divided approximately in half between customers of types 1 and 2. In the case a = 1, 3, it is optimal to divide the throughput allocated to customers of types 1 and 2 as 17:5. When a = 7, this proportion changes as 20:4.

7 Conclusion

We analysed a queuing system with the MMAP of customers of two types, processor sharing and a limited number of places for customers of different types. We described the system operation by the multi-dimensional Markov chain, calculated its stationary distribution and the main performance characteristics. The Laplace-Stieltjes transform of the sojourn time distribution is found. Formulas for means and variances of the sojourn time are obtained. We carried out numerical experiments to study the behavior of the system performance characteristics and to find the optimal strategy for sharing the processor throughput between users of different types. The results obtained can be used in the study and planning of telecommunication networks for various purposes, in particular, the Internet of Things.