KPC-Toolbox: Simple Yet Effective Trace Fitting Using Markovian Arrival Processes

We present the KPC-Toolbox, a collection of MATLAB scripts for fitting workload traces into Markovian arrival processes (MAPs) in an automatic way. We first present detailed sensitivity analysis that builds intuition on which trace descriptors are most important for queueing. This sensitivity analysis stresses the importance of matching higher-order correlations (i.e., joint moments) of the process inter-arrival times rather than higher order moments of the distribution and provides guidance on the relative importance of different descriptors on queueing. Given that the MAP parameterization space can be very large, we focus on first determining the order of the smallest MAP that can fit the trace well, using the Bayesian information criterion (BIC) for determining the best order-accuracy tradeoff. Having determined the order of the target MAP, the KPC-Toolbox automatically derives a MAP that captures accurately the most essential features of the trace. Extensive experimentation illustrates the effectiveness of the KPC-Toolbox in fitting traces that are well-documented in the literature as very challenging to fit, showing that the KPC-Toolbox provides a simple and powerful solution to fitting accurately trace data into MAPs.