# Multiline queueing system with random time limitations and limited buffer space

### Oleg Tikhonenko

,### Paweł Zając

Journal of Applied Mathematics and Computational Mechanics |
Download Full Text |

MULTILINE QUEUEING SYSTEM WITH RANDOM TIME LIMITATIONS AND LIMITED BUFFER SPACE

Oleg Tikhonenko^{1}, Paweł Zając^{2}

^{1}
Faculty of Mathematics and Natural Sciences, College of Sciences

Cardinal Stefan Wyszyński University in Warsaw

Warsaw, Poland

^{2} Institute of Mathematics, Czestochowa University of Technology

Częstochowa, Poland

o.tikhonenko@uksw.edu.pl, pawel_zajac@vp.pl

Received: 3 April 2018; Accepted: 17 January 2019

**Abstract.** In the paper, we investigate multi-server queueing systems with
demands of random space requirements (volumes), in which buffer space is
limited by constant value and queueing ore (and) service time are limited by
exponentially distributed random variables. For such systems, stationary
demands number distribution and loss probability are determined. Some numerical
results are attached as well.

*MSC 2010:**90B22, 60K25, 68M20*

*Keywords: **total demands volume, system buffer capacity, loss probability,
Stieltjes
convolution*

1. Introduction

Queueing systems with demands of a random space requirement (or random volume) [1, 2] are the generalization of the classical queueing models [3, 4]. They can be used to model and solve various practical problems in the design of computer and communication systems (see e.g. [1, 2, 5]). In particular, such models can be applied to buffer space volume determination in the nodes of computer and communication networks. The main proposition of the theory of such systems [1] is the heterogeneity of demands served by the system with respect to their random volumes, in other words, we propose that different demands need different memory size (volume) during their presence in the system.

In the paper, we investigate queueing systems in which demands are also “impatient”, i.e. they can leave the system during their waiting in the queue or (and) during their servicing. In the classical queueing theory (for demands without random volume), systems with times limitations were investigated e.g. in [4, 6]. In particular, in [6] queueing systems with random limitations of queueing and (or) service time were investigated. In the paper [7], the system with random volume demands, deterministically limited total demands volume and deterministically limited queueing or sojourn time were analyzed.

In this paper, we investigate a similar system, but the difference is that, in the system under consideration, queueing and (or) service time are limited by exponen- tially distributed random variables. For example, we have a situation when a demand contains some information that can be grown old fore random reasons, and therefore it must be eliminated from the system.

The paper is organized as follows: In the Section 2, we give the mathematical description of the model and introduce some necessary notations. In Section 3, we introduce the functions describing the system behavior and define an appropriate Markov process. In Section 4, we build a system of differential equations for the function introduced in Section 3 and give its steady-state solution, from which the steady-state demands number distribution is determined. In Section 5, we determine the loss probability for the system under consideration. Section 6 contains examples of numerical results illustrating theoretical formulas, and the last Section 7 presents conclusions and final remarks.

2. Model description

