Markovian arrival processes

In queueing theory, Markovian arrival processes are used to model the arrival of customers to a queue.

Some of the most common include the Poisson process, Markov arrival process and the batch Markov arrival process.

Background

Markovian arrival processes have two processes. A continuous-time Markov process j(t), a Markov process which is generated by a generator or rate matrix, Q. The other process is a counting process N(t), which has state space $\mathbb{N}_{0}:=\mathbb{N}\cup\{0\}$ (where $\mathbb{N}$ is the set of all natural numbers). N(t) increases every time there is a transition in j(t) that is marked.

Poisson process

The Poisson arrival process or Poisson process counts the number of arrivals, each of which has an exponentially distributed time between arrival. In the most general case this can be represented by the rate matrix,

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

In the homogeneous case this is more simply,

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

Here every transition is marked.

Markov arrival process

The Markov arrival process (MAP) is a generalization of the Poisson process by having non-exponential distribution sojourn between arrivals. The homogeneous case has rate matrix,

$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]\; .$

An arrival is seen every time a transition occurs that increases the level (a marked transition), e.g. a transition in the D₁ sub-matrix. Sub-matrices D₀ and D₁ have elements of λ_i,j, the rate of a Poisson process, such that,

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

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

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

and

$(D_{0}+D_{1})\boldsymbol{1}=\boldsymbol{0}$

There are several special cases of the Markov arrival process.

Markov-modulated Poisson process

The Markov-modulated Poisson process or MMPP where m Poisson processes are switched between by an underlying Markov process. If each of the m Poisson processes has rate λ_i and the underlying process is generated by a $m\times m$ generator matrix R, then in the MAP representation,

$D_{1} = \operatorname{diag}\{\lambda_{1},\dots,\lambda_{m}\}$

a diagonal matrix of the rates of the Poisson process, and

D₀ = R − D₁

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

The batch Markovian arrival process (BMAP) is a generalisation of the Markovian arrival process by having arrivals of size greater than one. 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 λ_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}$

References

• Søren Asmussen (2000). Matrix-analytic Models and their Analysis, Scandinavian Journal of Statistics 27(2), 193–226.
• David M. Lucantoni (1993). The BMAP/G/1 Queue: A Tutorial, Lecture Notes in Computer Science: Performance Evaluation of Computer and Communication Systems (Editors: Lorenzo Donatiello and Randolph Nelson), volume 729.
• Srinivas R. Chakravarthy (2001). The batch Markovian arrival process: A review and future work. In Advances in Probability and Stochastic Processes, Ed. A. Krishnamoorthy, N.Raju and V. Ramaswami, Notable Publications, Inc., New Jersey, USA, 21-49.
• Srinivas R. Chakravarthy (2010). Markovian Arrival Processes. Wiley Encyclopedia of Operations Research and Management Science. Published Online: 15 JUN 2010.
• Marcel F. Neuts (1992). Models based on the Markovian arrival process. IEICE Transactions on Communications, E75B, 1255-1265.