Markovian arrival process

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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 Neuts in 1979.[2][4]

Definition[edit]

A Markov arrival process is defined by two matrices D0 and D1 where elements of D0 represent hidden transitions and elements of D1 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&\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 D0 = −λ and D1 = λ 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 Di

\begin{align}
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{align}

Special cases[edit]

Markov-modulated Poisson process[edit]

The Markov-modulated Poisson process or MMPP where m Poisson processes are switched between by an underlying continuous-time Markov chain.[6] 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}\{\lambda_{1},\dots,\lambda_{m}\}\\
D_{0} &=R-D_1.
\end{align}

Phase-type renewal process[edit]

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&\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]

Batch Markov arrival process[edit]

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


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 k occurs every time a transition occurs in the sub-matrix D_{k}. Sub-matrices D_{k} have elements of \lambda_{i,j}, the rate of a Poisson process, such that,


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

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

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

and


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

Fitting[edit]

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

Software[edit]

See also[edit]

References[edit]

  1. ^ Asmussen, S. R. (2003). "Markov Additive Models". Applied Probability and Queues. Stochastic Modelling and Applied Probability 51. pp. 302–339. doi:10.1007/0-387-21525-5_11. ISBN 978-0-387-00211-8.  edit
  2. ^ a b 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‎.  edit
  3. ^ Chakravarthy, S. R. (2011). "Markovian Arrival Processes". Wiley Encyclopedia of Operations Research and Management Science. doi:10.1002/9780470400531.eorms0499. ISBN 9780470400531.  edit
  4. ^ Neuts, Marcel F. (1979). "A Versatile Markovian Point Process". Journal of Applied Probability (Applied Probability Trust) 16 (4): 764–779. JSTOR 3213143. Retrieved 11 June 2013.  edit
  5. ^ Casale, G. (2011). "Building accurate workload models using Markovian arrival processes". ACM SIGMETRICS Performance Evaluation Review 39: 357. doi:10.1145/2007116.2007176.  edit
  6. ^ 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.  edit
  7. ^ Lucantoni, D. M. (1993). "The BMAP/G/1 queue: A tutorial". Performance Evaluation of Computer and Communication Systems. Lecture Notes in Computer Science 729. p. 330. doi:10.1007/BFb0013859. ISBN 3-540-57297-X.  edit
  8. ^ 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 2794. pp. 218–236. doi:10.1007/978-3-540-45232-4_14. ISBN 978-3-540-40814-7.  edit
  9. ^ Casale, G.; Zhang, E. Z.; Smirni, E. (2008). "KPC-Toolbox: Simple Yet Effective Trace Fitting Using Markovian Arrival Processes". 2008 Fifth International Conference on Quantitative Evaluation of Systems. p. 83. doi:10.1109/QEST.2008.33. ISBN 978-0-7695-3360-5.  edit