for the period 1 October 1997 – 31 December 1997

Report #2

CDRL A001

CONTRACT N66001-97-C-8527

15 January 1998

SUBMITTED BY

Carnegie Mellon University

Pittsburgh, PA 15213

Principal Investigator Administrative Contact Contract/Financial Contact

Daniel Siewiorek Margie Rennick

(412) 268-5228 (412) 268-6410

fax: (412) 268-5229 (412) 268-5229

dps@cs.cmu.edu

Distribution authorized to DOD components only; premature dissemination (date). Other requests shall be referred to Naval Command, Control and Ocean Surveillance Center (NCCOSC), RDT&E Division, San Diego, California 92152-5000.

Quarterly Status Report

Quorum

for the period 1 October 1997 –31 December 1997

Contract N66001-97-C-8527

CDRL A002

This status report is the quarterly contract deliverable (CDRL A002) which summarizes the effort expended by the Carnegie Mellon University team in support of Quorum on Contract N66001-97-C-8527.

Staff

Students

3.0 Project Description (last modified 9/97)

Amaranth provides a vision for a comprehensive approach to Quality of Service. The goal of the Amaranth project is to provide multi-dimensional, adaptive, assured Quality of Service (QoS) for heterogeneous distributed computing systems. In particular, Amaranth will provide probabilistic guarantees of service encompassing real-time deadlines, dependability, cryptographic security, and application-specific performance. Amaranth will incorporate adaptive, distributed optimization techniques to maximize system performance even in degraded operating modes. User-specific tradeoffs of service commitment duration, commitment firmness, and service dimensions will provide appropriate service to all users even in a resource-limited system. A specific goal is to provide an order of magnitude improvement in system efficiency over static resource allocation, while assuring a comparable QoS.

Amaranth will combine elements of theory, measurement, and negotiation. Four QoS dimensions (real-time deadlines, dependability, cryptographic security, and application-specific performance) will be related to system resources to enable significant ranges of resource/performance tradeoffs. Visualization and performance modeling tools will support viewing and changing QoS requests for the application, and tuning system QoS negotiation policies for efficiency.

System performance will be dynamically adjusted under varying workloads and resource levels. This will be achieved through the development of theoretical models of end-to-end QoS requirements and negotiation, as well as via the creation of performance monitoring capabilities and measurement tools. In particular, our work will have the following innovations in the underlying areas:

Theory: Amaranth will formally express different dimensions of end-to-end QoS

requirements within a unified theoretical framework. Then, a two-tiered modeling approach for decentralized resource usage optimization will be implemented, incorporating both analytic admission control and decentralized resource allocation.

Measurement: Amaranth will define portable and adaptable QoS parameters for operating

system and application software interfaces. Resource usage will be calculated and predicted using these system-independent parameters.

Negotiation: Amaranth will incorporate per-node scheduling approaches based on

analytic models and local measurements to assure a requested level of QoS. Inter-node dynamic optimization will be accomplished with adaptive negotiation algorithms

for system-level QoS capabilities. Optimization will consider the semantic importance of different datastreams and will be achieved in a completely decentralized manner.

Options to the statement of work included resources and a demonstration system.

Resources: Amaranth will incorporate tools for both single- and multi-dimensional visualization and tuning of QoS versus resource consumption.

System: In order to provide a concrete framework for developing Amaranth

capabilities, it will be implemented with a multi-session, tactically critical video

communication application upon a real-time network of workstations. This testbed will be used to observe and tune QoS tradeoffs under varying workloads and resource availability. Quantification of the effectiveness of the decentralized approach in

terms of efficiency and ability to meet QoS commitments will be accomplished by comparing it to a comparable statically scheduled system.

The Quarter’s focus was defining the stages of evolution for the algorithms and software. A simulator was designed to provide an easy to use platform for evaluating the new theoretical approaches and evaluating representations for visualizing measured data. One graduate student is developing the simulator and a second graduate student is building a monitoring tool for integration with the simulation. A third graduate student developed a simulator for the wireless portion of the network. Actual spending for the quarter is very close to target. Actual and budgeted spending are projected to be completely balanced by the end of the first contract year.

Simulation tool selection/acquisition.

