Markovian arrival process

This article is about arrival processes to queues. For bivariate processes, see Markov additive process.

In queueing theory, a discipline within the mathematical theory of probability, a Markovian arrival process (MAP or MArP ^[1] ) is a mathematical model for the time between job arrivals to a system. The simplest such process is a Poisson process where the time between each arrival is exponentially distributed. ^{[2] [3]}

The processes were first suggested by Marcel F. Neuts in 1979. ^{[2] [4]}

Definition

A Markov arrival process is defined by two matrices, D₀ and D₁ where elements of D₀ represent hidden transitions and elements of D₁ observable transitions. The block matrix Q below is a transition rate matrix for a continuous-time Markov chain. ^[5]

${\displaystyle Q=\left[{\begin{matrix}D_{0}&D_{1}&0&0&\dots \\0&D_{0}&D_{1}&0&\dots \\0&0&D_{0}&D_{1}&\dots \\\vdots &\vdots &\ddots &\ddots &\ddots \end{matrix}}\right]\;.}$

The simplest example is a Poisson process where D₀ = −λ and D₁ = λ where there is only one possible transition, it is observable, and occurs at rate λ. For Q to be a valid transition rate matrix, the following restrictions apply to the D_i

${\displaystyle {\begin{aligned}0\leq [D_{1}]_{i,j}&<\infty \\0\leq [D_{0}]_{i,j}&<\infty \quad i\neq j\\\,[D_{0}]_{i,i}&<0\\(D_{0}+D_{1}){\boldsymbol {1}}&={\boldsymbol {0}}\end{aligned}}}$

Special cases

Phase-type renewal process

The phase-type renewal process is a Markov arrival process with phase-type distributed sojourn between arrivals. For example, if an arrival process has an interarrival time distribution PH${\displaystyle ({\boldsymbol {\alpha }},S)}$ with an exit vector denoted ${\displaystyle {\boldsymbol {S}}^{0}=-S{\boldsymbol {1}}}$, the arrival process has generator matrix,

${\displaystyle Q=\left[{\begin{matrix}S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&0&0&\dots \\0&S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&0&\dots \\0&0&S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&\dots \\\vdots &\vdots &\ddots &\ddots &\ddots \\\end{matrix}}\right]}$

Generalizations

Batch Markov arrival process

The batch Markovian arrival process (BMAP) is a generalisation of the Markovian arrival process by allowing more than one arrival at a time. ^{[6] [7]} The homogeneous case has rate matrix,

${\displaystyle Q=\left[{\begin{matrix}D_{0}&D_{1}&D_{2}&D_{3}&\dots \\0&D_{0}&D_{1}&D_{2}&\dots \\0&0&D_{0}&D_{1}&\dots \\\vdots &\vdots &\ddots &\ddots &\ddots \end{matrix}}\right]\;.}$

An arrival of size ${\displaystyle k}$ occurs every time a transition occurs in the sub-matrix ${\displaystyle D_{k}}$. Sub-matrices ${\displaystyle D_{k}}$ have elements of ${\displaystyle \lambda _{i,j}}$, the rate of a Poisson process, such that,

${\displaystyle 0\leq [D_{k}]_{i,j}<\infty \;\;\;\;1\leq k}$

${\displaystyle 0\leq [D_{0}]_{i,j}<\infty \;\;\;\;i\neq j}$

${\displaystyle [D_{0}]_{i,i}<0\;}$

and

${\displaystyle \sum _{k=0}^{\infty }D_{k}{\boldsymbol {1}}={\boldsymbol {0}}}$

Markov-modulated Poisson process

The Markov-modulated Poisson process or MMPP where m Poisson processes are switched between by an underlying continuous-time Markov chain. ^[8] If each of the m Poisson processes has rate λ_i and the modulating continuous-time Markov has m × m transition rate matrix R, then the MAP representation is

${\displaystyle {\begin{aligned}D_{1}&=\operatorname {diag} \{\lambda _{1},\dots ,\lambda _{m}\}\\D_{0}&=R-D_{1}.\end{aligned}}}$

Fitting

A MAP can be fitted using an expectation–maximization algorithm. ^[9]

Software

• KPC-toolbox a library of MATLAB scripts to fit a MAP to data. ^[10]

See also

• Rational arrival process

References

1. Asmussen, S. R. (2003). "Markov Additive Models". Applied Probability and Queues. Stochastic Modelling and Applied Probability. Vol. 51. pp. 302–339. doi:10.1007/0-387-21525-5_11. ISBN   978-0-387-00211-8.
2. Asmussen, S. (2000). "Matrix-analytic Models and their Analysis". Scandinavian Journal of Statistics. 27 (2): 193–226. doi: 10.1111/1467-9469.00186 . JSTOR   4616600. S2CID   122810934.
3. Chakravarthy, S. R. (2011). "Markovian Arrival Processes". Wiley Encyclopedia of Operations Research and Management Science. doi:10.1002/9780470400531.eorms0499. ISBN   9780470400531.
4. Neuts, Marcel F. (1979). "A Versatile Markovian Point Process". Journal of Applied Probability. Applied Probability Trust. 16 (4): 764–779. doi:10.2307/3213143. JSTOR   3213143. S2CID   123525892.
5. Casale, G. (2011). "Building accurate workload models using Markovian arrival processes". ACM SIGMETRICS Performance Evaluation Review. 39: 357. doi:10.1145/2007116.2007176.
6. Lucantoni, D. M. (1993). "The BMAP/G/1 queue: A tutorial". Performance Evaluation of Computer and Communication Systems. Lecture Notes in Computer Science. Vol. 729. pp. 330–358. doi:10.1007/BFb0013859. ISBN   3-540-57297-X. S2CID   35110866.
7. Singh, Gagandeep; Gupta, U. C.; Chaudhry, M. L. (2016). "Detailed computational analysis of queueing-time distributions of the BMAP/G/1 queue using roots". Journal of Applied Probability. 53 (4): 1078–1097. doi:10.1017/jpr.2016.66. S2CID   27505255.
8. Fischer, W.; Meier-Hellstern, K. (1993). "The Markov-modulated Poisson process (MMPP) cookbook". Performance Evaluation. 18 (2): 149. doi:10.1016/0166-5316(93)90035-S.
9. Buchholz, P. (2003). "An EM-Algorithm for MAP Fitting from Real Traffic Data". Computer Performance Evaluation. Modelling Techniques and Tools. Lecture Notes in Computer Science. Vol. 2794. pp. 218–236. doi:10.1007/978-3-540-45232-4_14. ISBN   978-3-540-40814-7.
10. Casale, G.; Zhang, E. Z.; Smirni, E. (2008). "KPC-Toolbox: Simple Yet Effective Trace Fitting Using Markovian Arrival Processes" (PDF). 2008 Fifth International Conference on Quantitative Evaluation of Systems. p. 83. doi:10.1109/QEST.2008.33. ISBN   978-0-7695-3360-5. S2CID   252444.