=Paper=
{{Paper
|id=Vol-2650/paper42
|storemode=property
|title=Simulation of Finite-Source Retrial Queuing Systems With Collisions, Non-Reliable Server and Impatient Customers in the Orbit
|pdfUrl=https://ceur-ws.org/Vol-2650/paper42.pdf
|volume=Vol-2650
|authors=Ádám Tóth,János Sztrik
|dblpUrl=https://dblp.org/rec/conf/icai3/TothS20
}}
==Simulation of Finite-Source Retrial Queuing Systems With Collisions, Non-Reliable Server and Impatient Customers in the Orbit==
https://ceur-ws.org/Vol-2650/paper42.pdf
Proceedings of the 11th International Conference on Applied Informatics
Eger, Hungary, January 29–31, 2020, published at http://ceur-ws.org
Simulation of Finite-Source Retrial
Queuing Systems With Collisions,
Non-Reliable Server and Impatient
Customers in the Orbit
Ádám Tóth, János Sztrik
Faculty of Informatics
University of Debrecen
Kassai Road 26, Debrecen, 4028, Hungary
toth.adam@inf.unideb.hu
sztrik.janos@inf.unideb.hu
Abstract
The goal of the paper is to study a M/M/1//N finite-source retrial queuing
system with collisions and customers’ impatient behavior in the orbit. The
server is not reliable, breakdown can happen either in busy or in idle states.
The situation when an incoming customer from the orbit or from the source
finds the server busy causes a collision and both requests are directed toward
the orbit (including the customer under service, too). It is assumed that
every request in the source is eligible to generate customers whenever the
server is not working but these requests immediately get into the orbit. A
customer after some waiting for the server to be served can depart from
the orbit without fulfilling its service requirement these are the so-called
impatient customers. In that case it goes back to the source. All random
variables involved in the model construction are supposed to be independent
of each other. The novelty of the investigation is to carry out a sensitivity
analysis comparing various distributions of impatient time of customers on
the performance measures such as mean number of customers in the orbit,
mean waiting time of an arbitrary customer, mean waiting time of customers
who leave the system without service, probability of abandonment, server
utilization, etc. By the use of a self-developed simulation program several
graphical results and comparisons of the investigated systems are illustrated.
Keywords: impatient customer, retrial queueing system, sensitivity analysis,
simulation, non-reliability, collision
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
408
1. Introduction
At present with the rapid increase of traffic growth balks the analysis and optimal
designing of communication systems. With regard to exchanging of information,
a lot of communication process are created by companies from day to day. Con-
sequently, construction of new applicable models of telecommunication systems or
modifying of existing ones are necessary. Queuing systems with repeated calls may
competently describe major telecommunication systems, such as telephone switch-
ing systems, call centers, CSMA-based wireless mesh networks in frame level. Nu-
merous papers and books are devoted to study their importance like [19, 20]. The
main feature of retrial queueing system is that customers remain in the system
even if it is unable to find idle service unit and after some random time it attempts
to reach the service facility again. Impatience of the customers is a natural phe-
nomenon and an interesting topic in queueing theory. The process of reneging and
balking is extensively studied by many researchers for example in [21, 22]. When-
ever an arriving customer decides not to enter the system is called balking while
in reneging a customer in the system 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 facil-
ities are very limited thus users (sources) usually need to fight for these resources.
This results a high possibility of conflict because several sources may launch un-
coordinated attempts producing collisions. In these cases the loss of transmission
takes place and it is necessary to ensure of the process of retransmission. So evolv-
ing efficient procedures for preventing conflict and corresponding message delay is
essential. Some results on retrial queues with collision that have been published in
[1, 2, 3, 4, 5].
In many papers of retrial queueing literature the service unit is assumed to
be available steadily. But these assumptions are quite unrealistic because in real
life applications of these systems can break down, different types of problems can
arise like power outage, human error or other failures. Various factors have effect
on the transmission rate of the wireless channel in a 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 a great importance as the operation of non-reliable
systems modifies system characteristics and performance measures. Finite-source
retrial queues with server breakdowns have been investigated in several papers, for
example in [6, 7, 8], where the MOSEL software package (Modeling, Specification
and Evaluation Language) is used or in [9] where several homogeneous servers were
modeled and analyzed by the help of Generalized Stochastic Petri nets (GSPNs)
using retrial systems. There are other papers which studied a finite-source retrial
queue where the server is subject to breakdowns like [10, 11, 12, 13, 14].
In this paper we study the operation of the system where the service unit is
subject to breakdown and waiting customers can leave the system without spending
time at the service unit. The novelty of this investigation is to carry out sensitivity
409
analysis using assorted distributions of impatience of calls on performance measures
like mean waiting time of an incoming call or total utilization of the server. To
accomplish this goal a simulation program is evolved based on SimPack toolkit [15]
which is a collection of C and C++ libraries. In this several different simulation
algorithms are developed and provide the user with a set of utilities to build a
working simulation from a model description. This is a frame and contains very
basic building blocks, the model and its correct operation was coded by us. With
the help of this program graphical results are given.
2. System model
A retrial queueing system of type M/M/1//N is considered with a non-reliable
server and impatient customers which Figure 1 represents. In the finite-source
𝑁 customers reside and each of them is able to generate calls 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 spend in the orbit without fulfilling its service requirement. Exceeding
this time result that the customer no longer waits for the service unit and departs
without being served properly. This variable follows gamma, hypo-exponential,
hyper-exponential, Pareto and lognormal distribution with different parameters but
with the same mean value. In absence of waiting queue if an incoming customer
finds the server in idle state its service starts immediately. The service times of
the customers is exponentially distributed with parameter 𝜇. After its successfully
service customers return to the source. Encountering the service unit in busy
state the incoming customer remains in the system entering the orbit. After an
exponentially distributed time with parameter 𝜎/𝑁 customers located in the orbit
make an other 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 parameter 𝛾0 in case of a busy server and 𝛾1 when the server
awaits a customer. The repair process starts immediately upon the breakdown
which also follows exponential distribution with parameter 𝛾2 . If server failure
takes place during the service of a customer then it is transferred to the orbit.
All the random variables involved in the model construction are assumed to be
totally independent of each other.
3. Simulation results
Table 1 shows the set of parameters used in simulation. To obtain the desired
performance measures a statistics package is involved in our simulation program,
written by Andrea Francini in [16]. This class applies the method of batch mean to
gather a sequence of independent samples (batch means) by aggregating 𝑛 succes-
sive observations of a steady state simulation. It is one of the easiest and common
technique for establishing a confidence interval for steady state mean of a process.
410
Figure 1: System model
The size of batches should be long enough to guarantee that the sample averages
are approximately independent. Taking the average of the sample averages of each
batch results the final mean value. More detailed information about this tech-
nique see for example [17]. The simulations are performed with the confidence
level of 99.9%. Relative half-width of the confidence interval required to stop the
simulation run is 0.00001.
Our aim is to examine how the different distributions of impatience of calls
have an effect on the performance measure when the mean and variance are equal,
Table 2 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
utilized besides the case when the mean value is constant. Our simulation program
is equipped with random number generators and these functions need input pa-
rameters which are different in every distribution. To achieve valid comparison in
case of every distribution fitting process is needed to be done which can be viewed
in [18].
N 𝜆/𝑁 𝛾0 𝛾1 𝛾2 𝜎/𝑁 𝜇
100 0.01 0.1 0.1 1 0.01 1
Table 1: Numerical values of model parameters
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
Table 2: Parameters of the distribution of impatience of calls
411
Figure 2: Comparison of steady-state distributions
Figure 2 shows the comparison of steady-state distribution of the customers. It
represents the probability of how many customers residing in the system. Taking
a closer look on the results all the curves correspond to normal distribution and
in the following papers the proof of this phenomenon can be found in [23, 24, 25].
However, this figure clearly displays the contrast among the applied distributions.
Although the shape of the curves is almost the same the average number of cus-
tomers in the system varies a little bit especially in case of Pareto distribution and
when the average of impatience of calls is constant the mean is more compared to
the others.
Figure 3: Mean response time vs. arrival intensity using various distributions
The mean response time of a successfully served customer is shown in function
412
of arrival intensity on Figure 3. Under successfully served customer we mean those
customers who leaves the system through the service unit. Interestingly, differences
can be observed even though the first two moments are equal, especially in case
of applying gamma distribution. Results clearly illustrate the effect of various
distributions. Highest values are experienced at gamma distribution. Despite the
increasing arrival intensity the maximum property characteristic of finite-source
retrial queueing systems occurs under suitable parameter settings.
Figure 4: Probability of abandonment of a customer vs. arrival intensity using various
distributions
Figure 4 demonstrate how the probability of abandonment of a customer changes
with the increment of the arrival intensity. Under probability of abandonment we
mean the probability of 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 distributions
of impatience of calls but they differ significantly from each other. At gamma
distribution 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.
The last figure is related to the total utilization of server versus arrival inten-
sity. Total utilization contains every service time including the interrupted ones
no matter whether a call departed from the service unit or from the orbit. By
examining closely the figure we find prominent results when gamma distribution
is applied and regarding the others the received values are almost identical. With
the increment of arrival intensity the total utilization of the service unit increases
as well.
413
Figure 5: Total utilization of server vs. arrival intensity using various distributions
3.1. Different parameter setting
After viewing the above outcomes and figures we are intrigued to know how the
operation of the system changes if another parameter setting is used. To do so we
modify the parameters in order the squared coefficient of variation to be less than
one so hyper-exponential is exchanged for hypo-exponential distribution. Table
3 contains the modified parameter setting of distribution of impatience of calls.
Other parameters remain unchanged (see Table 1).
Distribution Gamma Hypo-exponential Pareto Lognormal
Parameters 𝛼 = 1.47059 𝜇1 = 0.01 𝛼 = 2.5718 𝑚 = 5.9552
𝛽 = 0.002941 𝜇2 = 0.0025 𝑘 = 305.5844 𝜎 = 0.72027
Mean 500
Variance 170000
Squared coefficient of variation 0.68
Table 3: Parameters of impatience of calls
We take over the same performance measures and figures but with the param-
eters of Table 3.
First, Figure 6 represents the steady state distribution. Analyzing the curves in
more detail they are much closer to each other as on Figure 2. Differences appear
among the applied distributions with this parameter setting, too. As regard to the
values with these parameters the mean number of customer is higher in case of
every distribution.
The next figure shows the mean response time of a successfully served customer
in function of arrival intensity. Examining Figure 7 the same tendency can be seen
as on the previous figure but differences can still be discovered especially in case of
gamma distribution. This figure also reveals that customers averagely spend less
time in the system compared to the previous parameter setting.
414
Figure 6: Comparison of steady-state distributions
Figure 7: Mean response time vs. arrival intensity using various distributions
Figure 8 demonstrates the probability of abandonment of a customer versus
arrival intensity. Not surprisingly after seeing the previous two figures the difference
of achieved values are relatively far from each other, disparity is still present among
the applied distributions. It can be stated that with these parameters customers
are more tend to leave the system from the orbit.
Lastly, on Figure 9 the running parameter (value of x-axis) is the arrival in-
tensity and value of y-axis is the total utilization of the server. Among the lines
there are not so significant differences, they coincide with each other meaning that
the utilization is almost the same except in case of Pareto and gamma distribution
where the utilization of service unit is significantly less.
415
Figure 8: Probability of abandonment of a customer vs. arrival intensity using
various distributions
Figure 9: Total utilization of server vs. arrival intensity using various distributions
4. Conclusion
In this paper a finite-source retrial queueing system is presented with a non-reliable
server, collisions and impatient customers. The obtained results fully demonstrated
how pivotal selecting a distribution of impatience of calls because it has a great
influence on the system characteristics despite the fact that the mean and the vari-
ance are exactly the same. Figure in connection with probability of abandonment
clearly assure this phenomenon. Results evidently indicated the distinction is no-
ticeable and significant 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. In the future we would
416
like to deal with more distributions to expand our investigation and examine the
performance measures when the distribution of service time is not exponential. We
also would like to analyze systems of two-way communication in order to carry out
a valid collating.
Acknowledgements. The research work of Ádám Tóth, János Sztrik was sup-
ported 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.
References
[1] Kvach, A., Nazarov, A., Sojourn Time Analysis of Finite Source Markov Re-
trial Queuing System with Collision, In: Dudin A., Nazarov A., Yakupov R. (eds)
Information Technologies and Mathematical Modelling - Queueing Theory and Ap-
plications. ITMM 2015. Communications in Computer and Information Science Vol.
564 (2015), 64–72
[2] Kvach, A., Numerical research of a Markov closed retrial queueing system without
collisions and with the collision of the customers, In: Proceedings of Tomsk State
University. A series of physics and mathematics. Tomsk. Materials of the II All-
Russian Scientific Conference Vol. 295 (2014), 105–112
[3] Kvach, A., Nazarov, A., Numerical research of a closed retrial queueing system
M/GI/1//N with collision of the customers, In: Proceedings of Tomsk State Univer-
sity. A series of physics and mathematics. Tomsk. Materials of the III All-Russian
Scientific Conference Vol. 297 (2015), 65–70
[4] Kvach, A., Nazarov, A., The research of a closed RQ-system M/GI/1//N with
collision of the customers in the condition of an unlimited increasing number of
sources, In: Probability Theory, Random Processes, Mathematical Statistics and Ap-
plications: Materials of the International Scientific Conference Devoted to the 80th
Anniversary of Professor Gennady Medvedev, Doctor of Physical and Mathematical
Sciences (2015), 65–70
[5] Nazarov, A., Kvach, A., Yampolsky, V. Asymptotic Analysis of Closed Markov
Retrial Queuing System with Collision, In: Dudin A., Nazarov A., Yakupov R., Gort-
sev A. (eds) Information Technologies and Mathematical Modelling. ITMM 2014.
Communications in Computer and Information Science Vol. 487 (2014), 334–341
[6] Almási, B., Roszik, J., Sztrik, J. Homogeneous finite-source retrial queues with
server subject to breakdowns and repairs, Mathematical and Computer Modelling
Vol. 42, No. 5–6 (2005), 673–682
[7] Sztrik, J. Tool supported performance modelling of finite-source retrial queues with
breakdowns, Publicationes Mathematicae Vol. 66 (2005), 197–211
[8] Sztrik, J., Almási, B., Roszik, J. Heterogeneous finite-source retrial queues with
server subject to breakdowns and repairs, Journal of Mathematical Sciences Vol. 132
(2006), 677–685
[9] Gharbi, N., Ioualalen, M. GSPN analysis of retrial systems with servers break-
downs and repairs, Applied Mathematics and Computation Vol. 174, No. 2 (2006),
1151–1168
417
[10] Dragieva Velika, I. Number of retrials in a finite source retrial queue with un-
reliable server, Asia-Pacific Journal of Operational Research Vol. 31, No. 2 (2014),
23
[11] Gharbi, N., Nemmouchi, B., Mokdad, L., Ben-Othman, J. The impact of
breakdowns disciplines and repeated attempts on performances of small cell networks,
Journal of Computational Science Vol. 5, No. 4 (2014), 633–644
[12] Krishnamoorthy, A., Pramod, P. K., Chakravarthy, S. R. Queues with in-
terruptions: a survey, TOP Vol. 22, No. 1 (2014), 290–320
[13] Zhang, F., Wang, J. Performance analysis of the retrial queues with finite number
of sources and service interruptions, Journal of the Korean Statistical Society Vol.
42, No. 1 (2013), 117–131
[14] Tóth, Á., Bérczes, T., Sztrik, J., Kvach, A. Simulation of Finite-Source Re-
trial Queueing Systems with Collisions and a Non-reliable Server, In: Vishnevskiy
V., Samouylov K., Kozyrev D. (eds) Distributed Computer and Communication Net-
works. DCCN 2017. Communications in Computer and Information Science Vol. 700
(2017), 146–158
[15] Fishwick, Paul A. SimPack: Getting Started With Simulation Programming In
C And C++, In: Proceedings of the 24th Conference on Winter Simulation (1992),
154–162
[16] Francini, A., Neri, F. SimPack: Getting Started With Simulation Programming
In C And C++, In: Proceedings of MASCOTS ’96 - 4th International Workshop
on Modeling, Analysis and Simulation of Computer and Telecommunication Systems
(1996), 116–122
[17] Chen, E., Kelton, D. A Procedure for Generating Batch-Means Confidence In-
tervals for Simulation: Checking Independence and Normality, Simulation Vol. 83
(1996), 683–694
[18] Sztrik, J., Tóth, Á., Pintér, Á., Bács, Z. Simulation of Finite-Source Retrial
Queues with Two-Way Communications to the Orbit, In: Dudin A., Nazarov A.,
Moiseev A. (eds) Information Technologies and Mathematical Modelling. Queueing
Theory and Applications. ITMM 2019. Communications in Computer and Informa-
tion Science Vol. 1109 (2019), 270–284
[19] Fiems, D., Phung-Duc, D. Light-traffic analysis of random access systems without
collisions, Annals of Operations Research Vol. 277 (2017), 311–327
[20] Artalejo, J. R., Gomez Corral, A. Retrial Queueing Systems: A Computational
Approach, Springer (2008)
[21] Kumar, S., Sharma, S. Transient performance analysis of a single server queuing
model with retention of reneging customers, Yugoslav Journal of Operations Research
Vol. 28, Issue 3 (2018), 315–331
[22] Kim, C. S., Dudin, S., Dudin, A., Samouylov, K. Analysis of a Semi-Open
Queuing Network with a State Dependent Marked Markovian Arrival Process, Cus-
tomers Retrials and Impatience, Mathematics Vol. 7 (2019), 715–734
[23] Nazarov, A., Sztrik, J., Kvach, A.,Tóth, Á. Asymptotic sojourn time analysis
of finite-source M/M/1 retrial queueing system with collisions and server subject to
breakdowns and repairs. Ann Oper Res Vol. 288, (2020), 417–434
418
[24] Nazarov, A., Sztrik, J., Kvach, A., Bérczes, T. Asymptotic analysis of finite-
source M/M/1 retrial queueing system with collisions and server subject to break-
downs and repairs. Ann Oper Res Vol. 277, (2019), 213–229
[25] Sudyko, E., Nazarov, A., Sztrik, J. Asymptotic waiting time analysis of a
finite-source M/M/1 retrial queueing system. Probability in the Engineering and In-
formational Sciences Vol. 33 Issue 3, (2019), 387–403
419