Compact Markov-modulated models for multiclass trace fitting

- We present the first paper on fitting the counting process of the marked Markov-modulated Poisson process.
- We develop techniques to exactly fit 2-state processes to empirical datasets.
- We develop search-based methods to approximately fit large processes to empirical datasets.
- A novel technique to compositionally define processes in terms of simpler 2-state processes is developed.
- Experimental results indicate that the proposed fitting methods provide accurate results.

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.