Informatics and Applications

2020, Volume 14, Issue 4, pp 37-46

ON MARKOVIAN AND RATIONAL ARRIVAL PROCESSES. II

V. A. Naumov
К. Е. Samouylov

Abstract

This article is the second part of the review carried out within the framework of the RFBR project No. 19-17-50126. The purpose of this review is to get the interested readers familiar with the basics of the theory of Markovian arrival processes to facilitate the application of these models in practice and, if necessary, to study them in detail. In the first part of the review, the properties of the general Markovian arrival processes are presented and their relationship with Markov additive processes and Markov renewal processes is shown. In the second part of the review, the important for applications subclasses of Markovian arrival processes, i. e., simple and batch arrival processes of homogeneous and heterogeneous arrivals, are considered. It is shown how the properties of Markovian arrival processes are associated with the product form of stationary distributions of Markov systems. In conclusion, matrix-exponential distributions and rational arrival processes are discussed that expand the capabilities of Markovian arrival processes for modeling complex systems, while preserving the convenience of analyzing them using computations.

[+] References (57)

Naumov, V. A. 1976. O nezavisimoy rabote podsistem slozhnoy sistemy [About independent operation of sub-systems of a complex system]. Tr. Ill Vsesoyuznoy shkoly- seminara po teorii massovogo obsluzhivaniya [3th All- Russian School-Seminar of Queuing Theory Proceedings]. Moscow. 2:169-177.
Bocharov, P. P., and V. A. Naumov. 1976. Analiz giperek- sponentsial'noy dvukhfaznoy sistemy s ogranichennym nakopitelem [Analysis of a hyperexponential two-phase system with a limited storage]. Informatsionnye seti i ikh struktura [Information networks and their structure]. Moscow: Nauka. 168-180.
Naumov, V.A. 1977. Ob obsluzhennoy i izbytochnoy nagruzkakh polnodostupnogo puchka s ogranichennoy ochered'yu [About serviced and excessive loads of a fully accessible bundle with a limited queue]. Chislennye metody resheniya zadach matematicheskoy fiziki i teorii system [Numerical methods for solving problems of mathematical physics and systems theory]. Moscow: UDN. 51-55.
Naumov, V. A. 1978. Issledovanie nekotorykh mnogo- faznykh sistem massovogo obsluzhivaniya [Research of some multiphase queuing systems]. Moscow: UDN. PhD Thesis. 98 p.
Lucantoni, D. M., K. Meier-Hellstern, and M. F Neuts. 1990. A single-server queue with server vacations and a class of non-renewal arrival processes. Adv. Appl. Probab. 22(3):676-705.
Basharin, G.P., V.A. Kokotushkin, and V.A. Naumov 1979. O metode ekvivalentnykh zamen rascheta fragmentov setey svyazi dlya TsVM [On the method of equivalent substitutions for calculating fragments of communication networks for a central computer]. Engineering Cybernetics 6:92-99.
Basharin, G.P., and V.A. Naumov. 1984. Simple matrix description of peaked and smooth traffic and its applications. 3rd ITC Specialist Seminar on Fundamentals of Teletraffic Theory. Moscow: VINITI. 38-44.
Neuts, M. F 1978. Renewal processes of phase type. Nav. Res. Logist. Q. 25(3):445-454.
Cinlar, E. 1967. Queues with semi-Markovian arrivals. J. Appl. Probab. 4(2):365-379.
Franken, P. 1968. Erlangsche Formeln fur semi- markowschen Eingang. Elektronische lnformationsverar- beitung Kybernetik 4(3):197-204.
Franken, P., and J. Kerstan. 1968. Bedienungssysteme mit unendlich vielen Bedienungsapparaten. Operations- forschung Mathematische Statistik 1:67-76.
Neuts, M.F., and S.-Z. Chen. 1972. The infinite server queue with semi-Markovian arrivals and negative exponential services. J. Appl. Probab. 9(1):178-184.
Bean, N. G., D. A. Green, and P. G. Taylor. 1996. When is a MAP poisson? 2nd Australia-Japan Workshop on Stochastic Models in Engineering, Technology and Man-agement Proceedings. Eds. J. Wilson, D. N. P. Murthy, and S. Osaki. Brisbane: Technology Management Center, University of Queensland. 34-43.
Naumov, V. A. 1988. Matrichnyy analog formuly Erlanga [The matrix analogue of a formula of Erlang]. Modeli raspredeleniya informatsii i metody ikh analiza [Information distribution models and methods for their analysis]. Moscow: VINITI. 39-43.
He, Q.-M. 1996. Queues with marked customers. Adv. Appl. Probab. 28(2):567-587.
He, Q.-M., and M. F. Neuts. 1998. Markov chains with marked transitions. Stoch. Proc. Appl. 74:37-52.
Neuts, M. F. 1977. A versatile Markovian point process. Newark, DE: University of Delaware, Department of Statistics and Computer Science. Technical Report 77/13. 29 p.
Neuts, M. F. 1989. Structured stochastic matrices ofM/G/1 type and their applications. New York, NY: Marcel Dekker. 512 p.
Lucantoni, D. M. 1991. New results on the single server queue with a batch Markovian arrival process. Communi-cations Statistics. Stochastic Models 7(1):1-46.
Narayana, S., andM. F. Neuts. 1992. The first two moment matrices of the counts for the Markovian arrival processes. Communications Statistics. Stochastic Models 8(3):459- 477.
Nielsen, B.F, L.A.F Nilsson, U. H. Thygesen, and J. E. Beyer. 2007. Higher order moments and conditional asymptotics of the batch Markovian arrival process. Stoch. Models 23(1): 1-26.
Bocharov, P.P., and V. A. Naumov 1977. O nekotorykh sistemakh massovogo obsluzhivaniya konechnoy emkosti [On some queueing systems of finite capacity]. Problemy peredachi informatsii [Problems of Information Transmis-sion] 13(4):96-104.
Naumov, V.A. 1982. Ob odnolineynoy sisteme s ogranichennym nakopitelem i zayavkami neskol'kikh vidov [About a single-line system with limited storage and multiple types of requests]. Modeli sistem raspredeleniya informatsii i ikh analiz [Models of information distribution systems and methods for their analysis]. Moscow: Nauka. 77-82.
Naumov, V. A. 1986. O funktsiyakhraspredeleniyasratsio- nal'nympreobrazovaniemLaplasa-Stilt'esa [Ondistribu-tion functions with rational Laplace-Stiltjes trans-formation]. Analiz informatsionno-vychislitel'nykh system [Analysis of information and computing systems]. Moscow: UDN. 47-56.
Bocharov, P.P., and A.V. Pechinkin. 1995. Teoriya massovogo obsluzhivaniya [Queueing theory]. Moscow: RUDN. 528 p.
Bocharov, P. P., C. D'Apice, A. V. Pechinkin, and S. Salerno. 2004. Queueing theory. Utrecht-Boston: VSP. 446 p.
Asmussen, S., and M. Bladt. 1996. Renewal theory and queueing algorithms for matrix-exponential distributions. Matrix-analytic methods in stochastic models. Eds. A. S. Alfa and S. Chakravarty. New York, NY: Marcel Dekker. 313-341.
Cox, D. R. 1955. A use of complex probabilities in the theory of stochastic processes. Math. Proc. Cambridge 51(2):313-319.
O'Cinneide, C.A. 1990. Characterization of phase-type distributions. Communications Statistics. Stochastic Models 6(1):1-57.
Bodrog, L., A. Horvath, and M. Telek. 2008. On the properties of moments of matrix exponential distributions and matrix exponential processes. Dagstuhl Seminar Proceedings 07461:1394.
Asmussen, S., and M. Bladt. 1999. Point processes with finite-dimensional conditional probabilities. Stoch. Proc. Appl. 82(1):127-142.
Horvath, G., and M. Telek. 2012. Acceptance-rejection methods for generating random variables from matrix exponential distribution and rational arrival processes. Matrix-analytic methods in stochastic models. Eds. G. La-touche, V. Ramaswami, J. Sethuraman, et al. New York, NY: Springer. 123-144.
Erlang, A. K. 1917. L0sning af nogle Problemer fra Sandsynlighedsregningen af Betydning for de automatiske Telefoncentraler. Elektroteknikeren 13:5-13.
Neuts, M. F 1975. Probability distribution of phase type. Liber Amicorum Professor Emeritus H. Florin. Ottignies- Louvain-la-Neuve, Belgium: University of Louvain, De-partment of Mathematics. 173-206.
Bartlett, M. S. 1945. Negative probability. Math. Proc. Cambridge 41(1):71-73.
Cox, D. R. 1955. The analysis of non-Markovian stochas-tic processes by the inclusion of supplementary variables. Math. Proc. Cambridge 51(3):433-441.
Bladt, M., and M. F Neuts. 2003. Matrix-exponential distributions: Calculus and interpretations via flows. Stoch. Models 19(1):113-124.
Khrennikov, A. 2009. Interpretations of probability. 2nd ed. Berlin: Walter de Gruyter. 237 p.
Naumov, V.A. 1987. Markovskie modeli potokov trebo- vaniy [Markov models of demand flows]. Sistemy massovogo obsluzhivaniya i informatika [Queuing systems and com-puter science]. Moscow: UDN. 67-73.
Asmussen, S. 2000. Matrix-analytic models and their analysis. Scand. J. Stat. 27(2):193-226.
Bladt, M. 2005. A review on phase-type distributions and their use in risk theory. ASTINBull. 35(1):145-161.
Artalejo, J. R., and A. Gomez-Corral. 2010. Markovian arrivals in stochastic modelling: A survey and some new results. SORT- Stat. Oper. Res. T. 34(2):101-144.
Vishnevskiy, V. M., and A. N. Dudin. 2017. Queueing systems with correlated arrival flows and their applications to modeling telecommunication networks. Automat. Rem. Contr. 78(8):1361-1403.
Basharin, G., V. Naumov, and K. Samouylov. 2018. On Markovian modelling of arrival processes. Stat. Pap. 59(4):1533-1540.
Neuts, M. F. 1981. Matrix-geometric solutions in stochastic models: An algorithmic approach. Baltimore, MA: The John Hopkins University Press. 332 p.
Latouche, G., and V. Ramaswami. 1999. Introduction to matrix analytic methods in stochastic modeling. Philadel-phia, PA: ASA & SIAM. 334 p.
Asmussen, S. 2003. Applied probability and queues. New York, NY: Springer. 438 p.
Breuer, L., andD. Baum. 2005. An introduction to queueing theory and matrix-analytic methods. Dordrecht: Springer. 272 p.
Bini, D.A., G. Latouche, and B. Meini. 2005. Numerical methods for structured Markov chains. New York, NY Oxford University Press. 336 p.
Asmussen, S., and C.A. O'Cinneide. 2006. Matrix- exponential distributions. Encyclopedia of statistical sciences. Eds. S. Kotz, C. B. Read, N. Balakrishnan, B. Vi- dakovic, and N. L. Johnson. Hoboken, NJ: John Wiley & Sons. 3:1-5. doi: 10.1002/0471667196.ess1092.pub2.
Li, Q.-L. 2009. Constructive computation in stochastic models with applications. Berlin: Springer-Verlag. 650 p.
Lipsky, L. 2009. Queueing theory: A linear algebraic approach. 2nd ed. New York, NY: Springer. 548 p.
Alfa, A. S. 2010. Queueing theory for telecommunications. New York, NY: Springer. 238 p.
He, Q.-M.2014. Fundamentals of matrix-analytic methods. New York, NY: Springer. 349 p.
Buchholz, P., J. Kriege, and I. Felko. 2014. Input modeling with phase-type distributions and Markov models. Theory and applications. New York, NY: Springer. 127 p.
Naumov, V. A., K. E. Samuylov, and Yu.V. Gaidamaka. 2015. Mul'tiplikativnye resheniya konechnykh tsepey Markova [Multiplicative solutions of finite Markov chains]. Moscow: RUDN. 159 p.
Bladt, M., and B. F. Nielsen. 2017. Matrix-exponential distributions in applied probability. Boston, MA: Springer. 736 p.

[+] About this article