# Stationary Distribution of Waiting Time in MAP/G/1/N Queueing System with LIFO Service Discipline

Alexander Dudin, Valentina Klimenok, Konstantin Samouylov

► To cite this version:

Alexander Dudin, Valentina Klimenok, Konstantin Samouylov. Stationary Distribution of Waiting Time in MAP/G/1/N Queueing System with LIFO Service Discipline. 15th International Conference on Wired/Wireless Internet Communication (WWIC), Jun 2017, St. Petersburg, Russia. pp.50-61, 10.1007/978-3-319-61382-6_5 . hal-01675436

HAL Id: hal-01675436

https://inria.hal.science/hal-01675436

Submitted on 4 Jan 2018

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Stationary Distribution of Waiting Time in MAP/G/1/N Queueing System with LIFO Service Discipline

Alexander Dudin¹*,² and Valentina Klimenok¹,² Konstantin Samouylov,²

¹ Department of Applied Mathematics and Computer Science
Belarusian State University
Minsk 220030, Belarus

dudin@bsu.by, klimenok@bsu.by

² Department of Applied Probability
and Informatics
RUDN University,
6 Miklukho-Maklaya st., 117198,
Moscow, Russia ksam@sci.pfu.edu.ru

**Abstract.** In this paper, we consider single server queueing system with a finite buffer, MAP input and independent generally distributed service times. Customers are selected for the service in accordance with the LIFO (Last In – First Out) service discipline. It is well known that stationary distribution of the number of customers in such a system coincides with the corresponding distribution in the system with FIFO (First In – First Out) discipline which has been studied in the literature early. In the present research we focus on investigating the stationary distribution of waiting (sojourn) time in the system.

*Keywords:* Single-server queue, Finite buffer, Markovian arrival process, LIFO service discipline, Waiting time distribution, Resource management and admission control

## 1 Introduction

Queueing systems with invasive service discipline (Last-in-First-out, LIFO) can be used to describe the data processing in many real systems. LIFO discipline is used in cases when the last data written into the structure of data must be removed or processed first. A useful analogy with the office worker is: a person can only work with one page at a time, so a new document is added to a folder on the top of the stack of the previous documents. By analogy, in a computer we also have limitations such as the width of the data bus and every time the system can manipulate with only one memory cell. Abstract mechanism of the LIFO is

<footnote>* Corresponding author.</footnote>
used in calculations realized in the real structures of data in the form of a stack,
which is obviously related to a "pack of paper", a "pile of plates", and so on.
The term LIFO emphasizes that in the process of list processing and temporary
storage of a limited set of data the last written data must be processed first.

LIFO service discipline can be considered as the opposed one to the or-
dered FIFO service discipline. Queueing systems with FIFO service discipline
are most popular among researches because the corresponding real systems are
more common. The second reason for popularity of FIFO discipline is the fact
that distributions of the queue length in the systems with FIFO and LIFO dis-
ciplines are the same. It allows sometimes to get the desired results for a queue
with LIFO discipline using the results of investigation of the corresponding queue
with FIFO discipline which is generally easier to study.

However, the distributions of waiting (sojourn) time in the queues with FIFO
and LIFO are different. For queueing system with stationary Poisson flow, an
infinite buffer and LIFO service discipline the stationary distribution of the wait-
ing (sojourn) time has been obtained early, see, for example, [9]. But we do not
know results concerning the distribution of waiting (sojourn) time for the analo-
gous system with a finite buffer, and even much less results for the system with
a finite buffer and the input flow different from the stationary Poisson one.

Both disciplines, FIFO and LIFO, are widely used in modern telecommunica-
tion and computer networks. E.g., comparison of these discipline (with variants
of tail-drop and front-drop of packets) in application to modelling the delivering
of live multimedia streaming over ad hoc networks is given in [11]. Application
of LIFO discipline in multihop networks is discussed in [7].

The flows in modern telecommunication and computer networks can consid-
erably differ from a stationary Poisson one. In particular, they do not possess
the basic property of a stationary Poisson flow - memoryless property. There-
fore, in the past decade and more queueing systems with correlated flows have a
great interest among researchers in the field of telecommunications and queuing
theory. At the present time, the most popular mathematical model of such flows
is a Markovian Arrival Process.

