Hidden Markov model of a GI/G/2/0 queuing system with losses

Semi-Markov processes are widely used to model queuing systems. The relevance of the study is due to the increase in the capabilities for analysis and performance of queuing systems for which semi-Markov models are constructed. The application of the hidden Markov model theory to them also underscores the importance of this research. In this regard, this article discusses the application of the apparatus of the hidden Markov models theory to a lossy queuing system described by a semi-Markov process with a general phase state space. This makes it possible not only to move beyond the exponential law of the distribution of service times and the flow of applications when describing the system, but also to solve the problems of forecasting and evaluating states and signals, correcting the model while the system is in operation. For transition to a discrete set of states of the Semi-Markov model, the algorithm of stationary phase enlargement is employed. As an illustrative example, a merged semi-Markov model of the GI/G/2/0 queuing system with losses is constructed. Based on it, a hidden Markov model is developed for which the problems of analyzing dynamics and predicting states are solved. The parameters of the hidden Markov model are refined by means of the Baum-Welsh algorithm; the most probable sequence of changing states of the system is determined by the received signal vector.

1. 1. Rykov V. Controllable queueing systems: from the very beginning up to nowadays. Reliability: Theory & Applications. 2017;12(2):39–61.

2. 2. Medhi J. Stochastic Models in Queueing Theory 2nd edition. United Kingdom, Academic Press; 2002. 504 p.

3. 3. Peschansky A.I. Semi-Markov models of one-server loss queues with recurrent input. Chisinau, Lambert Academic Publishing; 2013. 144 p.

4. 4. Korlat A.N., Kuznetsov V.N., Novikov M.M., Turbin A.F. Polumarkovskie modeli vosstanavlivaemykh sistem i sistem massovogo obsluzhivaniya. Chisinau, Shtiintsa; 1991. 275 p. (In Russ.).

5. 5. Korolyuk V.S., Turbin A.F. Protsessy markovskogo vosstanovleniya v zadachakh nadezhnosti sistem. Kiev, Nauk. dumka; 1982. 236 p. (In Russ.).

6. 6. Korolyuk V.S., Korolyuk V.V. Stochastic Models of Systems. Dordrecht, Springer Science+Business Media; 1999. 185 p.

7. 7. Grabski F. Semi-Markov Processes: Applications in System Reliability and Maintenance. Amsterdam, Elsevier Science; 2014. 270 p.

8. 8. Obzherin Yu.E., Boyko E.G. Semi-Markov Models: Control of Restorable Systems with Latent Failures. London, Elsevier Academic Press; 2015. 212 p.

9. 9. Obzherin Y.E., Sidorov S.M. Semi-Markov model and phase-merging scheme of a multi-component system with the group instantly replenished time reserve. International Journal of Reliability, Quality and Safety Engineering. 2019;26(3):1950014. DOI:10.1142/S0218539319500141.

10. 10. Ross S.M. Introduction to Probability Models. 9th ed. USA, Elsevier Academic Press; 2006. 800 p.

11. 11. Rabiner L.R. A Tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE. 1989;77(2):257–286. DOI: 10.1109/5.18626.

12. 12. Kobayashi H., Mark B., Turin W. Probability, Random Processes, and Statistical Analysis: Applications to Communications, Signal Processing, Queueing Theory and Mathematical Finance. Cambridge, Cambridge University Press; 2011. 812 p.

13. 13. Obzherin Y. Semi-Markovian model of two-line queuing system with losses. Intelligent Information Management. 2016;8(2):17–26. DOI: 10.4236/iim.2016.82003.

14. 14. Isguder H.O., Uzunoglu-Kocer U., Celikoglu C.C. Generalization of the Takacs’ formula for GI/M/n/0 queuing system with heterogeneous servers. Lecture Notes in Engineering and Computer Science: Proceedings of The World Congress on Engineering. 2011;1:45–47.

15. 15. Isguder H.O., Uzunoglu-Kocer U. Analysis of GI/M/n/n queueing system with ordered entry and no waiting line. Applied Mathematical Modelling. 2014;38(3):1024–1032. DOI: 10.1016/j.apm.2013.07.029.

16. 16. Obzherin Y.E., Sidorov S.M., Nikitin M.M. Hidden Markov model of information system with component-wise storage devices. In: Vishnevskiy V., Samouylov K., Kozyrev D. (eds) Distributed Computer and Communication Networks. Lecture Notes in Computer Science. 2019;11965:354–364. DOI: 10.1007/978-3-030-36614-8_27.

17. 17. Tanackov I., Prentkovskis O., Jevtić Ž., Stojić G., Ercegovac P. A new method for Markovian adaptation of the non-Markovian queueing system using the hidden Markov model. Algorithms. 2019;12(7):133. DOI: 10.3390/a12070133.

18. 18. Obzherin Y.E., Skatkov A.V. Semi-markov model of a queuing system with losses. J Math Sci. 1993;65:1672–1677. DOI: 10.1007/BF01097518.

19. 19. Peschansky A.I., Kovalenko A.I. Semi-Markov model of a single-server queue with losses and maintenance of an unreliable server. Cybern Syst Anal. 2015;51:632–643. DOI: 10.1007/s10559-015-9754-5.

20. 20. Peschansky A.I. Kovalenko A.I. Stationary characteristics of a single-server queue system with losses and an unreliable server. Tavricheskii vestnik informatiki i matematiki = Taurida Journal of Computer Science Theory and Mathematics. 2013;1(22):69–79. (In Russ.).