The basic approaches to performance evaluation of computer
systems include analytical modeling, simulation, and measurements.
My work focuses on analytical modeling.
An example model is a multiclass multiserver queueing system
whose attributes include the system's workload in the form
of N job arrival processes each with
its own arrival rate, the system's resources
in the form of a queue and K servers each
with its own service rate,
and a service scheduling discipline.
arrival and service rates may be a function
of the current model state, and not all servers need be
activated at all times (where activation of more servers
improves the performance but may increase cost).
Given such models, common performance metrics of interest
include expected job response time, server utilization, throughput,
and so on.
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.
and complex models, these special structures are usually too
expensive to expose automatically
(as that may involve searching through a combinatorial number
My work on analytical modeling focuses on discovery of
special structure in models which results in
order(s) of magnitude improvement in computational efficiency.
We have developed Markovian models and efficient solutions of systems
that employ threshold-based techniques with hysteresis
behavior to dynamically adjust the amount of resources available for
job service [A4,
A threshold-based approach is useful in systems which
incur significant server setup, usage, and removal
costs. It is also a good approach to dynamic management of
a pool of resources between multiple workload classes using
the same system.
The hysteresis is needed
to guard against momentary fluctuations in workload.
For instance, such techniques are used in
Novell file servers in managing their buffer pool.
However, performance prediction for threshold-based systems
is often difficult as such systems exhibit
anomalous response time behavior, as observed in
our work as well as that of others.
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
(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),
(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,
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
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
show less than 1.5% spread between
upper and lower bounds with an order of magnitude improvement in
computational cost over the exact solution).
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
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
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.
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.
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
This work focuses on modeling and analysis of storage servers that serve a
variety of applications requesting video, image, audio, and
text data with vastly different performance and quality-of-service (QoS)
requirements as well as resource demand characteristics.
For instance, the QoS requirement of continuous media (CM) workload
(e.g., video) is to meet specific deadlines in data delivery with
high probability (e.g., greater than .99), while the non-CM
workload (e.g., images and text) requires fast response time with no errors.
Hence, we model multimedia servers which share resources dynamically
among the different types of workloads while satisfying their
We first designed a family of disk scheduling
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
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
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. Muntz1,
of using embedded Markov chains to analyze non-Markovian
It involves a combination of steady state and transient analysis.