We consider a queueing system of *M*/*M*/*n*/*m*-type, in which all demands
are characterized by some random
volume (or space requirement) , where is
a non-negative random variable that doesn’t depend on
the volumes of other
demands and the epoch of the demand’s entering to the system. Denote by the distribution function of
the random variable Let be the total
demands volume or the sum of all volumes of demands present in the system at time instant *t*. The values of the
random process are bounded by the con-
stant value *V *() named the system buffer capacity. Let be the number of demands present in the system at time instant *t*.

If a demand of volume *x *arrives to the
system at epoch *t* when there are other demands in it and we have and the demand is accepted to
the system. In opposite case (), the demand will be lost without
influence to future system behavior. In this case, we have The arriving demand will be lost also if
there are other demands at the epoch t.

Demands accepting to the system are served in accordance to FIFO discipline. But their queueing time and (or) sojourn time are limited by some random variables having an exponential distributions with parameters and respectively, i.e. demands can leave the system (be lost) during waiting in the queue or servic- ing. In particular, if only queueing time is limited in the system, we have if only service time is limited, we have and if sojourn time is limited in the system, we obtain Let a be the parameter of demands enter flow, be the parameter of service time (we assume that service time doesn’t depend on the demand volume). We also assume that the traffic load of the system is finite ().

Our aim is the determination of the steady-state distribution of number of demands present in the system and the demand loss probability.

3. Process and characteristics

The behavior of the system under consideration can be described by the following Markov random process

(1) |

where** **** **is the
volume of the *j***-**th demand presenting in the system at time
instant *t*. It is clear that

The process (1) we shall characterize by the functions having the following probability sense:

(2) |

(3) |

(4) |

It is clear that, for we have

4. Steady-state distribution of demands present in the system

It can be easily shown that the functions (2)-(4) satisfy the following Kolmogorov-type equations (see also [8] for comparison):

(5) |

(6) |

(7) |

(8) |

(9) |

Assume that at
least one of the values *m *and *V *is finite. Then, we have obviously that when in
the sense of a weak convergence, where the random variables and are the steady-state number of demands present
in the system and their total volume, consequently. So, the following
finite limits exist:

(10) |

(11) |

We have evidently for

It follows from the equations (5)-(9) that the steady-state characteristics (10) and (11) satisfy the following equations:

(12) |

(13) |

(14) |

(15) |

(16) |

Introduce the following notation for the Stieltjes convolution of the distribution function : .

Then, by direct substitution, we can easily show that the solution of the Eqs. (12)-(16) has the form:

(17) |

where

We have from the relations (17) that

| (18) |

The probability can be determined from the normalization condition whereas we obtain:

5. Loss probability

Let *A *be the event that an arbitrary
arriving demand is accepted to the system
and served completely and *K *be the mean number
of busy servers in steady state. We have evidently that and
we obtain for probability of the event *A*: Then,
the probability that an arbitrary demand is lost at its arriving epoch or is
not served completely can be determined as

6. Numerical examples

In this section, we present numerical
examples illustrating theoretical results. More precisely, we present how the
loss probability depends on the buffer
capacity *V *and the parameters Assume that the
volumes of entering
demands are exponentially distributed with parameter and
service time has
an exponential distribution with parameter Consider
three cases of the considered system when (a
single-server system).

Fig. 1. Loss probability, , Fig. 2. Loss probability, , ,

Fig. 3. Loss probability, , Fig. 4. Loss probability, , ,

Fig. 5. Loss probability, , Fig. 6. Loss probability, , ,

In the first case (Figs. 1 and 2), only
the queueing time is limited, i.e. we have Assume
that the system buffer capacity *V *takes the values from 0 to 10,
and the parameter takes the values from 0 to 2.
Furthermore, when and ,
then and . For
example, if there is one waiting place in the queue (),
then, for and the
loss probability is equal to 0.68765 (Fig. 1).
If , then (Fig.
2).

In the second case, only service time is
limited (Figs. 3 and 4), then we have Assume
that the system buffer capacity *V *takes the values from 0 to 5, and the
parameter takes the values from 0 to 2.
Furthermore, when and ,
then and . For example, if the queue size is 1 (), for and *V* = 1,
the loss probability 0.898072 (Fig. 3).
If , then we have 0.8985
(see Fig. 4).

In the third case, the sojourn time of demand
in the system is limited, then we assume (Figs. 5
and 6). Assume that *V *takes the values from 0 to 5 and takes values from 0 to 2.
In addition, when and ,
we have and . For
example, if there is one waiting place
in the queue (), for and
we have 0.898516
(Fig. 5).
If , then 0.898603
(Fig. 6).

7. Conclusions

In the paper, we consider a multiline queueing system with random time limitations and limited buffer space. The determination of the steady-state distribution of number of demands present in the system and the demand loss probability are presented. Some special cases of the system under consideration are provided with numerical calculations in Maple. In any case, when the number of waiting places increases, of course the loss probability of demand also increases. This model shows the loss probability of demand (see Figs. 1-6). The results obtained in the paper can be used for estimating of total demands volume characteristics in the nodes of computer and telecommunication networks.

References

[1]
Tikhonenko, O. (2006). *Probability Methods of
Information System Analysis*. Warsaw: Akade-micka Oficyna Wydawnicza EXIT
(in Polish).

[2]
Tikhonenko, O.M. (1990). *Queueing Models in
Information Systems* (*Modeli massovogo obsluzhivanija v sistemah
obrabotki informacii*). Minsk: Universitrtskoe (in Russian).

[3]
Bocharov, P.P., D’Apice, C., Pechinkin, A.V.,
& Salerno, S. (2004). *Queueing Theory*. Utrecht-
-Boston: VSP.

[4]
Gnedenko, B.V., & Kovalenko, I.N. (1989). *Introduction
to Queueing Theory*. Boston: Birkhäuser.

[5]
Naumov, V.A., & Samouylov, K.E. (2016). On
relationship between queueing systems with
resources and Erlang networks. *Informatics and Applications *(*Informatika
i ee Primeneniya*),
*10*, 3, 9-14 (in Russian).

[6]
Ovcharov, L.A. (1969). *Applied Queueing
Theory* (*Prikladnye zadachi teorii massovogo obsluzhivanija*). Moscow:
Mashinostrojenie (in Russian).

[7]
Tikhonenko, O., & Zając, P. (2017). Queueing
systems with demands of random space requirement and limited queueing or
sojourn time. *Communications in Computer and Information
Science*, *718*, 380-391.

[8]
Alexandrov, A.M., & Kaz, B.A. (1973).
Non-homogeneous demands flows service. Izvestiya
AN SSSR. *Tekhnicheskaya Kibernetika*, *2*, 47-53 (in Russian).