Integrated Dynamic Control for Robust Quality-of-Service Routing

Summary

This project deals with the dynamic control of large networks that integrate real-time and non-real-time applications with heterogeneous Quality-of-Service (QoS) requirements. To meet these requirements, adaptive algorithms are needed for the routing, scheduling and admission control components. Routing provides a selection of routes, which should have sufficient resources to satisfy the applications' QoS. Scheduling allocates link resources (bandwidth, buffers, etc.) among the different service classes. Admission accepts or rejects a new incoming application, based on the requested QoS and the available resources. Because each control component causes and reacts to changes in the network state, there is a strong time-dependent interaction among them. By taking this interaction into account, we are developing QoS routing algorithms that will provide significant improvements in performance. To that end, we are developing dynamic integrated models. A novel numerical-analytical technique, called Z-iteration, is being used to solve these models. The Z-iteration is a promising approach to rapid and accurate solutions to transient performance of integrated networks consisting of both wired and wireless links. Networks based on ATM and integrated services IP are considered. This project is developing software educational tools and projects for integrated networks, and will experiment with providing QoS support to educational multimedia applications.

Acknowledgment

This project is supported by the National Science Foundation through a CAREER grant NCR-9701988.

Personnel

Project Description

The design of effective control algorithms for QoS networks is far more complicated than for traditional networks (e.g., telephone and data networks). Firstly, QoS networks will support diverse applications that have diverse characteristics and requirements at very high speeds. Secondly, the necessary algorithms are usually adaptive with parameters being varied dynamically according to service class and current or delayed network state information. Furthermore, arrival and service statistics are often time-varying. Thus, there is a strong time-dependent interaction among the various control components as each component causes and reacts to changes in the network state. Design and evaluation approaches must take into account this interaction to ensure a highly efficient QoS system.

In this project, we are developing routing algorithms with improved transient and steady-state performance by exploiting the time-dependent interaction between routing and other control components. The developed routing algorithms are designed to scale in terms of processing, storage and communication requirements. Routing involves selecting paths/routes with sufficient resources to satisfy the applications' QoS. Unlike traditional least-loaded-based routing, which has load balancing as its major objective, QoS routing has the more important (and often conflicting) goal of actively matching the distribution of available network resources to the distribution of the diverse QoS requests/calls. Achieving this goal results in increasing the chance that the selected path indeed satisfies the requested QoS, which in turn results in increased network utilization (or equivalently, revenue).

This project was motivated by our experiences with dynamic class-based datagram routing, real-time virtual-circuit routing, and hierarchical routing. Our work demonstrates that performance can be significantly improved by integrating routing with scheduling and admission control. In particular, integrated QoS control can lead to the efficient distribution of calls from diverse traffic classes over the network, performance gains in terms of revenue, delay etc., and fairness among the different classes. We briefly discuss below some of our preliminary findings.

In [1], the routing of delay-sensitive and throughput-sensitive best-effort traffic is considered. It is shown that routing performance can be significantly improved if, instead of traditional first-come-first-served, a class-based packet scheduling structure is used and exploited when calculating link costs for the different classes. In particular, delay-sensitive traffic is packed on low-delay routes, and throughput-sensitive traffic on high-capacity routes.

In [2], the routing of real-time virtual-circuits (VCs) with different bandwidth requirements over a virtual-path-based ATM network is considered. We considered routing policies which implement packing of narrowband VCs (having relatively small bandwidth requirement) on some paths in order to leave room on other paths for wideband VCs. This packing strategy achieves two desired properties: (1) it minimizes the fragmentation of available bandwidth, which in turn results in (2) improved fairness by increasing the chances of admittance for wideband VCs. It is shown that packing-based VC routing schemes outperform traditional least-loaded-based routing schemes in terms of revenue. Furthermore, fairness among the different VC classes is shown to be much improved when routing is appropriately coupled with admission control. This integrated control does not further discourage the routing of larger VCs over alternate (longer) paths to save resources; all VC classes are treated fairly concerning the use of alternate paths.

The considered packing-based schemes are, however, based on pessimistic/deterministic analysis. They only account for the different bandwidth requirements of different classes, but not on their traffic intensities (demands). These traffic intensities may be known a priori (based on traffic forecasts) or dynamically estimated. In [3], we present an on-line VC routing scheme that is based on the concept of load profiling, which allows a distribution of available bandwidth across a set of candidate routes to match the characteristics of incoming VC QoS requests. We show the effectiveness of our load-profiling approach when compared to traditional load-balancing and load-packing VC routing schemes.

In [4], a real-time VC routing scheme that is based on the viewserver hierarchy is presented. The scheme is shown to scale to very large networks in terms of storage and communication requirements. Results illustrate that routing performance can be significantly affected by the hierarchical structure used to achieve scaling (which typically causes loss of routing/QoS information). In particular, under our viewserver hierarchy, a source node obtains a partial view of the network (as opposed to a full-view). This partial view typically does not contain long paths. This is generally desirable since using long paths would tie up more resources. This produces the same effect obtained with the well-known "trunk reservation" control, giving priority to short length VCs over long ones.

It is clear from our past work that considering the interaction among various controls significantly improves performance. In order to design truly integrated dynamic QoS control for large networks in a cost-effective way, it is crucial to find efficient and accurate modeling and evaluation tools. This allows for the rapid prototyping and evaluation of different design alternatives, while at the same time accounting for the complex end-to-end behavior resulting from dynamic conditions and the subtle interactions among the various control components. Unfortunately, traditional tools do not seem effective. Analytical approaches are often too coarse, ignoring detailed and dynamic situations. Simulation approaches are often too expensive due to the need for a large number of replicated simulation runs to obtain descent confidence measures. In [5], we introduce a parallelizable dynamic-flow-based method, called Z-iteration, which achieves a good balance between accuracy and speed. The method is general and applicable to multi-class systems. We used it to evaluate a number of simple multi-class systems, including integrated services networks and parallel database servers. The method has proven to be both accurate and fast, providing modeling power close to that of simulation at a fraction of the computation expense. In [6] and [7], the Z-iteration is applied to more detailed network models and used to evaluate a number of dynamic VC routing schemes.

A key component of this method is to develop models for wireline and wireless links that reflect their different characteristics, QoS scheduling and admission control algorithms. These link models can be obtained analytically or experimentally using system identification techniques. The overall network model can then be solved to determine control parameters (e.g. arrival rates controlled by routing) that optimize some performance/cost function (e.g. throughput, delay). The speed of the Z-iteration also suggests that it could be used within network switches/routers to predict performance on-line and make control decisions accordingly. We have recently acquired high-speed ATM switches through industrial support from GTE and FORE. Traffic measurements on ATM switches and on IP routers will be used to derive and validate our traffic and link models.

This project will develop software educational tools and projects for QoS networks based on the Z-iteration and the MaRS network simulator [8]. Furthermore, we will experiment with implementing our integrated QoS control and routing algorithms within a QoS architecture for educational multimedia applications and Computer Supported Cooperative Work (CSCW) applications in general. [9] presents a preliminary architecture and [10] presents a computer supported lifelong learning model.

Papers


Last updated Jan 15, 1998