Modeling and Performance Evaluation Methodology

Performance evaluation of real systems is complex, suffers from scalability problems (such as the so-called ``state space explosion'' problem), and usually requires advanced model solution techniques. Often, such techniques are based on exploitation of ``special structure'' in the models. With large and complex models, these special structures are usually too expensive to expose automatically (as that may involve searching through a combinatorial number of permutations). My work on analytical modeling focuses on discovery of special structure in models which results in order(s) of magnitude improvement in computational efficiency.

Threshold-based Systems

There has been much interest in developing efficient performance evaluation techniques for such systems. However, past results have been obtained only for fairly restricted models which include limitations on one or more of the following: (a) number of servers in the system (often restricted to 2), (b) size of the waiting room, (c) heterogeneity of servers, (d) number of job classes (usually 1), and (e) absence of hysteresis. We have developed a divide-and-conquer type methodology (using stochastic complementation) which allows extremely efficient computation of performance metrics for a variety of threshold-based models with hysteresis without such restrictions, handling heterogeneous servers, bulk arrivals, non-instantaneous server activation, and multi-class workloads, all without restrictions on the number of servers or the size of the waiting room.

For a variety of single-class models [A4, D10] we derived either: (1) an exact closed-form expression, or (2) an exact algorithmic solution, or (3) provable (through sample path analysis) and tight performance bounds, which, for all practical purposes, is as good as having an exact solution (e.g., experiments in [D10] show less than 1.5% spread between upper and lower bounds with an order of magnitude improvement in computational cost over the exact solution). Moreover, allowing non-instantaneous resource activation in a model, while difficult to analyze accurately, is important because activation time is often the distinguishing characteristic of a resource management policy. No other work addresses this problem with more than 2 servers.

The efficiency is obtained by breaking the model into smaller pieces, solving each piece separately, and then using these solutions in constructing the exact solution to the original model. For cases where it was not possible to apply the divide-and-conquer approach directly, we developed modified models which were suited for the divide-and-conquer approach and produced provable and tight bounds on performance metrics of the original model [D10]. Due to the divide-and-conquer nature of our approach, the reduction in computation grows as the number of servers in the system grows.

Based on the success with single-class models, we have developed an efficient method for multi-class models [D20]. In systems with multiple job classes it is desirable to find good approaches to sharing resources without statically partitioning them among the job classes. Threshold-based techniques constitute one category of such approaches. There have been no prior analytical results for the multi-class version of this model, which corresponds to an important characteristic of real systems.

Solving this model exactly is difficult because it is infinite in multiple dimensions and appears to lack sufficient structure. We developed [D20] an approximate iterative solution method. This method ``breaks up'' the original N-class model into N single class models, which are ``coupled'' through a set of blocking probabilities that express the interaction between classes. Empirical comparison against simulation indicates that this method is fast and fairly accurate. Most of our test cases are within 5% of the simulation results with more than two orders of magnitude improvement in computation time. Although this is an approximate solution technique, our experiments indicate that good threshold settings result in much higher performance improvements (e.g., 50%) than the loss in accuracy due to the approximation. Hence, our solution technique is a promising approach to evaluating multi-class threshold-based systems.

Mixed-workload Multimedia Systems

We first designed a family of disk scheduling algorithms [A12, D16] in order to explore the possible design choices and tradeoffs of interest. Such algorithms (ours as well as those of other researchers) often use cycle-based scheduling of the CM workload which results in models that are non-Markovian (because each chunk of CM workload must be completed by the end of a specified time unit) and non-work-conserving (because early service carries penalties in the form of increased buffer space requirements). These algorithms mostly differ in: (1) how they ``interleave'' service of CM and non-CM workloads, (2) how they order the service of non-CM requests, and (3) how work-conserving they are with respect to CM workload.

We developed a family of analytical non-Markovian models which represent this class of scheduling algorithms and have tractable analytical solutions [A5]. Prior approaches to modeling such systems include M/G/1 queue with vacation models. Our model, which can be viewed as a polling-type system, more faithfully captures the behavior of scheduling algorithms, is extensible to a wider class of such algorithms, and allows computation of a larger number of important performance metrics, for both types of workloads.

In this work [A5], each scheduling algorithm being modeled is captured through construction of appropriate service time distributions for CM and non-CM workloads, where the CM workload distribution is then matched with an Erlang and the non-CM with a load-dependent exponential. (Parameters for these distributions can be obtained by benchmarking the disk and extracting the seek function, transfer times, and so on.) Hence, all the events in the model are exponential, except for the deterministic time unit during which a chunk of the CM workload should be completed. Our solution of the models is based on an existing methodology, by de Souza e Silva, H.R. Gail, and R.R. Muntz¹, of using embedded Markov chains to analyze non-Markovian stochastic processes. It involves a combination of steady state and transient analysis.