Z-iteration:

Fast Evaluation of Large Adaptive Networks

Last Updated: December 15, 1999
 

Z-iteration computes the time evolution of instantaneous ensemble metrics (e.g., average queue size at time t) of large adaptive distributed systems at a cost several orders cheaper than simulation. It uses novel approximation techniques to numerically solve time-dependent queuing models. Comparison against simulations confirm its accuracy and speed. Click here for an overview. Z-iteration methods have been implemented for Integrated-services connection-oriented networks (details and results). TCP/IP networks (details and results).   Z-iteration methods are being developed for other areas, including integrated-sevices TCP/IP networks on-line evaluation for network control on-line distributed evaluation for federated control   Papers  Software  NetSolver : Z-iteration implementation for TCP/IP networks (March 23, 1999). Z-prototyper : Z-iteration implementation for connection-oriented networks (1997).

Overview

• 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:
• 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).
Our past experience with these approaches, including work on a popular routing testbed called MaRS (Maryland Routing Simulator), led us to the Z-iteration. 
 
• Z-iteration computes instantaneous ensemble metrics of time-dependent queueing systems (e.g. blocking probability at time t, average queue size at time t) by making use of three very different kinds of approximations, functional, encapsulation, and decomposition, each providing enormous computational savings:

 
• 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, either numerically or by simulation, instantaneous performance measures of a larger system containing the encapsulated system without ``opening up'' the encapsulated system.
 
• The decomposition approximation approximates networks of queues and multi-class multi-resource queues by a collection of loosely-coupled multi-class single-resource models. This again reduces the dimensionality of the Chapmann-Kolmogorov equations.
 
• Z-iteration methods have been implemented for connection-oriented integrated-services networks, for TCP/IP networks, and for networks of M/M/1/K queues with time-varying arrival, service, and routing rates. Comparison against simulations confirm the accuracy and speed of the Z-iteration methods. Details are provided below. We are currently developing Z-iteration methods for other areas, including TCP/IP integrated-sevices networks, on-line evaluation for network control, and on-line distributed evaluation for control of federated networks.
   

• We consider a connection-oriented network with connection-request classes, each specifying a source node, a destination node, an arrival rate, a service duration, and a QoS (quality of service) attribute.  Each request is routed on one of the paths available for each class, where it is subjected to admission control and resource reservation.

• This network is converted to a time-dependent MCMR (multi-class multi-resource) queue consisting of a resource set for each link of the network and a class for each pair of workload class and possible path. The arrival rate of a MCMR class is a function of the arrival rate of its network connection-request class and the current routing state.

• The MCMR queue is then evaluated by the Z-iteration, first decomposing the MCMR queue into multiple MCSR (multi-class single-resource) queues, and then using functional approximation on each MCSR queue.

• The Z-prototyper, an implementation of this evaluator, has been available on the WWW since 1997. Applications are described in papers.
 

• We consider TCP/IP networks with TCP and UDP transport connections over adaptive IP routing.

• The IP layer of the network is modeled by a time-dependent open network of queues in the natural way: A queue is introduced for each link of the network. The max queue size and server speed correspond to the buffers and speed of the link. The routing probabilities between queues are derived from the paths of the transport connections. Changes in paths (due to adaptive routing) are modeled by appropriate changes in the values of the (time-dependent) routing probabilities.

• Each UDP source is modeled by a time-dependent stochastic process (of fluid/Poisson statistics) whose rate is varied according to the application and can be specified either by traces or synthetically. This accomodates practically any kind of traffic, including audio, video, http, file transfer, self-similar, long-range dependency, etc.

• Each TCP source is modeled (or encapsulated) by a profile expressing its instantaneous throughput versus instantaneous roundtrip time and instantaneous loss probability. We represent it by a surface as shown here. The profile is empirically obtained and hence accounts for the algorithms and implementation features of the source. Click here for profiles of TCP Reno as implemented on Windows NT, NetBSD, and the NS simulator.

• Click here for examples of evaluations of TCP driven networks and comparisons against NS simulations.
  
  
• NetSolver 1.0, a Windows implementation of this evaluator is now available (March 1999).

 

Papers

Z-iteration: Efficient Estimation of Instantaneous Measures in Time-Dependent Multi-Class Systems. The Z-iteration method for MCMR (multi-class multi-resource) queues along with simple applications.

Fast Time-Dependent Evaluation of Integrated Services Networks. An application to a network with routing, admission, and scheduling control can be found.

Numerical Evaluation of Hierarchical QoS Routing. An application to a network with adaptive hierarchical QoS routing.

Fast Evaluation of Ensemble Transients of Large IP Networks (ps.gz, 100K).  The Z-iteration method for open networks of M(t)/M(t)/1/K queues, and application to IP networks.

Empirical TCP Profiles and Application (ps.gz, 4M).  TCP profiles and their application to the Z-iteration evaluation of TCP/IP networks.

Fast Evaluation of Ensemble Transients of M(t)/M(t)/* Networks (ps.gz, 95K).  The Z-iteration method for open networks of M(t)/M(t)/1/K queues.

Z-iteration for RED TCP/IP Networks.  Preliminary results on Z-iteration for TCP/IP networks with RED routers.

Z-iteration for CBQ TCP/IP Networks.  Preliminary results on Z-iteration for TCP/IP networks with CBQ (class-based queueing) routers.

Software

NetSolver : Z-iteration implementation for TCP/IP networks (March 1999).

Z-prototyper : Z-iteration implementation for connection-oriented networks (1997).