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