Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Phase Type and Matrix Exponential Distributions in Stochastic Modeling Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Fitting Phase-Type Distributions and Markovian Arrival Processes: Algorithms and Tools

Authors : Hiroyuki Okamura, Tadashi Dohi

Published in: Principles of Performance and Reliability Modeling and Evaluation

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This chapter provides a comprehensive survey of PH (phase-type) distribution and MAP (Markovian arrival process) fitting. The PH distribution and MAP are widely used in analytical model-based performance evaluation because they can approximate non-Markovian models with arbitrary accuracy as Markovian models. Among a number of past research results on PH/MAP fitting, we present the mathematical definition of the PH distribution and MAP, and summarize the most recent state-of-the-art results on the fitting methods. We also offer an overview of the software tools for PH/MAP fitting.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
previous chapter An Analytical Framework to Deal with Changing Points and Variable Distributions in Quality Assessment
next chapter Constant-Stress Accelerated Life-Test Models and Data Analysis for One-Shot Devices
Footnotes
1
The PH parameters can be defined by \((\varvec{\alpha }, \varvec{T})\). In this chapter, since the diagonals of \(\varvec{T}\) are determined after estimating nondiagonals of \(\varvec{T}\) and \(\varvec{\tau }\), the PH parameters include \(\varvec{\tau }\).
 
2
When the number of samples increases, the log-likelihood function can be approximated by a multivariate normal distribution.
 
3
The MCMC is a sample-based approximation method for posterior distributions.
 
4
In the implementation, to avoid underflow in \(\hat{\varvec{f}}_k\) and \(\hat{\varvec{b}}_k\), the scaling technique should be applied.
 
