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 , 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 , 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 , 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 , 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 , 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  and , 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 . 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.  presents a preliminary architecture and  presents a computer supported lifelong learning model.
 I. Matta and M. Krunz. Packing
and Least-Loaded Based Routing in Multi-Rate Loss Networks. Proc.
IEEE ICC '97, 827-831 (1997).
 A. Bestavros and I. Matta. Load
Profiling for Efficient Route Selection in Multi-Class Networks. Proc.
IEEE ICNP'97, 183-190 (1997).
 C. Alaettinoglu, I. Matta, and A. U. Shankar. A
Scalable Virtual Circuit Routing Scheme for ATM Networks. Proc.
IEEE ICCCN '95, 630-637 (1995).
 I. Matta and A. U. Shankar. Z-Iteration:
A Simple Method for Throughput Estimation in Time-Dependent Multi-Class
Systems. Proc. ACM SIGMETRICS/PERFORMANCE '95, 126-135 (1995).
 I. Matta and A. U. Shankar. An
Iterative Approach to Comprehensive Performance Evaluation of Integrated
Services Networks. Proc. IEEE ICNP '94, 40-47 (1994). Extended
version to appear in Computer Networks and ISDN Systems - special
issue on Modeling of Wired and Wireless ATM.
 I. Matta and A. U. Shankar. Dynamic
Routing of Real-Time Virtual Circuits. Proc. IEEE ICNP '96,
 C. Alaettinoglu, A. U. Shankar, K. Dussa-Zieger, and
I. Matta. Design
and Implementation of MaRS: A Routing Testbed. Journal of Internetworking:
Research & Experience, vol. 5, no.1, 17-41 (1994).
 I. Matta, M. Eltoweissy and K. Lieberherr. From
CSCW Applications to Multicast Routing: An Integrated QoS Architecture.
NU-CCS-97-09 (1997). To appear in Proc. IEEE ICC '98.
 M. Eltoweissy and I. Matta. Computer Supported Generative Learning. To appear in International Conference on Technology and Education ICTE '98.