A retrial queueing system with processor sharing and impatient customers

Objectives. The problem of constructing and investigating a mathematical model of a stochastic system with processor sharing, repeated calls, and customer impatience is considered. This system is formalized in the form of a queueing system. The operation of the queue is described in terms of multi-dimensional Markov chain. A condition for the existence of a stationary distribution is found, and algorithms for calculating the stationary distribution and stationary performance characteristics of the system are proposed.

Methods. Methods of probability theory, queueing theory and matrix theory are used.

Results. The steady state operation of a queueing system with repeated calls, processor sharing and two types of customers arriving in a marked Markovian arrival process is studied. The channel bandwidth is divided between two types of customers in a certain proportion, and the number of customers of each type simultaneously located on the server is limited. Customers of one of the types that have made all the channels assigned to them busy leave the system unserved with some probability and, with an additional probability, go to the orbit of infinite size, from where they make attempts to get service at random time intervals. Customers of the second type, which caused all the channels assigned to them to be busy, are lost. Customers in orbit show impatience: each of them can leave orbit forever if the time of its stay in orbit exceeds some random time distributed according to an exponential law. Service times of customers of different types are distributed according to the phase law with different parameters. The operation of the system is described in terms of a multi-dimensional Markov chain. It is proved that for any values of the system parameters this chain has a stationary distribution. Algorithms for calculating the stationary distribution and a number of performance measures of the system are proposed. The results of the study can be used to simulate the operation of a fixed capacity cell in a wireless cellular communication network and other real systems operating in the processor sharing mode.

1. Ghosh A., Banik A. D. An algorithmic analysis of the / /1 generalized processor-sharing queue. Computers and Operations Research, 2017, vol. 79, pp. 1–11.

2. Telek M., van Houdt B. Response time distribution of a class of limited processor sharing queues. Performance Evaluation Review, 2018, vol. 45, no. 3, pp. 143–155. https://doi.org/10.1145/3199524.3199548

3. Yashkov S., Yashkova A. Processor sharing: a survey of the mathematical theory. Automation and Remote Control, 2007, vol. 68, pp. 662–731.

4. Zhen Q., Knessl C. On sojourn times in the finite capacity / /1 queue with processor sharing. Operations Research Letters, 2009, vol. 37, pp. 447–450.

5. Masuyama H., Takine T. Sojourn time distribution in a / /1 processor-sharing queue. Operations Research Letters, 2003, vol. 31, pp. 406–412.

6. Dudin S., Dudin A., Dudina O., Samouylov K. Analysis of a retrial queue with limited processor sharing operating in the random environment. Lecture Notes in Computer Science, 2017, vol. 10372, pp. 38–49.

7. Dudin A., Dudin S., Dudina O., Samouylov K. Analysis of queuing model with limited processor sharing discipline and customers impatience. Operations Research Perspectives, 2018, vol. 5, pp. 245–255.

8. Klimenok V., Dudin A. A retrial queueing system with processor sharing. Communications in Computer and Information Science, 2021, vol. 1391, pp. 46–60.

9. He Q. M. Queues with marked customers. Advances in Applied Probability, 1996, vol. 28, pp. 567–587.

10. Dudin A. N., Klimenok V. I., Vishnevsky V. M. The Theory of Queuing Systems with Correlated Flows. Springer, 2020, 410 p.

11. Neuts M. F. Matrix-Geometric Solutions in Stochastic Models. Baltimore, the Johns Hopkins University Press, 1981, 352 p.

12. Graham A. Kronecker Products and Matrix Calculus with Applications. Cichester, Ellis Horwood, 1981, 130 p.

13. Ramaswami V. Independent Markov processes in parallel. Communications in Statistics. Stochastic Models, 1985, vol. 1, pp. 419–432.

14. Ramaswami V., Lucantoni D. M. Algorithms for the multi-server queue with phase-type service. Communications in Statistics. Stochastic Models, 1985, vol. 1, pp. 393–417.

15. Dudina O., Kim C. S., Dudin S. Retrial queueing system with Markovian arrival flow and phase type service time distribution. Computers and Industrial Engineering, 2013, vol. 66, pp. 360–373.

16. Klimenok, V. I., Dudin A. N. Multi-dimensional asymptotically quasi-Toeplitz Markov chains and their application in queueing theory. Queueing Systems, 2006, vol. 54, pp. 245–259.