Literature
1.
Akaike H (1973) Information theory and an extension of the maximum likelihood principle. In: Petrov BN, Csaki F (eds) Proceedings of the 2nd international symposium on information theory. Akademiai Kiado, pp 267–281
2.
3.
Altiok T (1985) On the phase-type approximations of general distributions. IEEE Trans 17:110–116CrossRef
4.
Andersen AT, Nielsen BF (1998) A Markovian approach for modeling packet traffic with long-range dependence. IEEE J Sel Areas Commun 16(5):719–732CrossRef
5.
6.
Asmussen S, Nerman O, Olsson M (1996) Fitting phase-type distributions via the EM algorithm. Scand J Stat 23(4):419–441MATH
7.
Baum LE, Petrie T, Soules G, Weiss N (1970) A maximization technique occurring in the statistical analysis of probabilistic function of Markov chains. Ann Math Stat 41(1):164–171MathSciNetCrossRefMATH
8.
Bladt M, Gonzalez A, Lauritzen SL (2003) The estimation of phase-type related functionals using Markov chain Monte Carlo methods. Scand Act J 4:280–300MathSciNetCrossRefMATH
9.
Bobbio A, Cumani A (1992) ML estimation of the parameters of a PH distribution in triangular canonical form. In: Balbo G, Serazzi G (eds) Computer performance evaluation. Elsevier Science Publishers, pp 33–46
10.
Bobbio A, Horváth A, Telek M (2005) Matching three moments with minimal acyclic phase type distributions. Stoch Models 21(2/3):303–326MathSciNetCrossRefMATH
11.
12.
Bolch G, Greiner S, de Meer H, Trivedi KS (2006) Queueing networks and Markov chains: modeling and performance evaluation with computer science applications, 2nd edn. Wiley, New YorkCrossRefMATH
13.
Breuer L (2002) An EM algorithm for batch Markovian arrival processes and its comparison to a simpler estimation procedure. Ann Oper Res 112:123–138MathSciNetCrossRefMATH
14.
Buchholz P (2003) An EM-algorithm for MAP fitting from real traffic data. In: Kemper P, Sanders WH (eds) Computer performance evaluation modelling techniques and tools, vol 2794. Springer, LNCS, pp 218–236CrossRef
15.
Buchholz P, Kriege J (2009) A heuristic approach for fitting MAPs to moments and joint moments. In: Proceedings of the 6th international conference on the quantitative evaluation of systems, pp 53–62
16.
Buchholz P, Panchenko A (2004) A two-step EM-algorithm for MAP fitting. In: Proceedings of 19th international symposium on computer and information sciences, LNCS, vol 3280. Springer, pp 217–227
17.
18.
Casale G, Zhang E, Smirni E (2008) KPC-toolbox: simple yet effective trace fitting using Markovian arrival processes. In: Proceedings of 5th international conference on quantitative evaluation of systems (QEST2008), pp 83–92
19.
Cumani A (1982) On the canonical representation of homogeneous Markov processes modelling failure-time distributions. Microelectron Reliab 22:583–602CrossRef
20.
Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the EM algorithm. J R Stat Soc Series B B-39:1–38
21.
Deng L, Mark J (1993) Parameter estimation for Markov modulated Poisson processes via the EM algorithm with time discretization. Telecommun Syst 1:321–338CrossRef
22.
Distefano S, Trivedi KS (2013) Non-Markovian state-space models in dependability evaluation. Qual Reliab Eng Int 29(2):225–239CrossRef
23.
24.
Fackrell M (2005) Fitting with matrix-exponential distributions. Stoch Models 21:377–400MathSciNet
25.
Fearnhead P, Sherlock C (2006) An exact Gibbs sampler for the Markov modulated Poisson processe. J R Stat Soc Series B 66(5):767–784MathSciNetCrossRefMATH
26.
Feldmann A, Whitt W (1998) Fitting mixtures of exponentials to long-tail distributes to analyze network performance models. Perform Eval 31:245–258CrossRef
27.
28.
29.
30.
Heffes H, Lucantoni DM (1986) A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance. IEEE J Sel Areas Commun 4(6):856–868CrossRef
31.
Horváth A, Telek M (2002) PhFit: a general phase-type fitting tool. In: Proceedings of computer performance evaluation/tools, lecture notes in computer science, vol. 2324. Springer, pp 82–91
32.
Horváth G, Buchholz P, Telek M (2005) A MAP fitting approach with independent approximation of the inter-arrival time distribution and the lag correlation. In: Proceedings of the 2nd international conference on the quantitative evaluation of systems. IEEE CS Press, pp 124–133
33.
Horváth G, Okamura H (2013) A fast EM algorithm for fitting marked Markovian arrival processes with a new special structure. In: Proceedings of European performance engineering workshop, lecture notes in computer science (LNCS), vol 8168, pp 119–133
34.
35.
Johnson MA (1993) Selecting parameters of phase distributions: combining nonlinear programming, heuristics, and Erlang distributions. ORSA J Comput 5:69–83CrossRefMATH
36.
Johnson MA, Taaffe MR (1989) Matching moments to phase distributions: mixtures of erlang distribution of common order. Stoch Models 5:711–743MathSciNetCrossRefMATH
37.
Johnson MA, Taaffe MR (1990) Matching moments to phase distributions: density function shapes. Stoch Models 6:283–306
38.
39.
Johnson MA, Taaffe MR (1991) An investigation of phase-distribution moment-matching algorithms for use in queueing models. Queueing Syst 8:129–148MathSciNetCrossRefMATH
40.
41.
Klemm A, Lindemann C, Lohmann M (2003) Traffic modeling of IP networks using the batch Markovian arrival process. Perform Eval 54:149–173CrossRefMATH
42.
43.
Marie R (1980) Calculating equilibrium probabilities for \(\lambda (n)\)/\({C}_k\)/1/\({N}\) queues. In: Proceedings of the 1980 international symposium on computer performance modelling, measurement and evaluation (SIGMETRICS’80). ACM Press, pp 117–125
44.
McLachlan GJ, Jones PN (1988) Fitting mixture models to grouped and truncated data via the EM algorithm. Biometrics 44(2):571–578CrossRefMATH
45.
Mitchell K, van de Liefvoort A (2003) Approximation models of feed-forward G/G/1/N queueing networks with correlated arrivals. Perform Eval 52(2–4):137–152CrossRef
46.
47.
Neuts MF (1981) Matrix-geometric solutions in stochastic models. Johns Hopkins University Press, BaltimoreMATH
48.
O’Cinneide CA (1989) On nonuniqueness of representations of phase-type distributons. Stoch Models 5:322–330MathSciNet
49.
50.
51.
52.
Okamura H, Dohi T (2009) Faster maximum likelihood estimation algorithms for Markovian arrival processes. In: Proceedings of 6th international conference on quantitative evaluation of systems (QEST2009), pp 73–82
53.
Okamura H, Dohi T (2015) Mapfit: an R-based tool for PH/MAP parameter estimation. In: Proceedings of The 12th international conference on quantitative evaluation of systems (QEST2015), pp 105–112
54.
Okamura H, Dohi T, Trivedi KS (2009) Markovian arrival process parameter estimation with group data. IEEE/ACM Trans Netw 17(4):1326–1339CrossRef
55.
Okamura H, Dohi T, Trivedi KS (2011) A refined EM algorithm for PH distributions. Perform Eval 68(10):938–954CrossRef
56.
Okamura H, Dohi T, Trivedi KS (2013) Improvement of EM algorithm for phase-type distributions with grouped and truncated data. Appl Stoch Models Bus Ind 29(2):141–156MathSciNetCrossRefMATH
57.
Okamura H, Kishikawa H, Dohi T (2013) Application of deterministic annealing EM algorithm to MAP/PH parameter estimation. Telecommun Syst 54:79–90CrossRef
58.
Okamura H, Watanabe R, Dohi T (2014) Variational Bayes for phase-type distribution. Commun Stat Theory Methods 43(8):2013–2044MathSciNetMATH
59.
Olsson M (1996) Estimation of phase-type distributions from censored data. Scand J Stat 23:443–460MathSciNetMATH
60.
Osogami T, Harchol-Balter M (2006) Closed form solutions for mapping general distributions to minimal PH distributions. Perform Eval 63(6):524–552CrossRefMATH
61.
Panchenko A, Thümmler A (2007) Efficient phase-type fitting with aggregated traffic traces. Perform Eval 64:629–645CrossRef
62.
63.
Reinecke P, Kraub T, Wolter K (2012) Cluster-based fitting of phase-type distributions to empirical data. Comput Math Appl 64:3840–3851MathSciNetCrossRefMATH
64.
Roberts WJJ, Ephraim Y, Dieguez E (2006) On Rydén’s EM algorithm for estimating MMPPs. IEEE Signal Process Lett 13(6):373–376CrossRef
65.
66.
67.
Telek M, Heindl A (2002) Matching moments for acyclic discrete and continuos phase-type distributions of second order. Int J Simul Syst Sci Technol 3(3–4):47–57
68.
Telek M, Horváth G (2007) A minimal representation of Markov arrival processess and a moments matching method. Perform Eval 64(9–12):1153–1168CrossRef
69.
Thümmler A, Buchholz P, Telek M (2006) A novel approach for phase-type fitting with the EM algorithm. IEEE Trans Dependable Secure Comput 3(3):245–258CrossRef
70.
71.
Trivedi KS (2001) Probability and statistics with reliability, queueing, and computer sciences applications, 2nd edn. Wiley, New York
72.
van der Heijden MC (1988) On the three-moment approximation of a general distribution by a Coxian distribution. Probab Eng Inf Sci 2:257–261CrossRef
73.
van de Liefvoort A (1990) The moment problem for continuous distributions. Technical report, University of Missouri, WP-CM-1990-02, Kansas City
74.
Watanabe R, Okamura H, Dohi T (2012) An efficient MCMC algorithm for countinuous PH distributions. In: Laroque C, Himmelspach J, Pasupathy R, Rose O, Uhrmacher AM (eds) Proceedings of The 2012 winter simulation conference, p 12
75.
76.
Yamaguchi Y, Okamura H, Dohi T (2010) Variational Bayesian approach for estimating parameters of a mixture of Erlang distributions. Commun Stat Theory Methods 39(3):2333–2350MathSciNetCrossRefMATH
77.
Yoshihara T, Kasahara S, Takahashi Y (2001) Practical time-scale fitting of self-similar traffic with Markov modulated Poisson process. Telecommun Syst 17(1–2):185–211CrossRefMATH
Metadata
Title
Fitting Phase-Type Distributions and Markovian Arrival Processes: Algorithms and Tools
Authors
Hiroyuki Okamura
Tadashi Dohi
Copyright Year
2016
Book
Principles of Performance and Reliability Modeling and Evaluation

Print ISBN: 978-3-319-30597-4

Electronic ISBN: 978-3-319-30599-8

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-30599-8_3