Adaptive control algorithms determine the end-to-end performance
of distributed systems, especially high-performance systems; for example,
networking systems have adaptive routing, congestion control, admission
control, etc. Any accurate performance prediction approach must capture
the transient phenomena, specifically, the time evolution of performance
measures while adapting to feedback, especially delayed feedback. It must
also capture the interaction of the various control algorithms, otherwise
stress conditions are avoided.
Time-dependent queueing systems are undoubtedly the natural modeling
tool. Their arrival and service rates can be functions of delayed system
state, and solving them yields transient responses to network and workload
changes. However these systems are not tractable by traditional approaches:
Simpler models (e.g. steady-state queueing models, fluid models, models
without workload) are more tractable but their accuracy is questionable.
experience with these approaches, including work on a popular routing
testbed called MaRS
(Maryland Routing Simulator), led us to the Z-iteration.
Analytical approaches cannot handle realistic networks features, including
most kinds of feedback.
Numerical solutions are unmanageable for realistic networks (because the
state space becomes enormous).
Discrete-event simulations are unmanageable for realistic networks (because
of number of scheduled events becomes enormous).
The Z-iteration is a numerical-analytical method that very efficiently
computes instantaneous probabilistic measures of time-dependent queueing
systems (e.g. blocking probability at time t, average queue size at time
t). It unifies three very different kinds of approximations, functional,
encapsulation, and decomposition, each providing enormous computational
approximation approximates instantaneous relationships between performance
measures by the corresponding steady-state relationships (e.g. blocking
probability at time t as a function of utilization at time t is approximated
by steady-state blocking probability as a function of steady-state utilization).
This reduces large multi-dimensional Chapmann-Kolmogorov equations to simple
one-dimensional flow equations.
Current version of the Z-iteration implements these approximations
for time-dependent multi-class multi-resource (MCMR) queues with (time-dependent)
Poisson arrivals and general service. We are extending this to networks
approximation represents a system by an ``interface'' of relationships
between instantaneous measures of the system. Given such an encapsulation
of a system, we can compute instantaneous performance measures of a larger
system containing the encapsulated system without ``opening up'' the encapsulated
approximation approximates multi-class multi-resource models by a collection
of loosely-coupled multi-class single-resource models. This again reduces
the dimensionality of the Chapmann-Kolmogorov equations.
Target System Prototyping
We refer to the system under evaluation as the target system. The
basic approach to evaluating the target system is to convert it to a time-dependent
MCMR queue which is then evaluated by the Z-iteration (in general, the
target system would be mapped to any system directly solvable by the Z-iteration).
The MCMR queue is driven by the target system workload and control algorithms.
The structure of the MCMR queue (i.e. classes, resources, rates) depends
on the structure of the target system (i.e. classes, resources, control
(Example: Consider an adaptive routing network with workload
defined in terms of classes, each specifying a source node, a destination
node, a packet arrival rate, and a packet service rate; the routing algorithm
chooses from among the several paths available for each class. This target
system can be converted to a MCMR queue with a resource for each link of
the network and a class for each pair of workload class and possible path.
Thus the arrival rate of a MCMR class depends on the arrival rate of its
target system class and the current routing state.)
At any time t, the prototyper maintains the following:
The evolution of the MCMR performance measures is obtained using Z-iteration
until the time of the next control update, at which point the control state
changes (as a function of the target system performance measures). This
in turn sets new MCMR arrival and service rates for the next Z-iteration
control state (state of the control algorithms)
target system arrival rates (part of target system specification)
MCMR arrival rates (inferred from target system arrival rates and control
MCMR performance measures
target system performance measures (inferred from the MCMR measures and
time of the next control algorithm update.
package implements the above evaluation method. It has the following:
A Z-iteration library
of functions for evaluating MCMR queues.
A simulation library
of functions for simulating MCMR queues. This simulator is provided
for validation purposes only; in general, it will take far more computation
time than the Z-iteration evaluator.
A common API
for the simulation and Z-iteration libraries. Thus an application can readily
switch between the two evaluation methods.
A collection of target
system models. Currently they are of connection-oriented flat and
hierarchical networks with dynamic routing, link scheduling, admission
control (and the resulting resource reservation). Each target workload
class represents a stream of connection requests with the following attributes:
source and destination node for the connection requests, rate at which
the requests are generated, traffic descriptors of the requests (eg, peak
and avg rates, burstiness), desired QoS of the requests (eg, end-to-end
delay/jitter of either statistical or deterministic flavor, maximum loss
probability), and duration of established connections.
An on-line network
evaluator of the above connection-oriented networks. The on-line evaluator
has a java applet for constructing target systems, a server (not an applet)
for doing Z-iteration evaluation, and a collection of predefined target
systems. It is best run using Sun's appletviewer, which comes with the
Java(tm) Development Kit.
The on-line network
evaluator (client only) is also available as a separate
You are welcome to
try the on-line
network evaluator through a web browser (Netscape
4.0 or higher).
The original version of
the Z-iteration along with simple applications can be found here.
An application to a
network with routing, admission, and scheduling control can be found here.
An application to a hierarchical
network with various state aggregation schemes can be found