Markovian arrival process explained

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.^[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]

Q = \left[\begin{matrix} D _{0} &D _{1} & 0 & 0 & ... \\ 0 &D _{0} &D _{1} & 0 & ... \\ 0 & 0 &D _{0} &D _{1} & ... \\ \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

\begin{align} 0 \leq [D _{1} ] _{i,j} &< inf ty \\ 0 \leq [D _{0} ] _{i,j} &< inf ty i ≠ j \\ [D _{0} ] _{i,i} &< 0 \\ (D _{0} + D _{1} )\boldsymbol{ 1 } & = \boldsymbol{ 0 } \end{align}

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

(\boldsymbol{\alpha},S) with an exit vector denoted \boldsymbol{S} ^{0} =- S\boldsymbol{ 1 } , the arrival process has generator matrix,Q = \left[\begin{matrix} S&\boldsymbol{S} ^{0} \boldsymbol{\alpha}& 0 & 0 & ... \\ 0 &S&\boldsymbol{S} ^{0} \boldsymbol{\alpha}& 0 & ... \\ 0 & 0 &S&\boldsymbol{S} ^{0} \boldsymbol{\alpha}& ... \\ \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,

Q = \left[\begin{matrix} D _{0} &D _{1} &D _{2} &D _{3} & ... \\ 0 &D _{0} &D _{1} &D _{2} & ... \\ 0 & 0 &D _{0} &D _{1} & ... \\ \vdots & \vdots & \ddots & \ddots & \ddots \end{matrix}\right] .

An arrival of size

k occurs every time a transition occurs in the sub-matrix D _{k} . Sub-matrices D _{k} have elements of λ _{i,j} , the rate of a Poisson process, such that,0 \leq [D _{k} ] _{i,j} < inf ty 1 \leq k 0 \leq [D _{0} ] _{i,j} < inf ty i ≠ j [D _{0} ] _{i,i} < 0

and

\sum ^{inf ty} _{k =0} 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

\begin{align} D _{1} & = \operatorname{diag}\{ λ _{1} , ... , λ _{m} \}\\ D _{0} & = R - D _{1. \end{align}}

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

Notes and References

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