- 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.
Contents
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
(where
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,
In the homogeneous case this is more simply,
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,
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,
and
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
generator matrix R, then in the MAP representation,
a diagonal matrix of the rates of the Poisson process, and
- D0 = R − D1
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
with an exit vector denoted
, the arrival process has generator matrix,
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,
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,
and
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.
Categories:- Queueing theory
- Markov processes
Wikimedia Foundation. 2010.