| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Novel Approach for Phase-Type Fitting with the EM Algorithm
July-September 2006 (vol. 3 no. 3)
pp. 245-258
The representation of general distributions or measured data by phase-type distributions is an important and nontrivial task in analytical modeling. Although a large number of different methods for fitting parameters of phase-type distributions to data traces exist, many approaches lack efficiency and numerical stability. In this paper, a novel approach is presented that fits a restricted class of phase-type distributions, namely, mixtures of Erlang distributions, to trace data. For the parameter fitting, an algorithm of the expectation maximization type is developed. This paper shows that these choices result in a very efficient and numerically stable approach which yields phase-type approximations for a wide range of data traces that are as good or better than approximations computed with other less efficient and less stable fitting methods. To illustrate the effectiveness of the proposed fitting algorithm, we present comparative results for our approach and two other methods using six benchmark traces and two real traffic traces as well as quantitative results from queueing analysis.
[1] 245 S. Asmussen, O. Nerman, and M. Olsson, “Fitting Phase-Type Distributions via the EM Algorithm,” Scandinavian J. Statistics, vol. 23, pp. 419-441, 1996.[2] A. Bobbio, A. Horváth, M. Scarpa, and M. Telek, “Acyclic Discrete Phase Type Distributions: Properties and a Parameter Estimation Algorithm,” Performance Evaluation, vol. 54, pp. 1-32, 2003.[3] A. Bobbio and M. Telek, “A Benchmark for Estimation Algorithms: Results for Acyclic-PH,” Stochastic Models, vol. 10, pp. 661-677, 1994.[4] P. Buchholz, “An EM-Algorithm for MAP Fitting from Real Traffic Data,” Proc. Int'l Conf. Computer Performance Evaluation— Modelling Techniques and Tools (TOOLS '03), pp. 218-236, 2003.[5] A. Cumani, “On the Canonical Representation of Homogeneous Markov Processes Modeling Failure— Time Distributions,” J. Microelectronics and Reliability, vol. 22, pp. 583-602, 1982.[6] A.P. Dempster, N.M. Laird, and D.B. Rubin, “Maximum Likelihood from Incomplete Data via the EM Algorithm,” J. Royal Statistical Soc., vol. 39, pp. 1-38, 1977.[7] A. Edelman and H. Murakami, “Polynomial Roots from Companion Matrix Eigenvalues,” Math. of Computation, vol. 64, pp. 763-776, 1995.[8] R. El Abdouni Khayari, R. Sadre, and B.R. Haverkort, “Fitting World-Wide Web Request Traces with the EM-Algorithm,” Performance Evaluation, vol. 52, pp. 175-191, 2003.[9] Y. Fang, “Hyper-Erlang Distribution Model and Its Application in Wireless Mobile Networks,” Wireless Networks, vol. 7, pp. 211-219, 2001.[10] A. Feldmann and W. Whitt, “Fitting Mixtures of Exponentials to Long-Tail Distributes to Analyze Network Performance Models,” Performance Evaluation, vol. 31, pp. 245-258, 1998.[11] B.R. Haverkort, “Markovian Models for Performance and Dependability Modeling,” Proc. Conf. Formal Methods and Performance Analysis (FMPA '00), pp. 38-83, 2001.[12] G-FIT Software, ls4-www.cs.uni-dortmund.de/homethummler, 2005.[13] A. Horváth and M. Telek, “Markovian Modeling of Real Data Traffic: Heuristic Phase Type and MAP Fitting of Heavy Tailed and Fractal Like Samples,” Proc. Conf. Evaluation of Complex Systems: Techniques and Tools (Performance '02), pp. 405-434, 2002.[14] A. Horváth and M. Telek, “Phfit: A General Phase-Type Fitting Tool,” Proc. Int'l Conf. Computer Performance Evaluation— Modelling Techniques and Tools (TOOLS '02), T. Fields, P.G. Harrison, J. Bradley, and U. Harder, eds., pp. 82-91, 2002.[15] M.A. Johnson, “Selecting Parameters of Phase Distributions: Combining Nonlinear Programming, Heuristics, and Erlang Distributions,” ORSA J. Computing, vol. 5, pp. 69-83, 1993.[16] M.A. Johnson and M.R. Taaffe, “The Denseness of Phase Distributions,” Purdue School of Industrial Eng. Research Memoranda, no. 88-20, 1988.[17] M.A. Johnson and M.R. Taaffe, “Matching Moments to Phase Distributions: Mixtures of Erlang Distributions of Common Order,” Stochastic Models, vol. 5, pp. 711-743, 1989.[18] M.A. Johnson and M.R. Taaffe, “Matching Moments to Phase Distributions: Nonlinear Programming Approaches,” Stochastic Models, vol. 6, pp. 259-281, 1990.[19] T. Krishnan and G.J. McLachlan, The EM Algorithm and Extensions. John Wiley and Sons, 1997.[20] A. Lang and J.L. Arthur, “Parameter Approximation for Phase-Type Distributions. Matrix Analytical Methods in Stochastic Models,” Lecture Notes in Pure and Applied Math., vol. 183, pp. 151-206, 1997.[21] A. Mandelbaum, A. Sakov, and S. Zeltyn, “Empirical Analysis of a Call Center,” technical report, Technion, Israel Inst. of Tech nology, 2000.[22] S. Resnick, “Modeling Data Networks,” Technical Report TR-1345, School of Operations Research and Industrial Eng., Cornell Univ., 2002.[23] A. Riska, V. Diev, and E. Smirni, “An EM-Based Technique for Approximating Long-Tailed Data Sets with PH Distributions,” Performance Evaluation, vol. 55, pp. 147-164, 2004.[24] L. Schmickler, “MEDA: Mixed Erlang Distributions as Phase-Type Representations of Empirical Distribution Functions,” Stochastic Models, vol. 8, pp. 131-156, 1992.[25] K.S. Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, second ed. John Wiley and Sons, 2002.
Index Terms:
Performance analysis and design aids, Markov processes, traffic modeling, communication networks, hyper-Erlang distributions.
Citation:
Axel Th?mmler, Peter Buchholz, Mikl? Telek, "A Novel Approach for Phase-Type Fitting with the EM Algorithm," IEEE Transactions on Dependable and Secure Computing, vol. 3, no. 3, pp. 245-258, July-Sept. 2006, doi:10.1109/TDSC.2006.27