We have performed a technology survey to identify simulation tools and their capability. We've chosen Paul Fishwick's SimPack C++ simulation toolbox from University of Florida (http://www.cis.ufl.edu/~fishwick/simpack/simpack.html) because it is complete, has source code, is inexpensive (free), and is readily distributable for technology transfer.

Further evaluation of SimPack will include ease of use, extensibility and graphical capabilities.

Simpack was ported from Solaris to DEC UNIX. The source code was edited and a library was added to support asynchronous events. The SC21 network was Implemented to evaluate the feasibility of using Simpack for more complex operations. Real Time extensions to Windows NT were evaluated for possible use in the Amaranth development environment for the leaf nodes. Defined four Application Program Interfaces (API) for the Simulator. Developing the first API for the Network Topology input. Standardizing the format and semantics of the input file, so that a standard parsing mechanism may be used.

The relationship between the simulator, theory, and measurement is as follows:

- Policy plug-ins will use well defined APIs to communicate with the simulator and the visualization module.

- The visualization module will receive inputs from the simulator and actual system values and will report resource levels which will be mapped into QoS levels and application levels.

- Three applications with different QoS requirements will be used: Video

Conferencing (Real Time, large data), Robotic Control (Hard Real Time), and Web Browsing (Throughput)..

Measurement

We have developed a simulation for a mobile network to determine the best protocol for QoS. Variables include number of nodes, node location, communications energy function (i.e. square law for satellite communications, cube and higher for terrestrial communications), and message traffic patterns. Measurements include work load, power consumed, and latency for individual nodes. Latency and total power consumption are calculated for the total system. A trade-off among signal/noise ratio (SNR), bandwidth, power, mobility, and latency can be made to achieve lower error rates, which

translates into more robustness. The processing gain measured as the ratio of Bandwidth to Bit Rate determines the number of users the system can support and the throughput

per user. For wireless networks, power consumption should be added to the QoS dimensions.

We are defining an initial set of composite functions that will be graphically displayed. The challenge will be to define functions which effectively summarize the vast amount of information collected from the system. A technical report has been developed describing the simulator.

Several operating systems have been studied to help define an API for performance measurements. In particular Windows NT and RTMach have studied.

In order to develop software, a development platform has been designed. The platform will consist of five application nodes multiply connected to a "cloud" of three routers. The routers will run NetBSD, while the leafs will be a heterogeneous mixture of Windows NT and RTMach.

Theory/ Negotiation

Quality of service (QoS) has been receiving wide attention in recent years in many research communities including networking, multimedia systems, real-time systems and distributed systems. In large distributed systems such as those used in defense systems, on-demand service and inter-networked systems, applications contending for system resources must satisfy timing, reliability and security constraints as well as user-perceived quality requirements. Allocating sufficient resources to different applications in order to satisfy various requirements is a fundamental problem in these situations. A basic yet flexible model for performance-driven resource allocations can therefore be useful in making appropriate tradeoffs.

We have developed a promising outline of a basic analytical model for QoS management in systems which must satisfy application needs along multiple dimensions such as timeliness, reliable delivery schemes, cryptographic security and data quality. We refer to this model as Q-RAM (QoS-based Resource Allocation Model). The model assumes a

system with multiple concurrent applications, each of which can operate at different levels of quality based on the system resources available to it. Each application, in turn, may also need access to multiple resource types at each operating point of allocated resources. The goal of the model is to allocate the resources to the various applications such that the overall system utility is maximized under the constraint that each application can meet its minimum needs. We have identified some resource profiles of applications which allow such decisions to be made efficiently and in real-time. We have also identified application utility functions along different dimensions which are composable to form unique application requirement profiles.

The paper "A QoS-based Resource Allocation Model" was presented at the IEEE Real-Time Systems Symposium in San Francisco on December 5, 1997. The paper presents an analytical model for distributing finite resources among multiple applications such that the overall utility to the system is maximized. Each application must satisfy multiple QoS dimensions. For example, consider an audio application sampling audio from a local microphone and transmitting it to a receiver on the network. The application can use more or less resources. It can use any available resources to enhance the audio sampling rate to enhance the quality of the received audio stream. Alternatively, it can increase the resolution of each sample to improve the quality of each audio sample. It can also process audio samples in smaller batches reducing the end-to-end delay on the stream for interactive applications. It can use the additional resources to encrypt the audio data for security reasons. Or it can send multiple copies of each packet to ensure that at least one copy of every packet reaches the destination. The QoS-based allocation model (Q-RAM) we developed assigns utility functions to each of these QoS dimensions (application quality, timeliness, reliability, and security) as a function of operating points along each dimension. Each operating point of these QoS utility functions is then mapped to the resource demands imposed on the system.

The objective of the Q-RAM model is to allocate resources for each application such that the total system utility (the sum of the utility obtained by each application) is maximized. We have identified an algorithm for optimal resource allocation for the case of a single QoS dimension and a single resource type. The same algorithm finds the optimal resource allocation if there are multiple QoS dimensions which are independent of one another. A QoS dimension is said to be independent of another if changes in the latter does not increase the resource demands on the former. In the case of dependent dimensions and a single resource, we have identified a greedy algorithm which finds a near-optimal solution. However, cases can be identified where this algorithm will not yield a solution close to the optimal. We are currently developing an algorithm which will find the optimal resource allocation even under these conditions. This algorithm will use

variants of convex programming and is expected to have pseudo-polynomial complexity. The goal is to have such algorithms execute in real-time to make resource allocation descisions online. The algoroithms can also be used off-line for making excellent resource allocation decisions even for static systems.

We have developed a new approach termed to queueing theory, called real-time queueing theory, in which tasks which are processed by the system have specific timing

requirements. One important measure of performance is the system's ability to satisfy those requirements. Real-time queueing theory is different from the ordinary queueing theory used for computer performance evaluation in that it keeps track of the lead-times (time until deadline) of each task. This lead-time vector changes dynamically, both in size (tasks arrive and depart) and in the value of its components (tasks age while in the system). The goal of real-time queueing theory are: (1) to develop descriptions of system behavior under assumptions about the nature of task arrival and service times, task deadlines and the real-time scheduling policy being used and (2) to develop control policies which will predictably minimize lateness. To date, this theory has been developed under heavy traffic conditions (conditions in which the service system is operating near its capacity), and the heavy traffic approximations have exhibited excellent accuracy. In addition, a theory of real-time queueing networks has also been developed, and that theory should be applicable to distributed systems.

We have developed a prototype simulator for networks of mobile devices using wireless peer-to-peer transmission. The goal of the simulator is to determine the best protocol for QoS. Input variables to the simulator include number of nodes, node location, communications energy function (i.e. square law for satellite communications, cube and higher for terrestrial communications), and message traffic patterns.

7.1 Open issues with no plan, as yet, for resolution:

Selection of a demonstration application. A set of concurrent applications have been identified which individual stress different QoS metrics. A real time control application stresses real time response, a web browser stresses throughput, encryption of the web data provides security, and video conferencing stresses both latency and throughput.

Identification of the operating system upon which to implement our concepts.

Identification of the network architecture to serve as the basis for software development and evaluation.

The Statement of Work consisted of four areas:

Select and adapt as necessary a QoS theoretical framework for inter-dimensional tradeoffs.

Create a multi-dimensional QoS theoretical framework for inter-dimensional tradeoffs. This framework will encompass the notion of time-sensitive, probabilistic QoS commitments to accommodate the reality of system degradation and overloads.

· QoS Theoretical Framework: Technical report defining the QoS characteristics, parameters, and relationships upon which the theoretical aspects of our work will be based. This includes a description of the theoretical QoS framework for selective interrelation of QoS parameters, mechanisms, and policies based on an example application. We are developing analytic methods to support QoS tradeoffs on

dimensions that can be related to processing requirements (e.g. timeliness, cryptographic security and reliability). We expect to rely on two classes of analytic methodologies: real-time scheduling theory (including rate monatomic and dynamic scheduling methods for

periodic tasks) and real-time queueing theory to handle the stochastic behavior of application arrivals, service times, timing requirements and network routing requirements.

Create resource models/simulations to provide a representative QoS workload for quantifying later project results.

· Resource Models: Software implemented synthetic workload generator for resource availability and resource consumption for use in creating a QoS workload.

- Selected video-conferring with synchronized web-browsing as an application (MS NetMeeting) to focus development.

Develop an initial version of a single-dimension QoS visualization tool for instrumenting and understanding later results.

· Single-Axis QoS Visualization (prototype): Software implemented user control panel for monitoring and adjusting a QoS parameter.

Special emphasis will be placed on decentralized approaches that can survive equipment failures and overloads.

1/98: Instrumented static network simulation. Hand-created network configuration is simulated, including animated instrumentation (e.g., queue depth and utilization of resources).

Measurement functions. How can primitive metrics be composed into system wide metrics.

2/98 Set up development network platform with application suite.

3/98: Reconfigurable network simulation with fault injection.

Simulation is expanded for reconfigurability (i.e., can model a more-or-less arbitrary network topology). Also, fault injection points are provided to insert resource failures and thus observe system response. Simulation will have simplistic fault response routines that act as stubs for later Amaranth policy protocols.

5/98: Developing real-time scheduling and real-time queuing methods tailored to selected application class.

6/98: Simulation with given workload is able to drive a visualization tool (so, simulation provides instrumentation of the system, and visualization provides more intuitive system-level summaries).

6/98 Live Network Monitoring. Primitive data collectors. Design and implementation.

Information display.

The Quarter’s focus was defining the stages of evolution for the algorithms and software. A simulator was designed to provide an easy to use platform for evaluating the new theoretical approaches and evaluating representations for visualizing measured data. A target set of applications and a software development environment have been defined. Weekly design meetings keep the team focused on the first year deliverables.

Raj Rajkumar, Chen Lee, John Lehoczky and Dan Siewiorek "A Resource Allocation Model for QoS Management" In Proceedings of the IEEE Real-Time Systems Symposium, December 1997.

Matt Ettus, "Power Consumption and Latency as a Function of Path Loss and Routing in Multihop SS-CDMA Wireless Networks, ICES Technical Report, December 1997.