Computing Publications

Publications Home » Trace Data Characterization and F...

Trace Data Characterization and Fitting for Markov Modeling

Giuliano Casale, Eddy Zheng Zhang, Evgenia Smirni

Journal Article
Perform. Eval.
Volume 67
Issue 2
February, 2010
DOI 10.1016/j.peva.2009.09.003

We propose a trace fitting algorithm for Markovian Arrival Processes (MAPs) that

can capture statistics of any order of interarrival times between measured events.

By studying real traffic and workload traces often used in performance evaluation

studies, we show that matching higher order statistical properties, in addition to

first and second order descriptors, results in increased queueing prediction accuracy

with respect to algorithms that only match the mean, the coefficient of variation,

and the autocorrelations of the trace. This result supports the approach of modeling

traces by the interarrival time process instead of the counting process that is more

frequently used in previous work.

We proceed by first characterizing the general properties of MAPs using a spectral

approach. Based on this result, we show how different MAPs can be combined to-

gether using Kronecker products to define a larger MAP with predefined properties

of interarrival times. We then devise an algorithm that is based on this Kronecker

composition and can accurately fit data traces. This MAP fitting algorithm uses

nonlinear optimization that can be customized to fit an arbitrary number of mo-

ments and to meet the desired cost-accuracy tradeoff. Numerical results of the fitting

algorithm on real data, such as the Bellcore Aug89 trace and a Seagate disk drive

trace, indicate that the proposed fitting technique achieves increased prediction

accuracy with respect to other state-of-the-art fitting methods.

PDF of full publication (1.3 megabytes)
(need help viewing PDF files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.