Analysis and Synthesis of Pseudo-Periodic Job Arrivals in Grids: A Matching Pursuit Approach

Pseudo-periodicity is one of the basic job arrival patterns on data-intensive clusters and Grids. In this paper, a signal decomposition methodology called matching pursuit is applied for analysis and synthesis of pseudo-periodic job arrival processes. The matching pursuit decomposition is well localized both in time and frequency, and it is naturally suited for analyzing non-stationary as well as stationary signals. The stationarity of the processes can be quantitatively measured by permutation entropy, with which the relationship between stationarity and modeling complexity is excellently explained. Quantitative methods based on the power spectrum are also provided to measure the degree of periodicity present in the data. Matching pursuit is further shown to be able to extract patterns from signals, which is an attractive feature from a modeling perspective. Real world workload data from production clusters and Grids are used to empirically evaluate the proposed measures and methodologies.