“Markovian arrival 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]

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]

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

Special cases

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

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 allowing more than one arrival at a time.^[7] The homogeneous case has rate matrix,

An arrival of size

occurs every time a transition occurs in the sub-matrix

. Sub-matrices

have elements of

, the rate of a Poisson process, such that,

Fitting

Software

See also

References

1. ^{{Cite book | first1=S. R. |last1=Asmussen| doi = 10.1007/0-387-21525-5_11 | chapter = Markov Additive Models | title = Applied Probability and Queues | series = Stochastic Modelling and Applied Probability | volume = 51 | pages = 302–339 | year = 2003 | isbn = 978-0-387-00211-8 | pmid = | pmc = }}
2. ^¹{{Cite journal | last1 = Asmussen | first1 = S. | title = Matrix-analytic Models and their Analysis | doi = 10.1111/1467-9469.00186 | journal = Scandinavian Journal of Statistics | volume = 27 | issue = 2 | pages = 193–226 | year = 2000 | jstor = 4616600| pmid = | pmc = |via=JSTOR |registration=y}}
3. ^{{Cite book | last1 = Chakravarthy | first1 = S. R. | chapter = Markovian Arrival Processes | doi = 10.1002/9780470400531.eorms0499 | title = Wiley Encyclopedia of Operations Research and Management Science | year = 2011 | isbn = 9780470400531 | pmid = | pmc = }}
4. ^{{cite journal | last1 = Neuts | first1 = Marcel F. | year = 1979 | title = A Versatile Markovian Point Process | journal = Journal of Applied Probability | volume = 16 | issue = 4 | pages = 764–779 | publisher = Applied Probability Trust | jstor = 3213143 |via=JSTOR |registration=y}}
5. ^{{Cite journal | last1 = Casale | first1 = G. | doi = 10.1145/2007116.2007176 | title = Building accurate workload models using Markovian arrival processes | journal = ACM SIGMETRICS Performance Evaluation Review | volume = 39 | pages = 357 | year = 2011 | pmid = | pmc = }}
6. ^{{Cite journal | last1 = Fischer | first1 = W. | last2 = Meier-Hellstern | first2 = K. | doi = 10.1016/0166-5316(93)90035-S | title = The Markov-modulated Poisson process (MMPP) cookbook | journal = Performance Evaluation | volume = 18 | issue = 2 | pages = 149 | year = 1993 | pmid = | pmc = }}
7. ^{{Cite book | last1 = Lucantoni | first1 = D. M. | chapter = The BMAP/G/1 queue: A tutorial | doi = 10.1007/BFb0013859 | title = Performance Evaluation of Computer and Communication Systems | series = Lecture Notes in Computer Science | volume = 729 | pages = 330 | year = 1993 | isbn = 3-540-57297-X | pmid = | pmc = }}
8. ^{{Cite book | last1 = Buchholz | first1 = P. | chapter = An EM-Algorithm for MAP Fitting from Real Traffic Data | doi = 10.1007/978-3-540-45232-4_14 | title = Computer Performance Evaluation. Modelling Techniques and Tools | series = Lecture Notes in Computer Science | volume = 2794 | pages = 218–236 | year = 2003 | isbn = 978-3-540-40814-7 | pmid = | pmc = }}
9. ^{{Cite book | last1 = Casale | first1 = G. | last2 = Zhang | first2 = E. Z. | last3 = Smirni | first3 = E. | doi = 10.1109/QEST.2008.33 | chapter = KPC-Toolbox: Simple Yet Effective Trace Fitting Using Markovian Arrival Processes | title = 2008 Fifth International Conference on Quantitative Evaluation of Systems | pages = 83 | year = 2008 | isbn = 978-0-7695-3360-5 | pmid = | pmc = | url = http://www.doc.ic.ac.uk/~gcasale/qest08kpctoolbox.pdf}}