In this paper we consider single server queueing system with a finite buffer, MAP input and generally distributed service time. Customers are selected for the service in accordance with LIFO service discipline. As in was mentioned above, the stationary distribution of the number of customers in such a system coincides with the corresponding distribution in the system with FIFO discipline which has been studied in [2], [3], [4]. In the present research, we focus on in- vestigating the stationary distribution of waiting (sojourn) time of an arbitrary customer admitted into the system and arbitrary customer.

## 2 Model description

We consider a single server queueing system with a finite buffer of size *N* and
LIFO service discipline. Customers arrive into the system in accordance with
a Markovian Arrival Process (*MAP*). The *MAP* is defined by the underlying
process $v_t$, $t \ge 0$, which is an irreducible continuous-time Markov chain with finite state space $\{0, \dots, W\}$, and the $(W+1) \times (W+1)$ matrices $D_0$ and $D_1$. The entries of the matrix $D_0$ define the rates of the process $v_t$, $t \ge 0$, transitions which are accompanied by generating a customer while non-diagonal entries of the matrix $D_0$ describe the rates of the process $v_t$, $t \ge 0$, transitions which are not accompanied by generating a customer. The matrices $D_0$ and $D_1$ can be defined by their matrix generating function $D(z) = D_0 + D_1z$, $|z| \le 1$. The matrix $D(1)$ is an infinitesimal generator of the process $v_t$, $t \ge 0$. The intensity (fundamental rate) of the MAP is defined as

$$ \lambda = \theta D_1 e $$

where $\theta$ is the unique solution of the system

$$ \theta D(1) = 0, \theta e = 1, $$

and the intensity of batch arrivals is defined as $\lambda_b = \theta(-D_0)e$. Here and in the sequel $e(0)$ is a column (row) vector of appropriate size consisting of 1's (0's). The coefficient of variation, $c_{var}$, of intervals between batch arrivals is given by

$$ c_{var}^2 = 2\lambda_b\theta(-D_0)^{-1}e - 1 $$

while the coefficient of correlation, $c_{cor}$, of intervals between successive batch arrivals is calculated as

$$ c_{cor} = (\lambda_b \theta(-D_0)^{-1} D_1 (-D_0)^{-1} e - 1) / c_{var}^2. $$

