IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v255y2016i3p822-833.html
   My bibliography  Save this article

Compact Markov-modulated models for multiclass trace fitting

Author

Listed:
  • Casale, Giuliano
  • Sansottera, Andrea
  • Cremonesi, Paolo

Abstract

Markov-modulated Poisson processes (MMPPs) are stochastic models for fitting empirical traces for simulation, workload characterization and queueing analysis purposes. In this paper, we develop the first counting process fitting algorithm for the marked MMPP (M3PP), a generalization of the MMPP for modeling traces with events of multiple types. We initially explain how to fit two-state M3PPs to empirical traces of counts. We then propose a novel form of composition, called interposition, which enables the approximate superposition of several two-state M3PPs without incurring into state space explosion. Compared to exact superposition, where the state space grows exponentially in the number of composed processes, in interposition the state space grows linearly in the number of composed M3PPs. Experimental results indicate that the proposed interposition methodology provides accurate results against artificial and real-world traces, with a significantly smaller state space than superposed processes.

Suggested Citation

  • Casale, Giuliano & Sansottera, Andrea & Cremonesi, Paolo, 2016. "Compact Markov-modulated models for multiclass trace fitting," European Journal of Operational Research, Elsevier, vol. 255(3), pages 822-833.
    • Handle: RePEc:eee:ejores:v:255:y:2016:i:3:p:822-833
    DOI: 10.1016/j.ejor.2016.06.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716304258
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.06.005?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Van Houdt, Benny, 2012. "Analysis of the adaptive MMAP[K]/PH[K]/1 queue: A multi-type queue with adaptive arrivals and general impatience," European Journal of Operational Research, Elsevier, vol. 220(3), pages 695-704.
    2. Bodrog, L. & Heindl, A. & Horváth, G. & Telek, M., 2008. "A Markovian canonical form of second-order matrix-exponential processes," European Journal of Operational Research, Elsevier, vol. 190(2), pages 459-477, October.
    3. He, Qi-Ming & Neuts, Marcel F., 1998. "Markov chains with marked transitions," Stochastic Processes and their Applications, Elsevier, vol. 74(1), pages 37-52, May.
    4. Lothar Breuer, 2002. "An EM Algorithm for Batch Markovian Arrival Processes and its Comparison to a Simpler Estimation Procedure," Annals of Operations Research, Springer, vol. 112(1), pages 123-138, April.
    5. Peter Buchholz & Miklós Telek, 2013. "On minimal representations of Rational Arrival Processes," Annals of Operations Research, Springer, vol. 202(1), pages 35-58, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Benjamin Avanzi & Greg Taylor & Bernard Wong & Alan Xian, 2020. "Modelling and understanding count processes through a Markov-modulated non-homogeneous Poisson process framework," Papers 2003.13888, arXiv.org, revised May 2020.
    2. Avanzi, Benjamin & Taylor, Greg & Wong, Bernard & Xian, Alan, 2021. "Modelling and understanding count processes through a Markov-modulated non-homogeneous Poisson process framework," European Journal of Operational Research, Elsevier, vol. 290(1), pages 177-195.
    3. Yera, Yoel G. & Lillo, Rosa E. & Ramírez-Cobo, Pepa, 2019. "Fitting procedure for the two-state Batch Markov modulated Poisson process," European Journal of Operational Research, Elsevier, vol. 279(1), pages 79-92.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Peter Buchholz & Jan Kriege, 2017. "Fitting correlated arrival and service times and related queueing performance," Queueing Systems: Theory and Applications, Springer, vol. 85(3), pages 337-359, April.
    2. Yera, Yoel G. & Lillo, Rosa E. & Ramírez-Cobo, Pepa, 2019. "Fitting procedure for the two-state Batch Markov modulated Poisson process," European Journal of Operational Research, Elsevier, vol. 279(1), pages 79-92.
    3. Horváth, Gábor, 2015. "Efficient analysis of the MMAP[K]/PH[K]/1 priority queue," European Journal of Operational Research, Elsevier, vol. 246(1), pages 128-139.
    4. Ramírez-Cobo, Pepa & Carrizosa, Emilio & Lillo, Rosa E., 2021. "Analysis of an aggregate loss model in a Markov renewal regime," Applied Mathematics and Computation, Elsevier, vol. 396(C).
    5. Yutaka Sakuma & Onno Boxma & Tuan Phung-Duc, 2021. "An M/PH/1 queue with workload-dependent processing speed and vacations," Queueing Systems: Theory and Applications, Springer, vol. 98(3), pages 373-405, August.
    6. Marcel F. Neuts & Jian-Min Li, 1999. "Point Processes Competing for Runs: A New Tool for their Investigation," Methodology and Computing in Applied Probability, Springer, vol. 1(1), pages 29-53, July.
    7. Rodríguez, Joanna & Lillo, Rosa E. & Ramírez-Cobo, Pepa, 2015. "Failure modeling of an electrical N-component framework by the non-stationary Markovian arrival process," Reliability Engineering and System Safety, Elsevier, vol. 134(C), pages 126-133.
    8. Qi-Ming He & Jiandong Ren, 2016. "Analysis of a Multivariate Claim Process," Methodology and Computing in Applied Probability, Springer, vol. 18(1), pages 257-273, March.
    9. Hautphenne, Sophie & Fackrell, Mark, 2014. "An EM algorithm for the model fitting of Markovian binary trees," Computational Statistics & Data Analysis, Elsevier, vol. 70(C), pages 19-34.
    10. Dimitri frosinin & L. Breuer, 2006. "Threshold policies for controlled retrial queues with heterogeneous servers," Annals of Operations Research, Springer, vol. 141(1), pages 139-162, January.
    11. Joanna Rodríguez & Rosa E. Lillo & Pepa Ramírez-Cobo, 2016. "Nonidentifiability of the Two-State BMAP," Methodology and Computing in Applied Probability, Springer, vol. 18(1), pages 81-106, March.
    12. Ivo Adan & Brett Hathaway & Vidyadhar G. Kulkarni, 2019. "On first-come, first-served queues with two classes of impatient customers," Queueing Systems: Theory and Applications, Springer, vol. 91(1), pages 113-142, February.
    13. Andrzej Chydzinski & Pawel Mrozowski, 2016. "Queues with Dropping Functions and General Arrival Processes," PLOS ONE, Public Library of Science, vol. 11(3), pages 1-23, March.
    14. Miklós Telek, 2022. "The two-matrix problem," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 265-267, April.
    15. Lin, Lei & Wang, Qian & Sadek, Adel W., 2014. "Border crossing delay prediction using transient multi-server queueing models," Transportation Research Part A: Policy and Practice, Elsevier, vol. 64(C), pages 65-91.
    16. Pepa Ramírez-Cobo & Rosa E. Lillo, 2012. "New Results About Weakly Equivalent MAP 2 and MAP 3 Processes," Methodology and Computing in Applied Probability, Springer, vol. 14(3), pages 421-444, September.
    17. A. Gómez-Corral & M. E. Martos, 2009. "Marked Markovian Arrivals in a Tandem G-Network with Blocking," Methodology and Computing in Applied Probability, Springer, vol. 11(4), pages 621-649, December.
    18. B. Houdt & J. Velthoven & C. Blondia, 2008. "QBD Markov chains on binomial-like trees and its application to multilevel feedback queues," Annals of Operations Research, Springer, vol. 160(1), pages 3-18, April.
    19. Karumbathil Rasmi & Machuveettil Joseph Jacob & Alexander S. Rumyantsev & Achyutha Krishnamoorthy, 2021. "A Multi-Server Heterogeneous Queuing-Inventory System with Class-Dependent Inventory Access," Mathematics, MDPI, vol. 9(9), pages 1-23, May.
    20. Yera, Yoel G. & Lillo, Rosa E. & Nielsen, Bo F. & Ramírez-Cobo, Pepa & Ruggeri, Fabrizio, 2021. "A bivariate two-state Markov modulated Poisson process for failure modeling," Reliability Engineering and System Safety, Elsevier, vol. 208(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:255:y:2016:i:3:p:822-833. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.