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:
The functional
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.
The encapsulation
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
system.
The decomposition
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.
(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 Z-prototyper 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
package.
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
here.