article

Markovian arrival process parameter estimation with group data

Authors:

Hiroyuki Okamura,

Tadashi Dohi,

Kishor S. TrivediAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 17, Issue 4

Pages 1326 - 1339

https://doi.org/10.1109/TNET.2008.2008750

Published: 01 August 2009 Publication History

Get Access

Abstract

This paper addresses a parameter estimation problem of Markovian arrival process (MAP). In network traffic measurement experiments, one often encounters the group data where arrival times for a group are collected as one bin. Although the group data are observed in many situations, nearly all existing estimation methods for MAP are based on nongroup data. This paper proposes a numerical procedure for fitting a MAP and a Markov-modulated Poisson process (MMPP) to group data. The proposed algorithm is based on the expectation-maximization (EM) approach and is a natural but significant extension of the existing EM algorithms to estimate parameters of the MAP and MMPP. Specifically for the MMPP estimation, we provide an efficient approximation based on the proposed EM algorithm. We examine the performance of proposed algorithms via numerical experiments and present an example of traffic analysis with real traffic data.

References

[1]

D. M. Lucantoni, K. S. Meier-Hellstern, and M. F. Neuts, "A single-server queue with server vacations and a class of non-renewal arrival processes," Adv. Appl. Prob., vol. 22, pp. 676-705, 1990.

Crossref

Google Scholar

[2]

M. F. Neuts, Structured Stochastic Matrices of M/G/1 Type and Their Applications. New York: Marcel Dekker, 1989.

Google Scholar

[3]

T. Takine, Y. Matsumoto, T. Suda, and T. Hasegawa, "Mean waiting times in nonpreemptive priority queues with Markovian arrival and i.i.d. service processes," Performance Evaluation, vol. 20, pp. 131-149, 1994.

Digital Library

Google Scholar

[4]

Y. Cao, H. Sun, and K. S. Trivedi, "Performance analysis of reservation media-access protocol with access and serving queues under bursty traffic in GPRS/EGPRS," IEEE Trans. Veh. Technol., vol. 52, pp. 1627-1641, Jun. 2003.

Crossref

Google Scholar

[5]

Y. Cao, H. Sun, and K. S. Trivedi, "The effect of access delay in capacity-on-demand access over a wireless link under bursty packet-switched data," Performance Evaluation, vol. 57, pp. 69-87, 2004.

Digital Library

Google Scholar

[6]

G. Bolch, S. Greiner, H. de Meer, and K. S. Trivedi, Queueing Networks and Markov Chains: Modeling and Performance Evaluation With Computer Science Applications, 2nd ed. Hoboken: Wiley, 2006.

Digital Library

Google Scholar

[7]

S. Asmussen and G. Koole, "Marked point processes as limits of Markovian arrival streams," J. Appl. Prob., vol. 30, pp. 365-372, 1993.

Crossref

Google Scholar

[8]

W. Leland, M. Taqqu, W. Willinger, and D. Wilson, "On the self-similar nature of Ethernet traffic (extended version)," IEEE/ACM Trans. Netw., vol. 2, no. 1, pp. 1-15, Feb. 1994.

Digital Library

Google Scholar

[9]

A. Erramilli and P. R. Singh, "Chaotic maps as models of packet traffic," in Proc. 14th ITC, 1994, pp. 329-338.

Google Scholar

[10]

I. Norros, "On the use of fractional Brownian motion in the theory of connectionless networks," IEEE J. Sel. Areas Commun., vol. 13, no. 6, pp. 953-962, Aug. 1995.

Digital Library

Google Scholar

[11]

A. Erramilli, O. Narayan, and W. Willinger, Fractal Queueing Models, in Frontiers in Queueing, J. H. Dshalalow, Ed. Boca Raton, FL: CRC Press, 1997, pp. 245-269.

Digital Library

Google Scholar

[12]

S. Andersson and T. Rydén, "Maximum likelihood estimation of a structured MMPP with applications to traffic modeling," presented at the 13th ITC Specialist Sem. Meas. Modeling of IP Traffic, 2000.

Google Scholar

[13]

A. Klemm, C. Lindemann, and M. Lohmann, "Traffic modeling of IP networks using the batch Markovian arrival process," Performance Evaluation, vol. 54, pp. 149-173, 2003.

Digital Library

Google Scholar

[14]

H. Heffes and D. M. Lucantoni, "A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance," IEEE J. Sel. Areas Commun., vol. SAC-4, no. 6, pp. 856-868, Sep. 1986.

Digital Library

Google Scholar

[15]

A. T. Andersen and B. F. Nielsen, "A Markovian approach for modeling packet traffic with long-range dependence," IEEE J. Sel. Areas Commun., vol. 16, no. 5, pp. 719-732, Jun. 1998.

Digital Library

Google Scholar

[16]

T. Yoshihara, S. Kasahara, and Y. Takahashi, "Practical time-scale fitting of self-similar traffic with Markov modulated Poisson process," Telecommun. Syst., vol. 17, no. 1-2, pp. 185-211, 2001.

Digital Library

Google Scholar

[17]

