=Paper=
{{Paper
|id=Vol-2874/paper18
|storemode=property
|title=Recent Results on Finite-Source Retrial Queues with Collisions and Impatient Customers in the Orbit
|pdfUrl=https://ceur-ws.org/Vol-2874/paper18.pdf
|volume=Vol-2874
|authors=János Sztrik,Ádám Tóth
}}
==Recent Results on Finite-Source Retrial Queues with Collisions and Impatient Customers in the Orbit==
https://ceur-ws.org/Vol-2874/paper18.pdf
Recent Results on Finite-Source Retrial
Queues with Collisions and Impatient
Customers in the Orbit∗
János Sztrik, Ádám Tóth
University of Debrecen, Faculty of Informatics
sztrik.janos@inf.unideb.hu
toth.adam@inf.unideb.hu
Proceedings of the 1st Conference on Information Technology and Data Science
Debrecen, Hungary, November 6–8, 2020
published at http://ceur-ws.org
Abstract
The goal of the paper is to study a finite-source retrial queuing system
with collisions and customers’ impatient behavior in the orbit. The situation
when an incoming request/call/job/customer either from the orbit or from
the source finds the server busy causes a collision and both requests are
directed toward the orbit. It is assumed that each source can generate request
whenever the server is failed but these requests immediately go into orbit and
it cannot generate a new one until the previous call returns to the source.
A customer after waiting for a few seconds in the orbit can depart without
fulfilling its service requirement these are the so-called impatient customers.
In that case, it returns to the source. The source, service, retrial, impatience,
operation, and repair times are supposed to be independent of each other.
The novelty of the investigation is to carry out a sensitivity analysis com-
paring various distributions of impatience time of customers on the main
performance measures of different type of customers, probability of abandon-
ment, total server utilization, etc.
Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
∗ The research of both authors was supported by the construction EFOP-3.6.3-VEKOP-16-
2017-00002. The project was supported by the European Union, co-financed by the European
Social Fund.
196
Keywords: Finite-source queuing system, retrial queues, collisions, server
breakdowns, and repairs, impatient customers, analytic results, algorithmic
approach, stochastic simulation, asymptotic analysis
AMS Subject Classification: 60K25, 68M20, 90B22
1. Introduction
Queuing systems with repeated calls may competently describe major telecommu-
nication systems, such as telephone switching systems, call centers, CSMA-based
wireless mesh networks in frame level. The main feature of the retrial queueing
system is that customers remain in the system even if it is unable to find an idle
service unit and after some random time it attempts to reach the service facility
again. Customers’ impatience is a natural phenomenon and an interesting topic in
queueing theory. The process of reneging and balking has been extensively studied
by many researchers during the last years. For example in [1–3] the generating
function approach has been used, while in [4, 5] the authors investigated the sys-
tems with the help of an asymptotic method when the impatience rate tends to
zero. In [6] a numerical approach has been used, the paper [7] is one of the earlier
works dealing with reneging. In papers [8–10, 12, 13] again the generating function
approach has been applied for infinite source systems with different fields of appli-
cations. In [18] the transient solution of the main performance measures has been
obtained, and finally in [21] a matrix-exponential method resulting a numerical
solution has been treated. Whenever an arriving customer decides not to enter the
system, which is called balking, while reneging means that a customer after waiting
for some time leaves the system without being served. In our investigated model
reneging customers are considered. Speaking of communication systems where the
available channels or other facilities are very limited thus users/sources usually need
to fight for these resources. This results in a high possibility of conflict because
several users may launch uncoordinated attempts producing collisions. In these
cases the loss of transmission takes place and it is necessary to ensure the process
of retransmission. So evolving efficient procedures for preventing conflict and cor-
responding message delay is essential. In case of a collision both requests, the one
under service and the newly arriving one go to orbit. A review of results on finite-
source retrial queues with collision and an unreliable server has been published in
[16]. In many papers of retrial queueing literature, the service unit is assumed
to be available all the time. But these assumptions are quite unrealistic because
in real-life applications of these systems the server can break down, for example
a power outage, human error, or other type of failures. Various factors have an
effect on the transmission rate of the wireless channel in a wireless communication
scenario and these are apt to suffer transmission failure, interruptions throughout
transferring the packets. Investigating retrial queueing systems with random server
breakdowns and repairs has great importance as the operation of non-reliable sys-
tems modifies system characteristics and performance measures. In this paper, we
assume that in the case of a failure of the server, the request generation from the
197
source continues, and calls go to orbit.
The novelty of this investigation is to carry out sensitivity analysis using dif-
ferent distributions of impatient customers on the performance measures. Various
figures help us to understand the special features of the system. The model is a
generalization of [19] and a continuation of the works [11, 20].
The present paper aims to show some recent results on single server finite-
source retrial queuing systems with impatient customers in the orbit. There are
investigations when the server is reliable and there are models when the server is
subject to random breakdowns and repairs depending on whether it is idle or busy.
Tool supported, numerical, and simulation methods are considered. Several cases
and examples are treated and the results of different approaches are compared to
each other showing the advantages and disadvantages of the given method. In
general, we could see that the steady-state distribution of the number of customers
in the service facility can be approximated by a normal distribution with a given
mean and variance. With the help of stochastic simulation, several systems are
analyzed showing directions for further analytic investigations. Tables and Figures
are collected to illustrate some special features of these systems.
2. System Model
A retrial queueing system of type 𝑀/𝑀/1//𝑁 is considered with a non-reliable
server and impatient customers which Figure 1 represents. In the finite-source 𝑁
Figure 1. Operational scheme of the system.
each of them can generate request towards the server with rate 𝜆/𝑁 so the inter-
request time is exponential with parameter 𝜆/𝑁 . Every incoming customer has
an ‘impatience’ property which determines how much time the customer spends in
the orbit without fulfilling its service requirement. Exceeding this time results that
the customer no longer waits for the service unit and departs without being served
properly. This variable follows exponential with parameter 𝜏 , hypo-exponential,
hyper-exponential, gamma, Pareto, and lognormal distribution with different pa-
rameters but with the same mean value. In absence of a waiting queue if an
198
incoming customer finds the server in idle state its service starts immediately. The
service times of the customers are exponentially distributed with parameter 𝜇. Af-
ter it’s successful service customers return to the source. Encountering the service
unit in a busy state the incoming customer causes a collision with the call under
service and both enter the orbit. After an exponentially distributed time with pa-
rameter 𝜎/𝑁 customers located in the orbit make another attempt to get into the
service. The server is not reliable so from time to time it is supposed to break
down. This is an exponentially distributed random variable with the parameter 𝛾0
in case of an idle server and 𝛾1 when the server is busy. The repair process starts
immediately upon the breakdown which also follows an exponential distribution
with parameter 𝛾2 . If server failure takes place during the service of a customer
then it is transferred to the orbit. Furthermore, in the case of a failure we can
distinguish two options. Namely, the failure either stops entering new customers
from the source or allows them to go to the orbit. Usually, we treat system with
the latter option if the other one is not stated.
The source, service, retrial, impatience, operation, and repair times are sup-
posed to be independent of each other.
3. Tool Supported Results
In this section, we show the results generated by MOSEL (MOdeling, Specification
and Evaluation Language), published in [11]. We must remark that in this case
all the above mentioned random variables are exponentially distributed. However,
it should be pointed out that in this case only the performance measures of an
Figure 2. Comparisons of different MOSEL results.
199
arbitrary customer and the probability of abandonment can be obtained. One of
the advantages of the simulation that we can make difference between abandoned
and successfully served requests, we can estimate the performance measures, re-
spectively, see Figure 2.
Table 1. Numerical values of input parameters.
N 𝜆/𝑁 𝛾0 𝛾1 𝛾2 𝜎/𝑁 𝜇 𝜏
100 0.01 0.1 0.1 1 0.05 1 0.001
4. Simulation Results
The simulation approach is a very important method that helps us in performance
modeling when the system is too complicated to investigate with the help of other
standard methods, like analytical, numerical, or asymptotic ones. For the interested
readers we list some of the most important works dealing with stochastic simulation
and statistical investigations of output data [14, 15, 17].
In this section first, we deal with exponentially distributed impatience time
which helps us to check our simulation results with the help of those we got using
MOSEL. As soon as we realized that the simulation program runs correctly we
can investigate the effect of the distribution of impatience time on the performance
measures as we will do in the second part. One of the advantages of the simulation is
that we can make a difference between abandoned and successfully served requests
as we show it in the second part.
4.1. Exponentially Distributed Impatience Times
In these cases, we would like to show the effect of the impatience rate 𝜏 on the
distribution of the number of customers in the system. All the random variables
mentioned above are supposed to be exponentially distributed.
Table 2. Different impatience rates.
N 𝜆/𝑁 𝜎/𝑁 𝛾0 𝛾1 𝛾2 𝜇 𝜏
Case 1 100 0.01 0.1 0.1 0.1 1 1 1E-10
Case 2 100 0.01 0.1 0.1 0.1 1 1 0.000001
Case 3 100 0.01 0.1 0.1 0.1 1 1 0.0001
Case 4 100 0.01 0.1 0.1 0.1 1 1 0.001
Case 5 100 0.01 0.1 0.1 0.1 1 1 0.01
Case 6 100 0.01 0.1 0.1 0.1 1 1 0.1
Case 7 100 0.01 0.1 0.1 0.1 1 1 1
Case 8 100 0.01 0.1 0.1 0.1 1 1 5
200
The results are understandable and illustrate what we expected, namely, the
higher the impatience rate is the fewer the number of customers is in the system
see Figure 3.
Figure 3. Distribution of number of customers for different impa-
tience rates.
4.2. Generally Distributed Impatience Times
We aim to examine how the different distributions of impatience of customers affect
the performance measure when the mean and variance are equal, respectively. The
investigations are divided into two parts depending on the squared coefficient of
variation.
Squared Coefficient of Variation is Greater than One
In the first part, Table 4 shows the parameters of distinct distributions. The
parameters are chosen in such a way that the squared coefficient of variation would
be greater than one. For comparison hyper-exponential, gamma, lognormal and
Pareto distributions are used besides the case when the impatience time is constant.
Our simulation program is equipped with random number generators and these
functions need input parameters that are different in each distribution.
Table 3. Numerical values of model parameters.
𝑁 𝜆/𝑁 𝛾0 𝛾1 𝛾2 𝜎/𝑁 𝜇
100 0.01 0.1 0.1 1 0.01 1
Figure 4 shows the comparison of steady-state distribution of the number of cus-
tomers in the system. Taking a closer look at the results all the curves correspond
to a normal distribution, the explanation can be found in paper [16]. However, this
figure displays the contrast among the applied distributions. Although the shape of
the curves is almost the same the average number of customers in the system varies
a little bit especially in the case of Pareto distribution and when the impatience
time of calls is constant the mean is greater compared to the others.
201
Table 4. Parameters of impatience distributions, squared coeffi-
cient of variation is greater than one.
Distribution Gamma Hyper-exponential Pareto Lognormal
Parameters 𝛼 = 0.390625 𝑝 = 0.33098 𝛼 = 2.1792 𝑚 = 5.57973
𝛽 = 0.0007813 𝜆1 = 0.00132 𝑘 = 270.56302 𝜎 = 1.12684
𝜆2 = 0.00268
Mean 500
Variance 640000
Squared coefficient of variation 2.56
Figure 4. Comparison of steady-state distributions.
The mean response time of different types of customer is shown in function of
arrival intensity on Figures 5, 6, 7. Figure 6 illustrates how the mean response
time of impatient customers changes. The mean waiting time in the orbit should
be constant, due to the constant impatient time of a customer. Of course, Figure 7
can be obtained with the help of the law of total expectation, too. Interestingly,
differences can be observed even though the first two moments are equal, respec-
tively. Results clearly illustrate the effect of various distributions. The highest
values are experienced at gamma distribution in the case of successful customers,
but in the case of impatient calls, constant impatience time gives the greatest val-
ues. Despite the increasing arrival intensity, the maximum property characteristic
of finite-source retrial queueing systems occurs under suitable parameter settings
as we mentioned in [16].
Figure 8 demonstrates how the probability of abandonment of a customer
changes with the increment of the arrival intensity. By probability of abandon-
ment we mean the probability that a customer leaves the system without getting
its full-service requirement (through the orbit). After a slow increase of the value
of this performance measure, it stagnates which is true for every used distribution
of impatience of calls but they differ significantly from each other. At gamma dis-
tribution, the tendency of leaving the system earlier is much higher than the others
especially compared to at constant mean of impatience of calls. Here the disparity
is much higher among the applied distributions compared to the previous Figures.
202
Figure 5. Mean response time vs. arrival intensity using various
distributions.
Figure 6. Mean response time vs. arrival intensity using various
distributions.
Figure 7. Mean response time vs. arrival intensity using various
distributions.
203
An explanation of this feature could be the following: if the squared coefficient of
variation is greater than one the gamma distribution takes small values with great
probability, so the customers leave the system quite early, and thus the probability
of abandonment is high.
Figure 8. Probability of abandonment of a customer vs. arrival
intensity using various distributions.
Figure 9 is related to the total utilization of server versus arrival intensity. To-
tal utilization contains every service time including the interrupted ones no matter
whether a call departed from the service unit or the orbit. By examining closely
the Figure we find prominent results when gamma distribution is applied and re-
garding the others, the received values are almost identical. With the increment of
arrival intensity, the total utilization of the service unit increases as well. Here the
explanation is the same as in the previous Figure, that is there are fewer customers
in the system and hence the utilization is the smallest.
Figure 9. Total utilization of server vs. arrival intensity using
various distributions.
We carried the simulation in the case when the squared coefficient of variation
is less than one, the mean is the same as before. The differences are noticeable but
not as big as in the previous cases, see [20].
204
5. Conclusion
In this paper, a finite-source retrial queueing system was presented with a non-
reliable server, collisions, and impatient customers in the orbit. The obtained
results fully demonstrated that the distribution of impatience of customers has a
great influence on the system’s characteristics even though the mean and the vari-
ance are the same. Figures in connection with the probability of abandonment
assure this phenomenon. Results indicated the distinction is noticeable and sig-
nificant among the performance measures having the same mean and variance of
different distributions when the squared coefficient of variation is greater than one
and moderate when it is less than one.
Acknowledgment. The authors are very grateful to the reviewers for their com-
ments, which improved the quality and the presentation of the paper.
References
[1] I. Adan, B. Hathaway, V. Kulkarni: On first-come, first-served queues with two classes
of impatient customers, Queueing Systems 91.1–2 (2019), pp. 113–142.
[2] A. Aissani, F. Lounis, D. Hamadouche, S. Taleb: Analysis of Customers’ Impatience
in a Repairable Retrial Queue under Postponed Preventive Actions, American Journal of
Mathematical and Management Sciences 38.2 (2019), pp. 125–150.
[3] J. R. Artalejo, V. Pla: On the impact of customer balking, impatience and retrials
in telecommunication systems, Computers & Mathematics with Applications 57.2 (2009),
pp. 217–229.
[4] E. Danilyuk, S. Moiseeva, A. Nazarov: Asymptotic Analysis of Retrial Queueing System
𝑀/𝐺𝐼/1 with Collisions and Impatient Calls, in: International Conference on Information
Technologies and Mathematical Modelling, Springer, 2019, pp. 230–242.
[5] E. Danilyuk, S. Moiseeva, J. Sztrik: Asymptotic Analysis of Retrial Queueing System
𝑀/𝑀/1 with Impatient Customers, Collisions and Unreliable Server, Journal of Siberian
Federal University, Mathematics & Physics 13.2 (2020), pp. 218–230.
[6] A. Dudin: Operations Research Perspectives, Operations Research 5 (2018), pp. 245–255.
[7] F. A. Haight: Queueing with reneging, Metrika 2.1 (1959), pp. 186–197.
[8] M. Jain, S. Rani: Markovian Model of Unreliable Server Retrial Queue with Discourage-
ment, Proceedings of the National Academy of Sciences, India Section A: Physical Sciences
(2020), pp. 1–8.
[9] C. Kim, A. Dudin, O. Dudina, V. Klimenok: Analysis of Queueing System with Non-
Preemptive Time Limited Service and Impatient Customers, Methodology and Computing
in Applied Probability (2019), pp. 1–32.
[10] J. S. Kim: Retrial queueing system with collision and impatience, Communications of the
Korean Mathematical Society 25.4 (2010), pp. 647–653.
[11] A. Kuki, T. Bérczes, Á. Tóth, J. Sztrik: Numerical analysis of finite source Markov
retrial system with non-reliable server, collision, and impatient customers, in: Annales Math-
ematicae et Informaticae, vol. 51, Liceum University Press, 2020, pp. 53–63.
[12] R. Kumar, B. K. Som: A multi-server queue with reverse balking and impatient customers,
Pak. J. Statist 36.2 (2020), pp. 91–101.
205
[13] L. Lakaour, D. Aissani, K. Aissanou, K. Barkaoui: 𝑀/𝑀/1 Retrial Queue with Colli-
sions and Transmission Errors, Methodology and Computing in Applied Probability (2018),
pp. 1–12.
[14] A. M. Law: Statistical analysis of simulation output data: the practical state of the art, in:
Proceedings of the 2015 Winter Simulation Conference, IEEE Press, 2015, pp. 1810–1819.
[15] A. M. Law, W. D. Kelton: Simulation modeling and analysis, McGraw-Hill New York,
1991.
[16] A. Nazarov, J. Sztrik, A. Kvach: A survey of recent results in finite-source retrial queues
with collisions, in: Information Technologies and Mathematical Modelling. Queueing Theory
and Applications, Springer, 2018, pp. 1–15.
[17] R. Y. Rubinstein, D. P. Kroese: Simulation and the Monte Carlo method, John Wiley
& Sons, 2016.
[18] Y. Satin, A. Zeifman, A. Sipin, S. Ammar, J. Sztrik: On Probability Characteristics for
a Class of Queueing Models with Impatient Customers, Mathematics 8.4 (2020), p. 594.
[19] Á. Tóth, T. Bérczes, J. Sztrik, A. Kvach: Simulation of finite-source retrial queueing
systems with collisions and non-reliable server, in: International Conference on Distributed
Computer and Communication Networks, Springer, 2017, pp. 146–158.
[20] Á. Tóth, J. Sztrik: Simulation of Finite-Source Retrial Queuing Systems With Collisions,
Non-Reliable Server and Impatient Customers in the Orbit, Proceedings of 11th International
Conference on Applied Informatics, Eger, Hungary (2020), CEUR Workshop Proceedings
(CEUR-WS.org) 2650 (2020), pp. 408–419,
url: http://ceur-ws.org/Vol-2650/.
[21] H. Wu, Q. M. He: Double-sided queues with marked Markovian arrival processes and
abandonment, Stochastic Models (2020), pp. 1–36.
206