Markovian arrival processes

From Wikipedia, the free encyclopedia

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

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

Contents

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

[edit] Poisson process

The Poisson arrival process or Poisson process counts the number of arrivals, each of which has a 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.

[edit] 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 D1 sub-matrix. Sub-matrices D0 and D1 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.

[edit] 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

D0 = R − D1

[edit] 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]

[edit] 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 Dk. Sub-matrices Dk 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}

[edit] References

 This article or section includes a list of references or external links, but its sources remain unclear because it lacks in-text citations.
You can improve this article by introducing more precise citations.
  • 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.