K. Mitchell and A. van de Liefvoort, "Approximation models of feed-forward G/G/1/N queueing networks with correlated arrivals," Performance Evaluation, vol. 51, no. 2-4, pp. 137-152, 2003.

Digital Library

Google Scholar

[18]

A. P. Dempster, N. M. Laird, and D. B. Rubin, "Maximum likelihood from incomplete data via the EM algorithm," J. Roy. Stat. Soc. B, vol. B-39, pp. 1-38, 1977.

Google Scholar

[19]

C. F. J. Wu, "On the convergence properties of the EM algorithm," Ann. Stat., vol. 11, pp. 95-103, 1983.

Crossref

Google Scholar

[20]

L. E. Baum, T. Petrie, G. Soules, and N. Weiss, "A maximization technique occurring in the statistical analysis of probabilistic function of Markov chains," Ann. Math. Stat., vol. 41, no. 1, pp. 164-171, 1970.

Crossref

Google Scholar

[21]

L. Deng and J. Mark, "Parameter estimation for Markov modulated Poisson processes via the EM algorithm with time discretization," Telecommun. Syst., vol. 1, pp. 321-338, 1993.

Digital Library

Google Scholar

[22]

S. Asmussen, O. Nerman, and M. Olsson, "Fitting phase-type distributions via the EM algorithm," Scandinavian. J. Stat., vol. 23, no. 4, pp. 419-441, 1996.

Google Scholar

[23]

T. Rydn, "An EM algorithm for estimation in Markov-modulated Poisson processes," Computational Stat. & Data Anal., vol. 21, no. 4, pp. 431-447, 1996.

Digital Library

Google Scholar

[24]

D. M. Lucantoni, "New results on the single server queue with a batch Markovian arrival process," Stochastic Models, vol. 7, pp. 1-46, 1991.

Crossref

Google Scholar

[25]

L. Breuer, "An EM algorithm for batch Markovian arrival processes and its comparison to a simpler estimation procedure," Ann. Operations Research, vol. 112, pp. 123-138, 2002.

Crossref

Google Scholar

[26]

W. J. J. Roberts, Y. Ephraim, and E. Dieguez, "On Rydén's EM algorithm for estimating MMPPs," IEEE Signal Process. Lett., vol. 13, no. 6, pp. 373-376, Jun. 2006.

Crossref

Google Scholar

[27]

P. Buchholz, "An EM-algorithm for MAP fitting from real traffic data," in Comput. Performance Evaluation Modelling Techniques and Tools, LNCS 2794, P. Kemper and W. H. Sers, Eds. New York: Springer-Verlag, 2003, pp. 218-236.

Google Scholar

[28]

P. Buchholz and A. Panchenko, "A two-step EM-algorithm for MAP fitting," in Proc. 19th Int. Symp. Comput. Inform. Sci., LNCS 3280., 2004, pp. 217-227.

Google Scholar

[29]

G. Horváth, P. Buchholz, and M. Telek, "A MAP fitting approach with independent approximation of the inter-arrival time distribution and the lag correlation," in Proc. 2nd Int. Conf. Quantitative Evaluation of Syst., 2005, pp. 124-133.

Digital Library

Google Scholar

[30]

J. K. Muppala, R. Fricks, and K. S. Trivedi, "Techniques for system dependability evaluation," in Computational Probability, W. K. Grassmann, Ed. Norwell, MA: Kluwer, 2000, pp. 445-479.

Google Scholar

[31]

A. L. Reibman and K. S. Trivedi, "Numerical transient analysis of Markov models," Comput. Oper. Res., vol. 15, no. 1, pp. 19-36, 1988.

Digital Library

Google Scholar

[32]

H. Akaike, B. N. Petrov and F. Csaki, Eds., "Information theory and an extension of the maximum likelihood principle," in Proc. 2nd Int. Symp. Inform. Theory, 1973, pp. 267-281.

Google Scholar

[33]

M. Telek and G. Horváth, "A minimal representation of Markov arrival processess and a moments matching method," Performance Evaluation , vol. 64, no. 9-12, pp. 1153-1168, 2007.

Digital Library

Google Scholar

Cited By

View all

Nezhel’skaya LKeba A(2021)Optimal State Estimation of a Generalized MAP Event Flow with an Arbitrary Number of StatesAutomation and Remote Control10.1134/S000511792105005682:5(798-811)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1134/S0005117921050056
Aceto GBovenzi GCiuonzo DMontieri APersico VPescapé A(2021)Characterization and Prediction of Mobile-App Traffic Using Markov ModelingIEEE Transactions on Network and Service Management10.1109/TNSM.2021.305138118:1(907-925)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1109/TNSM.2021.3051381
Almousa SHorváth GTelek M(2021)EM Based Parameter Estimation for Markov Modulated Fluid Arrival ProcessesPerformance Engineering and Stochastic Modeling10.1007/978-3-030-91825-5_14(226-242)Online publication date: 9-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-91825-5_14
Show More Cited By

Index Terms

Recommendations

Discrete-time single-server finite-buffer queues under discrete Markovian arrival process with vacations

