DOI
10.34229/KCA2522-9664.24.6.7
UDC 519.872
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
kuznetsov2016@icloud.com
|
2 Physical and Technical Institute of the National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine
sea_hawk@icloud.com
|
3 Physical and Technical Institute of the National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine
shumska-aa@ukr.net
|
|
FAST SIMULATION OF CUSTOMERS BLOCKING PROBABILITY
IN A QUEUEING SYSTEM WITH POISSON INPUT FLOW CONTROLLED
BY A SEMI-MARKOV PROCESS
Abstract. A multichannel queueing system with a Poisson input flow is considered.
The input flow rate depends on the current state of a semi-Markov process. This state also determines the type of the customer.
Each channel contains several service lines. To be serviced, the customer requires several lines with the distribution dependent on the customer’s type.
Not each channel is accessible for customers of a given type.
The accessibility is determined by some distribution depending both on the customer’s type and on the required number of lines.
If the channel does not have sufficient service lines, it is possible to reorient this customer to another channel.
The service time has a general distribution function depending on the customer’s type and the number of lines required for servicing.
A fast simulation method is proposed to evaluate the blocking probability of customers of a certain type demanding a given number of service lines. A comparison with the Monte Carlo method is made using a numerical example, and the change in the relative error of the estimate for decreasing blocking probability is analyzed.
Keywords: queueing system, semi-Markov process, channel, line, blocking probability, Monte Carlo method, fast simulation, estimate, relative error.
full text
REFERENCES
- 1. Ross K.W. Multiservice loss models for broadband telecommunication networks. London: Springer Verlag, 1995. 343 p.
- 2. Frenkel I.B., Karagrigoriou A., Lisnianski A., Kleyner A.V. Applied reliability engineering and risk analysis: Probabilistic models and statistical inference. New York: Wiley, 2013. 448 p.
- 3. Nyberg E., Virtamo J., Aalto S. An exact algorithm for calculating blocking probabilities in multicast networks. Networking. Ed. by G. Pujolle, H. Perros, S. Fdida, U. Krner, I. Stavrakakis. Paris, 2000. P. 275–286
- 4. Karvo J. Efficient simulation of blocking probabilities for multi-layer multicast streams. Networking. Ed. by E. Gregori, M. Conti, A. Campbell, C. Omidyar, M. Zukerman. Berlin: Springer-Verlag, 2002. P. 1020–1031
- 5. Beaubrun R., Pierre S., Conan J. Analysis of traffic distribution and blocking probability in future wireless networks. Int. J. of Wireless Inf. Networks. 2007. Vol. 14, N 1. P. 47–53
- 6. Beaubrun R., Ajinou W., Pierre S. Evaluation of blocking probability in multiservice wireless network. 2011, IFIP Wireless Days, 2011. P. 1–3
- 7. Wong E.W.M., Guo J., Moran B., Zukerman M. Information exchange surrogates for approximation of blocking probabilities in overflow loss systems. Proc. 25th Int. Teletraffic Congr. (ITC), 2013. P. 1–9
- 8. Chan Y.-C., Wong E.W.M. Blocking probability evaluation for non-hierarchical overflow loss systems. IEEE Trans. Commun. 2018. Vol. 66, N 5. P. 2022–2036
- 9. Wong E.W.M., Chan Y.-C. A century-long challenge in teletraffic theory: blocking probability evaluation for overflow loss systems with mutual overflow. IEEE Access. 2023. Vol. 11. P. 61274–61288
- 10. Sagkriotis S.G., Pantelis S.K., Moscholios I.D., Vassilakis V.G. Call blocking probabilities in a two-link multirate loss system for Poisson traffic. IET Networks. 2018. Vol. 7, N 4. P. 233–241
- 11. Heidelberger P. Fast simulation of rare events in queueing and reliability models. ACM Transactions on Modeling and Computer Simulation. 1995. Vol. 5, Iss. 1. P. 43–85
- 12. Falkner M., Devetsikiotis M., Lambadaris I. Fast simulation of networks of queues with effective and decoupling bandwidths. ACM Transactions on Modeling and Computer Simulation. 1999. Vol. 9, N 1. P. 45–58
- 13. Glasserman P., Heіdelberger Ph., Shahabuddіn P., Zajіc T. Multilevel splitting for estimating rare event probabilities. Oper. Research. 1999. Vol. 47, N 4. P. 585–600
- 14. Li J., Mosleh A., Kang R. Likelihood ratio gradient estimation for dynamic reliability applications. Reliab. Engin. and System Safety. 2011. Vol. 96, N 12. P. 1667–1679
- 15. Glasserman P. Monte Carlo methods in financial engineering. New York: Springer, 2004. 575 p.
- 16. Kovalenko I.N., Kuznetsov N.Yu. Methods of calculation of highly reliable systems [in Russian]. Moscow: Radio i svyaz’, 1988. 176 p.
- 17. Kovalenko I.N., Kuznetsov N.Yu., Pegg Ph.A. Mathematical theory of reliability of time dependent systems with practical applications. Chichester: Wiley, 1997. 303 p.
- 18. Shumskaya A.A. Accelerated modeling of the coefficient of unavailability of the restored system with limited relative error of the estimate. Kibernetika i sistemnyi analiz. 2003. N 3. P. 45–58
- 19. Kuznetsov N.Yu. Fast simulation technique in reliability evaluation of Markovian and non-Markovian systems. Simulation and Optimization Methods in Risk and Reliability Theory. New York: Nova Science Publishers, 2009. P. 69–112
- 20. Kuznetsov N.Yu., Shumskaya A.A. Assessment of the danger of failure of a redundant system by the method of accelerated modeling. Problemy upravleniya i informatiki. 2013. N 3. P. 50–62
- 21. Lagnoux A. Rare event simulation. Probab. Eng. and Inf. Sci. 2006. Vol. 20, N 1. P. 45–66
- 22. Gertsbakh I.B., Shpungin Y. Models of network reliability: Analysis, combinatorics, and Monte Carlo. Boca Raton: CRC Press, 2009. 203 p.
- 23. Blanchet J., Lam H. Rare event simulation techniques. Proc. of the 2011 Winter Simulation Conference. 2011, P. 217–231
- 24. Kuznetsov N.Yu., Kuznetsov I.N. Accelerated modeling of the probability of blocking of requests in service networks with multiple access. Kibernetika i sistemnyi analiz. 2021.Vol Т. 57, N 4. P. 30–43
- 25. Kuznetsov M.Yu., Shumska A.A. Accelerated simulation of the stationary probability of call blocking in a two-channel system with threshold service strategies. Kibernetyka ta systemnyi analiz. 2023. Vol. 59, N 5. P. 124–134
- 26. Kuznetsov M.Yu., Kuznetsov I.M., Shumska A.A. Accelerated simulation of the probability of blocking demands in a service network with multiple access and periodic intensities of incoming flows. Problemy keruvannya ta informatyky. 2023. N 3. P. 32–46
- 27. Kuznetsov I.M., Shumska A.A. Application of Accelerated Simulation to Finding Demand Blockage Probability in a Multi-Channel, Multiple Access Service System. Kibernetyka ta systemnyi analiz. 2024. Vol. 60, N 2. P. 51–63