Let $p_{\nu,\nu'}(k,t)$ be the probability that $k$ customers arrive in the MAP during the interval $(0,t)$ and the state of the underlying process $v_t$ of the MAP at the moment $t$ is $\nu'$ given that $\nu_0 = \nu$. Denote

$$ P(k,t) = (p_{\nu\nu'}(k,t))_{\nu,\nu'=0,W}, \quad k \ge 0. $$

Then, the matrices $P(k,t)$ are defined as the coefficients of the matrix expansion

$$ e^{D(z)t} = \sum_{k=0}^{\infty} P(k,t)z^k, \quad |z| \le 1. $$

For more information about the MAP see, e.g., [8].

The successive service times of customers are independent random variables with general distribution $B(t)$, Laplace-Stieltjes transform

$$ \beta(s) = \int_{0}^{\infty} e^{-st} dB(t), \quad Re \ s > 0, $$

$$ \text{and finite first moment } b_1 = \int_{0}^{\infty} t dB(t) < \infty. $$

As it was noted above, in the literature there are no results regarding such important performance measure of the system under study as waiting time. This paper is devoted to finding the Laplace-Stieltjes transform of the stationary distribution of the waiting time in such a system.
### 3 Laplace-Stieltjes Transform of the Stationary Distribution of Waiting Time

Let us introduce the following notation:

* $\Pi_{n,\nu,\nu'}(t)$ be the probability that the length of the busy period generated by a customer, which goes to the service leaving $n$ customers in the buffer, is less than $t$ and at the end of this period the MAP is in the state $\nu'$ under condition that at the beginning of the busy period the MAP was in the state $\nu$, $n = \bar{0}, \bar{N}, \nu, \nu' = \bar{0}, \bar{W}$;

* $\pi_{n,\nu,\nu'}(s) = \int_{0}^{\infty} e^{-st} d\Pi_{n,\nu,\nu'}(t), Re s \ge 0$;

* $\Pi_n(s) = (\pi_{n,\nu,\nu'}(s))_{\nu,\nu'=\bar{0},\bar{W}}$;

* $W_{n,\nu,\nu'}(t)$ be the probability that the waiting time of a customer, which sees $n$ customers in the system at the arrival moment, is less than $t$ and at the end of the waiting time the MAP is in the state $\nu'$ under condition that at the arrival moment the MAP was in the state $\nu, n = \bar{0}, \bar{N}, \nu, \nu' = \bar{0}, \bar{W}$;

* $w_{n,\nu,\nu'}(s) = \int_{0}^{\infty} e^{-st} dW_{n,\nu,\nu'}(t)$;

* $W_n(s) = (w_{n,\nu,\nu'}(s))_{\nu,\nu'=\bar{0},\bar{W}}$.

**Lemma 1.** The matrices $\Pi_n(s)$ of LSTs of distribution of the length of the busy period generated by a customer, which goes to the service leaving $n$ customers in the buffer, are calculated by the formulas of backward recursion

$$ \Pi_n(s) = \left\{ I - \sum_{k=1}^{N-n-1} Y_k(s) \Pi_{n+k-1}(s) \Pi_{n+k-2}(s) \dots \Pi_{n+1}(s) - \right. \\ \left. - [\beta(sI - D(1)) - \sum_{k=0}^{N-n-1} Y_k(s)] \Pi_{N-1}(s) \Pi_{N-2}(s) \dots \Pi_{n+1}(s) \right\}^{-1} \beta(sI - D_0), \\ n = N-1, N-2, \dots, 0, \qquad (1) $$

where

$$ \beta(sI - D(1)) = \int_{0}^{\infty} e^{-(sI - D(1))x} dB(x), \\ Y_k(s) = \int_{0}^{\infty} e^{-sx} P(k, x) dB(x), k \ge 0, \qquad (2) $$

I is the identity matrix. When it is needed, the dimension of the matrix is indicated as its suffix.

**Proof.** The proof is based on the probabilistic interpretation of the Laplace-Stieltjes transform. We assume that, independently on the system operation, the stationary Poisson input of so called catastrophes arrives. Let $s, s > 0$, be the rate of this flow.
Then $\Pi_n(s)$ is a matrix probability that during the busy period generated by a tagged customer, which goes to the service leaving $n$ customers in the buffer, a catastrophe does not arrive.

First, consider $n = N-1$. Let us calculate $\Pi_{N-1}(s)$ using the total probability formula. To this end, consider two cases: a) during the service time of the tagged customer no customers arrive at the system and b) during the service time of the tagged customer one or more customers arrive at the system.

In case a) the busy period under consideration ends at the service completion epoch. The matrix probability that during the service time no customers arrive at the system and a catastrophe does not arrive is equal to $\int_{0}^{\infty} e^{-sx}e^{D_{0}x}dB(x)$.

In case b) the length of the busy period under consideration ($L_{tag}$) can be represented as a sum of two independent random variables: service time of the tagged customer and the length of busy period generated by youngest customer arrived at the system during the service time ($L_{youn}$).

A matrix probability that during the service time one or more customers arrive at the system and a catastrophe does not arrive is equal to $\int_{0}^{\infty} e^{-sx}(e^{D(1)x} - e^{D_{0}x})dB(x)$.

The distribution of the random variable $L_{youn}$ is the same as the distribution of $L_{tag}$. From this it follows that a matrix probability that during the period $L_{youn}$ a catastrophe does not occur is equal to $\Pi_{N-1}(s)$. Then a matrix probability that during the service time of the tagged customer one or more customers arrive at the system and a catastrophe does not arrive during the busy period $L_{tag}$ is equal to the product $\int_{0}^{\infty} e^{-sx}(e^{D(1)x} - e^{D_{0}x})dB(x)\Pi_{N-1}(s)$.

From all has been said and the total probability formula it follows that the matrix $LST \Pi_{N-1}(s)$ is calculated as

$$ \Pi_{N-1}(s) = \int_{0}^{\infty} e^{-sx}e^{D_{0}x}dB(x) + \int_{0}^{\infty} e^{-sx}(e^{D(1)x} - e^{D_{0}x})dB(x)\Pi_{N-1}(s). $$

The similar arguments lead to the following relation:

$$ \begin{aligned} \Pi_{N-i}(s) = & \int_{0}^{\infty} e^{-sx}e^{D_{0}x}dB(x)+ \\ & + \int_{0}^{\infty} e^{-sx} \sum_{k=1}^{i-1} P(k,x)dB(x)\Pi_{N-i+k-1}(s)\Pi_{N-i+k-2}(s)\Pi_{N-i}(s)+ \\ & + \int_{0}^{\infty} e^{-sx} [e^{D(1)x} - \sum_{k=0}^{i-1} P(k,x)]dB(x)\Pi_{N-1}(s) \dots \Pi_{N-i}(s), \quad i = 1, 2, \dots, N. \quad (3) \end{aligned} $$
Using notation of Lemma 1 and introducing the value $n = N - i$, we obtain from (3) formula (1).

Now we are able to derive the LST of the distribution of the waiting time of a customer admitted into the system.

**Lemma 2.** The matrix $W_n(s)$ of LSTs of distributions of waiting time of a customer, which sees $n$ customers in the system at the arrival moment is calculated as follows:

$$W_0(s) = I_{W+1},$$

$$W_n(s) = \sum_{k=0}^{N-n} \tilde{Y}_k(s) \Pi_{k+n-1}(s) \Pi_{k+n-2}(s) \dots \Pi_n(s) + [\tilde{\beta}(sI - D(1)) - \sum_{k=0}^{N-n} \tilde{Y}_k(s)] \Pi_{N-1}(s) \Pi_{N-2}(s) \dots \Pi_n(s), \quad n = \overline{1, N}, \quad (4)$$

where

$$\tilde{\beta}(sI - D(1)) = \int_{0}^{\infty} e^{-(sI - D(1))x} d\tilde{B}(x), \\ \tilde{Y}_n(s) = \int_{0}^{\infty} e^{-sx} P(n, x) d\tilde{B}(x), \quad (5)$$

$\tilde{B}(t)$ is a distribution function of residual service time,

$$\tilde{B}(t) = b_1^{-1} \int_{0}^{t} (1 - B(x)) dx.$$

**Proof.** We should prove formula (4) for $1 \le n \le N$. Let an arriving (tagged) customer finds $n > 0$ customer in the system. It means that one customer is in the service and the rest $n - 1$ customers stay in the buffer. Suppose that during the residual service time $k$ customers arrive at the system, $k = \overline{0, N-n}$. Then all these customers will be admitted into the system.

Using the probabilistic interpretation of the Laplace-Stieltjes transform, we interpret $\int_{0}^{\infty} e^{-sx} P(k, x) d\tilde{B}(x)$ as a matrix probability that $k$ customers arrive at the system and during the residual service time a catastrophe does not arrive. Then, at the end of the current service, $n + k$ customers stay in the buffer. A customer which came last (the $k$th customer) will go to the service first. This customer leaves $n + k - 1$ customers in the buffer and initializes busy period generated by this customer. By Lemma 1, LSTs of distributions of busy period generated by the customer are given by the matrix $\Pi_{k+n-1}(s)$. After that, the $(k-1)$th customer arrived during residual service time will go to the service. LSTs of distributions of busy period generated by this customer are given by the matrix $\Pi_{k+n-2}(s)$.
The similar reasoning lead to the conclusion that the tagged customer will go to the service, i.e. his/her waiting time is over, when the busy period generated by the first customer arrived at the system during the residual service time ends. This first customer, entering the service, leaves in the buffer n customers and distribution of the busy period, generated by this customer, has matrix LST $\Pi_n(s)$.

Since busy periods, generated by k customers arrived at the system during the residual service time and placed in the buffer in front of our tagged customer, are independent random variables then their sum has a distribution with the matrix LST $\Pi_{k+n-1}(s)\Pi_{k+n-2}(s)\dots\Pi_n(s)$. During the residual service time, k customers can be admitted into the buffer, where $k = 0, N-n$. This explains presence of the sum over k in the first term on the right side of (4).

The second term on the right side (4) corresponds to the case when during the residual service time more than $N-n$ customers arrive at the system. The matrix probability that during the residual service time more than $N-n$ customers arrive at the system and a catastrophe does not occur is equal to $\int_0^\infty e^{-sx}[e^{D(1)x} - \sum_{k=0}^{N-n} P(k, x)]d\tilde{B}(x)$. Further arguments are similar to those in the derivation of the first term on the right side of (4) and lead to the corresponding expression on the right side of (4).

Introduce the notation for the joint stationary distribution of the number of customers in the system and state of the underlying process of the MAP at an arbitrary time:

$$p_i(\nu) = \lim_{t \to \infty} P\{i_t = i, \nu_t = \nu\}, \quad \nu = \overline{0, W+1}, \\ \mathbf{p}_i = (p_i(0), p_i(1), \dots, p_i(W)), \quad i = \overline{0, N+1}.$$

As it was mentioned before, the stationary distribution $\mathbf{p}_i$, $i = 0, N+1$, can be calculated as the stationary distribution of the system MAP/G/1 with FIFO service discipline. The corresponding result is presented in [2], [3]. Then, we can calculate the LST $w(s)$ using the following theorem.

**Theorem 1.** The LST $w(s)$ of the distribution of the waiting time of an arbitrary customer admitted into the system is calculated as

$$w(s) = \sum_{i=0}^{N} \mathbf{p}_i \frac{D_1}{\lambda} W_i(s)\mathbf{e}. \qquad (6)$$

**Proof** of the theorem follows from the total probability formula.

**Corollary 1.** The LST $\tilde{w}(s)$ of the distribution of the waiting time of an arbitrary customer is calculated as

$$\tilde{w}(s) = P_{loss} + w(s)(1 - P_{loss})$$

where the probability $P_{loss}$ of an arbitrary customer loss is computed as

$$P_{loss} = \mathbf{p}_{N+1} \frac{D_1 \mathbf{e}}{\lambda}.$$
**Corollary 2.** The rth moment of the waiting time of an arbitrary customer admitted into the system is calculated as

$$E_r\{w\} = (-1)^r \frac{d^r w(s)}{ds^r}\Big|_{s=0}, r \ge 1.$$

## 4 Calculation of the matrices $Y_n(s)$ and $\tilde{Y}_n(s)$

In the numerical implementation of formulas (1), (4) the problem of computing the matrices $Y_k(s)$ and $\tilde{Y}_k(s)$ defined by (2) and (5) arises.

First, we consider the problem of calculating the matrices $Y_k(s)$. In general, the elements of integration, matrices $P(k, t)$, $k \ge 0$, are not computed in explicit form, so to calculate these matrices, a procedure based on uniformization of the matrix exponent can be used. Such a procedure is described, e.g., in [6], [8]. In our case, we use this procedure with minor modification, and obtain the following formula for the calculation of the matrices $Y_n(s)$:

$$Y_n(s) = \sum_{j=0}^{\infty} \gamma_j(s) K_n^{(j)}, n \ge 0,$$

where $\gamma_j(s) = \int_0^\infty e^{-(\varphi+s)x} \frac{(\varphi t)^j}{j!} dB(x)$, $j \ge 0$, $\varphi$ is a maximum of modules of the diagonal entries of the matrix $D_0$, the matrices $K_n^{(j)}$, $n \ge 0, j \ge 0$, are computed using the recurrent formula given in [6], [8].

Calculation of the matrices $Y_n(s)$, $n \ge 0$, is greatly simplified when the service time has Phase type (PH) distribution. Class of such distributions is sufficiently general and is dense in the set of nonnegative distributions, see, e.g., [1] and [10]. The reader can find the definition and properties of PH distribution e.g., in [10]. Here we suppose that the reader is generally conversant with definition and properties of PH distribution and suggest that service time has PH distribution with an irreducible representation $(g, G)$ where $g$ is a stochastic $M$-size row vector and $G$ is a matrix of size $M$ which has the property of a sub-generator. Then the distribution function $B(t)$ has the following form:

$$B(t) = 1 - g e^{Gt} G_0$$

where $G_0 = -Ge$.

Substituting in (2) the expression for $B(t)$ and using the mixed product rule, we have

$$Y_k(s) = \int_0^\infty e^{-sx} P(k, x) dB(x)$$
$$ 
\begin{aligned}
&= \int_{0}^{\infty} e^{-sx} P(k, x) g e^{Gx} \mathbf{G}_{0} dx \\
&= (I_{\bar{W}} \otimes g) \int_{0}^{\infty} P(k, x) \otimes e^{(G-sI)x} dx (I_{\bar{W}} \otimes \mathbf{G}_{0})
\end{aligned} 
\quad (7) 
$$

where $\otimes$ is a symbol of Kronecker product of matrices, see [5].

Now we try to calculate the integral in (7).

For $n = 0$, we have $P(0, x) = e^{D_0 x}$ and we obtain the following formula

$$ \int_{0}^{\infty} P(0, x) \otimes e^{(G-sI)x} dx = -[D_0 \oplus (G-sI)]^{-1} \quad (8) $$

where $\oplus$ is a symbol of Kronecker sum of matrices, see [5].

To calculate the integrals for $n > 0$, we use the formula for integration by parts and the well known from the theory of MAPs the matrix differential equations:

$$ P'(k, x) = \sum_{l=0}^{k} P(l, x) D_{k-l}, \quad k \ge 0. \quad (9) $$

Then the following relations take place

$$ 
\begin{aligned}
\int_{0}^{\infty} P(k, x) \otimes e^{(G-sI)x} dx &= P(k, x) \otimes (G-sI)^{-1} e^{(G-sI)x} \Big|_{0}^{\infty} \\
&\quad - \int_{0}^{\infty} P'(k, x) \otimes e^{(G-sI)x} dx [I_{\bar{W}} \otimes (G-sI)^{-1}] \\
&= - \sum_{l=0}^{k} \int_{0}^{\infty} P(l, x) D_{k-l} \otimes (sI - G)^{-1} e^{(G-sI)x} dx. \quad (10)
\end{aligned}
 $$

Denote

$$ F_l(s) = \int_{0}^{\infty} P(l, x) \otimes e^{(G-sI)x} dx, \quad l \ge 0. \quad (11) $$

Using this notation, after some algebra we derive from (10) the following recursive formula for calculating the matrices $F_k(s)$:

$$ F_k(s) = - \sum_{l=0}^{k-1} \int_{0}^{\infty} F_l(x) (D_{k-l} \otimes I_M) [D_0 \oplus (sI - G)^{-1}]^{-1}, \quad k > 0, \quad (12) $$

with boundary condition (8).
Having the matrices $F_n(s)$ been calculated, we are able to calculate the required matrices $Y_k(s)$ by formula (7) which takes the form

$$Y_k(s) = (I_{\bar{W}} \otimes g) F_k(s) (I_{\bar{W}} \otimes G_0), k \ge 0. \quad (13)$$

Now we focus on calculating the matrices $\tilde{Y}_k(s)$, $k \ge 0$, introduced in (5). We will show that, for arbitrary distribution function $B(t)$ such that $B(0) = 0$, these matrices can be calculated via the matrices $Y_k(s)$ defined by formula (13). Let $n = 0$.

$$\tilde{Y}_0(s) = \int_0^\infty e^{-sx} P(0, x) d\tilde{B}(x) = b_1^{-1} \int_0^\infty e^{(D_0 - sI)x} (1 - B(x)) dx. \quad (14)$$

Using integration by parts, we have

$$\int_0^\infty e^{(D_0 - sI)x} (1 - B(x)) dx = \\ = (D_0 - sI)^{-1} e^{(D_0 - sI)x} (1 - B(x)) \Big|_0^\infty + (D_0 - sI)^{-1} \int_0^\infty e^{(D_0 - sI)x} dB(x).$$

whence it follows that

$$\int_0^\infty e^{(D_0 - sI)x} (1 - B(x)) dx = (D_0 - sI)^{-1} [-I + \int_0^\infty e^{(D_0 - sI)x} dB(x)]. \quad (15)$$

Note that

$$\int_0^\infty e^{(D_0 - sI)x} dB(x) = \int_0^\infty e^{-sx} P(0, x) dB(x) = Y_0(s).$$

Then it follows from (14), (15) that

$$\tilde{Y}_0(s) = b_1^{-1} (D_0 - sI)^{-1} (Y_0(s) - I). \quad (16)$$

Let now $n > 0$. Using integration by parts, we have

$$\int_0^\infty (e^{-sx} P(k, x))'(1 - B(x)) dx = e^{-sx} P(k, x)(1 - B(x)) \Big|_0^\infty + \int_0^\infty e^{-sx} P(k, x) dB(x)$$
whence it follows that

$$Y_k(s) = - \int_0^\infty (e^{-sx} P(k, x))'(1 - B(x)) dx. \qquad (17)$$

Differentiating in (17) and using the formula (9), we get relation

$$Y_k(s) = -s \int_0^\infty e^{-sx} P(k, x)(1 - B(x)) dx + \int_0^\infty e^{-sx} P(k, x) D_0(1 - B(x)) dx + \sum_{l=0}^{k-1} \int_0^\infty e^{-sx} P(l, x) D_{k-l}(1 - B(x)) dx.$$

Using notation, we can rewrite this formula as

$$Y_k(s) = -sb_1 \tilde{Y}_k(s) + b_1 \tilde{Y}_k(s) D_0 + \sum_{l=0}^{k-1} \tilde{Y}_l(s) D_{k-l}.$$

From the last relation we obtain the following recursive formula for calculation of the matrices $\tilde{Y}_k(s)$:

$$\tilde{Y}_k(s) = b_1^{-1} (D_0 - sI)^{-1} (Y_k(s) - \sum_{l=0}^{k-1} \tilde{Y}_l(s) D_{k-l}), \quad k > 0,$$

with boundary condition (16).

# 5 Conclusion

In this paper, we derived the Laplace-Stieltjes transform $w(s)$ of the stationary distribution of the waiting time in the queueing system MAP/G/1/N with LIFO service discipline. Since the waiting time and service time are the independent random variables, the Laplace-Stieltjes transform $v(s)$ of sojourn time in the system can by trivially calculated using the formula $v(s) = w(s)\beta(s)$. Using the formulas for the Laplace-Stieltjes transform, we can calculate the expectation and the higher order moments of the waiting time and the sojourn time in the system.

The results can be used for optimization of resource and buffer space management and admission control in telecommunication networks, e.g., ad hoc networks with finite buffers and in multihop networks with end-to-end deadline-constrained traffic with reliability requirements, and for performance evaluation and capacity planning of various real data structures where the last written data must be processed first.
# 6 Acknowledgments

This publication was financially supported by the Ministry of Education and
Science of the Russian Federation (the Agreement number 02.a03.21.0008)

# References

1. P. Buchholz, J. Kriege, and I. Felko, *Input modeling with phase-type distributions and Markov models: theory and applications*. Berlin-Heidelberg: Springer, 2014.

2. A.N. Dudin, A.A. Shaban, and V.I. Klimenok, "Analysis of a BMAP/G/1/N queue". *International Journal of Simulation: Systems, Science and Technology*, vol. 6, pp. 13-23, 2005.

3. A.N. Dudin, V.I. Klimenok, and G.V. Tsarenkov, "Characteristics calculation for a single server queue with the batch Markovian arrival process, semi-Markovian service and finite buffer." *Automation and Remote Control*, vol. 63, pp. 1285-1297, 2002.

4. A. Dudin, A. Shaban, "Analysis of the BMAP/SM/1/N Type System with Randomized Choice of Customers Admission Discipline". *Communications in Computer and Information Science*, vol. 638, pp. 44-56, 2016.

5. A. Graham, *Kronecker Products and Matrix Calculus with Applications*. Cichester: Ellis Horwood, 1981.

6. C.S. Kim, V. Klimenok, and O. Taramin, "A tandem retrial queueing system with two Markovian flows and reservation of channels". *Computers and Operations Research*, vol. 37, pp. 1238-1246, 2010.

7. R. Li, A. Eryilmaz, "Scheduling for end-to-end deadline-constrained traffic with reliability requirements in multihop networks". *IEEE/ACM Transactions on Networking*, vol. 20, pp. 1649-1662, 2012.

8. D. M. Lucantoni, "New results on the single server queue with a batch Markovian arrival process". *Communications in Statistics-Stochastic Models*, vol. 7, pp. 1-46, 1991.

9. V.F. Matveev, and V.G.Ushakov, *Queueing systems*. The Moscow University Press: Moscow, 1984, (in Russian).

10. M.F. Neuts, *Matrix-geometric solutions in stochastic models*. The Johns Hopkins University Press: Baltimore, 1981.

11. J. Nzouonta, T. Ott, C. Borcea, "Impact of queuing discipline on packet delivery latency in ad hoc networks". *Performance Evaluation*, vol. 66, pp. 667-684, 2009.