This paper treats a discrete-time single-server finite-buffer exhaustive (single- and multiple-) vacation queueing system with discrete-time Markovian arrival process (D-MAP). The service and vacation times are generally distributed random variables and ...
Stationary distributions and optimal control of queues with batch Markovian arrival process under multiple adaptive vacations

We consider an infinite-buffer single server queue with batch Markovian arrival process (BMAP) and exhaustive service discipline under multiple adaptive vacation policy. That is, the server serves until system emptied and after that server takes a ...
Computational analysis of a Markovian queueing system with geometric mean-reverting arrival process

In the queueing literature, an arrival process with random arrival rate is usually modeled by a Markov-modulated Poisson process (MMPP). Such a process has discrete states in its intensity and is able to capture the abrupt changes among different ...

Reviews

Reviewer: Panamalai R. Parthasarathy

The Markovian arrival process (MAP) is widely used for probabilistic analysis of communication network traffic. An important problem in MAP-based traffic modeling is estimating model parameters to fit observed traffic data. So far, no estimation procedure has been available for estimating group data. In this paper, Okamura, Dohi, and Trivedi propose two expectation-maximization (EM) algorithms for fitting the MAP and the Markov modulated Poisson process (MMPP) with generalized group data. The proposed EM algorithm can perform the maximum likelihood estimation when exact arrival times are not known. Moreover, in order to deal with the data that consists of many arrival observations in one bin, they propose the approximate EM algorithm for the MMPP special case. The numerical results point out that the maximum number of arrivals strongly affects the computation time of the EM algorithm with group data and that the length of step size for group data is a significant factor in determining the accuracy and the computation time in both exact and approximate EM algorithms. The authors also present an application of the proposed EM algorithm to real traffic data. The two methods proposed in this paper should be useful for estimating time series data that arises in a variety of situations, including Internet traffic. However, the size of MAP is limited, due to the computational effort needed. Many phases are necessary to accurately fit the MAP to the trace data with long-range dependence. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 4

August 2009

337 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 August 2009

Revised: 11 September 2007

Received: 30 November 2006

Published in TON Volume 17, Issue 4

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
346
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nezhel’skaya LKeba A(2021)Optimal State Estimation of a Generalized MAP Event Flow with an Arbitrary Number of StatesAutomation and Remote Control10.1134/S000511792105005682:5(798-811)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1134/S0005117921050056
Aceto GBovenzi GCiuonzo DMontieri APersico VPescapé A(2021)Characterization and Prediction of Mobile-App Traffic Using Markov ModelingIEEE Transactions on Network and Service Management10.1109/TNSM.2021.305138118:1(907-925)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1109/TNSM.2021.3051381
Almousa SHorváth GTelek M(2021)EM Based Parameter Estimation for Markov Modulated Fluid Arrival ProcessesPerformance Engineering and Stochastic Modeling10.1007/978-3-030-91825-5_14(226-242)Online publication date: 9-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-91825-5_14
de Gunst MKnapik BMandjes MSollie B(2019)Parameter estimation for a discretely observed population process under Markov-modulationComputational Statistics & Data Analysis10.1016/j.csda.2019.06.008140:C(88-103)Online publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1016/j.csda.2019.06.008
Dong FWu KSrinivasan V(2017)Copula Analysis of Temporal Dependence Structure in Markov Modulated Poisson Process and Its ApplicationsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/30892542:3(1-28)Online publication date: 29-Jun-2017
https://dl.acm.org/doi/10.1145/3089254
(2016)Analytical issues regarding the lack of identifiability of the non-stationary M A P 2Performance Evaluation10.1016/j.peva.2016.06.008102:C(1-20)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.peva.2016.06.008
Xiong BYang KZhao JLi WLi K(2016)Performance evaluation of OpenFlow-based software-defined networks based on queueing modelComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2016.03.005102:C(172-185)Online publication date: 19-Jun-2016
https://dl.acm.org/doi/10.1016/j.comnet.2016.03.005
Kriege JBuchholz P(2014)PH and MAP Fitting with Aggregated Traffic TracesProceedings of the 17th International GI/ITG Conference on Measurement, Modelling, and Evaluation of Computing Systems and Dependability and Fault Tolerance - Volume 837610.1007/978-3-319-05359-2_1(1-15)Online publication date: 17-Mar-2014
https://dl.acm.org/doi/10.1007/978-3-319-05359-2_1
Amador JArtalejo J(2013)Modeling computer virus with the BSDE approachComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2012.09.01457:1(302-316)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1016/j.comnet.2012.09.014
Okamura HKishikawa HDohi T(2013)Application of deterministic annealing EM algorithm to MAP/PH parameter estimationTelecommunications Systems10.1007/s11235-013-9717-y54:1(79-90)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1007/s11235-013-9717-y
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Discrete-time single-server finite-buffer queues under discrete Markovian arrival process with vacations

Stationary distributions and optimal control of queues with batch Markovian arrival process under multiple adaptive vacations

Computational analysis of a Markovian queueing system with geometric mean-reverting arrival process

Reviews

Access critical reviews of Computing literature here