8. Conclusions and future work

In this dissertation, we presented a set of modeling techniques for performance analysis of complex computer systems. In the following, we summarize the contributions of this dissertation.

• We proposed the D&C EM and D&C MM [79,80,23] parameterization techniques that approximate highly-variable data sets with PH distributions. First, we partition the data sets into subsets based on either their first moment (i.e., expected value) or their second moment (i.e., coefficient of variation), then we fit each subset into PH distributions using either the EM algorithm or the method of moments. The divide-and-conquer approach that we apply in both D&C EM and D&C MM increases their fitting accuracy and their computational efficiency. We evaluated the accuracy of D&C EM and D&C MM from the statistics and the queueing systems perspective.
• We captured long-range dependence in data sets using Hidden Markov models and PH distributions in a hierarchical fashion [86]. We evaluated the accuracy of this fitting method from the queueing system perspective.
• We prepared a survey on matrix-analytic techniques for solution of M/G/1-type, GI/M/1-type, and QBD processes [83]. We derived the matrix-analytic solution methods from first principles using stochastic complementation and illustrated the main concepts via simple examples.
• We developed ETAQA, a new aggregate matrix-analytic technique, that provides exact solutions for QBD, M/G/1-type, and GI/M/1-type e processes [21,22,81]. ETAQA computes an exact aggregate steady state probability distribution and a set of exact measures of interest. Detailed complexity analysis and experimental results demonstrate the computational efficiency and the numerical stability of the method.
• We developed and made available to the community a software tool, MAMSolver^8.1, which provides implementations of classic and recent matrix-analytic methods, including the ETAQA methodology, for the solution of QBD, GI/M/1-type, and M/G/1-type processes [82].
• We developed a new technique for the exact solution of a restricted class of GI/G/1-type Markov processes [85]. Such processes exhibit both M/G/1-type and GI/M/1-type patterns and cannot be solved exactly with existing techniques. The proposed methodology uses decomposition to separate the M/G/1-type and GI/M/1-type patterns, solves them independently, and aggregates the results to generate the final solution, i.e., the stationary probability vector.
• We demonstrated the applicability of our modeling techniques by evaluating the performance of load balancing policies in clustered Web servers. We proposed a size-based policy that assigns the incoming requests to the cluster based on their sizes [84].
• We proposed EQUILOAD, a load balancing policy in clustered Web servers [23]. EQUILOAD assigns each server of the cluster to serve a different pre-determined range of request sizes. Numerous experiments demonstrate that EQUILOAD outperforms traditional load balancing policies and improves user perceived performance.
• We improved EQUILOAD to adapt to the transient load conditions commonly experienced by clustered Web servers and proposed ADAPTLOAD [87]. ADAPTLOAD maintains good performance under conditions of transient overloads.