March 1998

Revised August 1998

---

---

1 - Introduction

This paper explores the relationship between quality of service and survivability.  Section 2 discusses the concepts of quality of service and survivability. Section 3 identifies and presents highlights of important QoS research efforts. Section 4 discusses these projects in more detail, particularly efforts whose approach to QoS is compatible to our approach to survivability.  Section 5 identifies technical "points of intersection" between the QoS and survivability work that could eventually lead to a confluence.  Section 6 identifies some issues that arise when QoS and survivability are combined and points out some weaknesses in the way the existing projects add and measure survivability.

2 - Quality of Service & Survivability

A pair of short papers from Rome Laboratory describe service-level QoS as a function of precision (how much), accuracy (how correct), and timeliness (does it come when needed).  For example, a map may be insufficiently precise (100m instead of 10m resolution), inaccurate (things in the wrong places), or untimely (delivered too late to be useful).  Unless all three requirements are met, a client is not getting what it needs and therefore the result is lacking in QoS.  A benefit function is defined for each point in this 3-D space stating the value to the client of receiving that particular QoS.  Distance metrics for the argument spaces are application dependent. For example, the distance between "red" and "orange" will be less than the distance between "red" and "blue" in a spectral dimension, but not in a textual dimension. The benefit function is similarly application-specific and may be situation dependent as well.

QoS at any given level of abstraction places QoS requirements on the components providing the QoS.  In the example, delivering a 10m map requires the retrieval of a certain number of bits of map data.

A survivable system is one that can repair itself or degrade gracefully to preserve as much critical functionality as possible in the face of attacks and failures.  A survivable system needs to be able to switch compatible services in an established connection and substitute acceptable alternatives.  It must also be able to dynamically adapt to the threats in its environment to reallocate essential processing to the most robust resources.

QoS and survivability are intricately linked; they are not the same, but neither makes sense without the other.

• Survivability without some notion of what is supposed to be surviving is pointless; the what is provided by QoS metrics.
• QoS "guarantees" that can't be made to survive or adapt under changing conditions are not very useful as guarantees, and could in fact lead to denial of service attacks as opponents bring a system to its knees by degrading QoS and causing the QoS management system to continually add superfluous resources.

3 - Overview of QoS Projects

BBN Cluster:  The BBN cluster consists of three architecture/infrastructure efforts based on a CORBA client server model:

• QuO - Quality Objects

team: BBN - see: papers
• AQuA - Adaptive Quality of Service Availability

team: BBN, Illinois, Cornell - see: papers
• OIT - Open Implementation Toolkit for Creating Adaptable Distributed Applications

team: BBN, Illinois - see: papers,

• DIRM - Dynamic Integrated Resource Management

team: BBN, Columbia, SMARTS - see: papers

SRI: SRI is developing an architecture and scheduling algorithms for the delivery of end-to-end QoS for a data streaming model:

• Adaptive QoS-driven Resource Management for Distributed Real Time Systems

team: SRI - see: papers,

• UltraSAN

team: Illinois - see papers
• QoSME

team: Columbia
• InCharge/MODEL

team: SMARTS, Inc. - see papers,
• Horus

team: Cornell

4 - QoS Project Details

BBN Related Projects -QuO, AQuA, OIT, DIRM

Using QDL, an object can specify the QoS it expects from each service that it uses and can specify what its usage patterns will be (e.g., invocations/sec).  An object will similarly use QDL to specify the QoS it knows how to provide (which can be different for different implementations or resource levels). These specifications are used to create client-server bindings called connections. Connections are first-class objects as they are in our survivability model defined in Composition Model for OSAs.

To make the writing of QoS specifications and the creation and maintenance of connections tractable, QoS is partitioned into regions of normative behavior.  Within each region it is assumed that every QoS is equally useable.  Region definitions look like predicates in a language like C. Some of these regions (e.g., Normal, Overload, InsufficientResources, Idle) are predefined, but others can be defined using QDL.  Clients and services parameterize these regions to define when they are in a particular one.  For example, a client may say that when in Normal mode, it will make between 2 and 10 calls/sec to a particular service; anything over 10 calls/sec puts the client into Overload mode.

The use of regions means that minor (insignificant) deviations in the QoS delivered do not require changes to the service or connection, which substantially simplifies runtime processing. Similarly, if clients and servers agree on common meanings for named regions, matching client and server specifications is simplified which is important since this activity must often be done on the fly. The use of QoS regions is a significant difference between the BBN and SRI approaches; in the SRI approach, the benefit function is allowed to be continuous.

The regions discussed so far are called negotiated regions since they represent where the client and server try to operate and form the basis for the connection contract. As long as both the client and server operate in their negotiated regions, all is well. However, it is possible for either the client or the server (which for these purposes also includes the connection between the proxy and the remote server implementation) to deviate from the negotiated region, either by overloading the server or failing to deliver results as required. Because of the potential for operating outside the negotiated regions, QuO defines reality regions to represent the actual QoS-relevant behaviors of client and servers. Reality regions are defined in the same way as negotiated regions; it appears that for any given connection, the same set of specifications will be used for both kinds of regions.  If the observed reality region differs from the negotiated region, the connection is no longer valid and remedial action must be taken.

Various monitors determine the reality region a connection is actually in. Monitors are presumably predefined to monitor the kinds of things that QuO cares about; others can presumably be defined, and there is a claim that they can be deployed selectively to only monitor those QoS items of interest.  Types of monitors include counting invocations, timers, and heartbeats. It seems that there could be a whole subsystem for inserting probes in useful places.

Operationally, a QuO object is a distributed object where part of it lies on the server side and part(s) lie with its various clients. It is appropriate to think of the client side as being a very smart proxy object that knows how to do QoS related actions.  (It appears that this stub can be further tailored to do just about anything, but that doesn't look like a good idea unless the architecture tells what kinds of things should be done in the proxy.)  A QuO proxy keeps track of the negotiated QoS mode of the connection; interacts with monitors; provides feedback to the client through interfaces generated from the QDL; and takes certain actions to maintain the negotiated QoS.

Client-side proxies can take actions to maintain a QoS mode or change the negotiated QoS region.   A client makes a service request through a client-side proxy which decides what to do with method invocations.  This could include sending the requests to a server, servicing them from a cache, routing to replicas, routing to a varying set of implementation objects, or ignoring them and signaling an exception.   How many of these they actually plan to provide is unknown, but this is definitely where they fit.  It fits very well with our survivability model, except that we would extract this from the purview of the client and move it to a Surivability Service to handle competing service demands.  In an ideal world, there would be a large number of generic actions that could be taken by any proxy to maintain QoS or shift regions gracefully when it detects a change in client behavior.  Our Evolution Model for OSAs defines many ways to evolve configurations.  Some of the actions a client-side proxy can take to maintain a region or change regions are:

• A server may be able to shift its implementation in order to stay in the same region without disturbing the client.  An example given is to change implementations to trade bandwidth for processing power as resource availability changes.  Since the server stays in the same negotiated region, the client doesn't need to see any change.
• The client may request a different negotiated region.  For example, it may go idle and negotiate a lower QoS region.  It is also possible that a client is detected to have entered a different region.  For example, the regions may define Idle as no messages of any kind for 5 minutes.   If the reality region enters Idle, it can be treated as if the client signaled that it was going Idle.  Thus a client can change modes without having to be implemented for QoS.
• A server may have multiple implementation strategies that will allow it to enter different regions.  For example, if the client goes Idle, the server may scale back its own resources, while if a Client enters an Overload mode, the server may add resources or shift to a different implementation.
• The proxy may make an up-call to the client to find out what to do.

The QuO papers give a fairly detailed figure of the form of the proxy objects.  The partitioning of function seems good and would allow us to extend if we needed to.  This looks like where a lot of their work went.

A weakness of the QuO project seems to be that they appear to have a sort of "one-level" service model, in which clients call services which are leaves.  Also, the allocation of resources appears to be under the control of the proxies, without much regard for other demands. They briefly mention a language, Resource Definition Language (RDL) for specifying resources and it would be reasonable that there be some sort of auction or scheduler that gave resources out in a non-object centric way, but this gets little attention.   It may be possible to handle both multiple levels of objects and sensible allocation for competing resources, but they don't seem to do it.  It appears that the architecture and models do make this possible.

AQuA is improving the QuO proxy architecture, attaching RSVP to allow QuO proxies to control QOS over CORBA, and adding regions to deal with availability as well as QoS.  Not much published, so what follows is my supposition as to how this will work.  It appears that they plan to predefine a number of negotiated regions for availability, where the region predicate has to do with things like how many replicas will be required in order to stay in that region.  Hooks down to a replication manager (probably via Horus or using Electra/Ensemble) are used as the monitors to detect whether the reality region for availability has changed (e.g., a replica died).  Actions in response to an availability change would be to start another replica or inform the client of the change and let the client decide what to do in the same way it decides what to do about QoS region changes.  UltraSAN is being used (or at least considered) as a way to determine the availability region predicates.  Using UltraSAN (and possibly SMARTS/Model), they will model various configurations and use the UltraSAN simulation and analysis tools to determine how long a configuration is likely to stay alive or how long it will take to reconfigure (I haven't actually seen the latter discussed at all, so maybe they do not plan to do this).  They will define and analyze configurations until they find one that has the right predicted availability for a particular client need.  That will then form a contract for a specific availability region.

It is not clear that they maintain a connection between QoS and availability.  It looks like region predicates express both QoS and availability concerns in the same predicate.  Since increased availability can degrade QoS (slower with more replicas depending on the operation), this needs to be addressed.  It does look like they will be able to determine that the combined reality region does not match the combined negotiated region, but that will not help with the act of finding a good combined region definition that can actually be instantiated.

OIT is just getting started and not much has been written about it.  It looks like they will be cleaning up some QuO internal architecture and perhaps developing a toolkit to help write and manage contracts.  This may integrate with the use of UltraSAN; it does not say so, but that would not be an unreasonable part of such a toolkit. It also appears that OIT will be using these extensions to provide some support for survivability along the lines of AQuA; it is not clear what the relationship is between them.

DIRM has much more the feel of a technology demonstration than the other projects.  Little is written about it, but it appears that the idea is to show off some QoS concepts in a collaborative decision process in some sort of military command post setting.

SRI

Resources are allocated by a scheduler based on a modified Dykstra shortest path algorithm for finding least cost (w.r.t. a definable cost function such as least time, cheapest, or throughput) path through a graph representing the required processing steps and communication. There is a delta form of the algorithm that gives delta-suboptimal decisions much faster.  A concern is algorithm speed and the fact that it appears to require a centralized scheduler.

It appears that the scheduling algorithm precludes the use of this work in a peer-peer or client-server setting; if so, this is a major differentiator between the SRI and BBN work. There are several reasons for this. It is hard to see how a shortest path algorithm can be adapted to handle arbitrary numbers of loop iterations as can be found in general client-server or peer-peer systems. A feature of the algorithms is that processing steps and flow be able to be identified on a time step basis; this doesn't seem to match an environment in which service requests are either random or have high variance.  All their examples deal with media delivery. The papers mention the ability to separate feedback paths from feed forward paths, but this is not explained.

They define more completely than anyone else surveyed the meaning of precision, accuracy, and timeliness, specifying explicit parameters for these concepts.  Each parameter has several components, including absolute values, relationships between values, expected values, bounds, and variance.  It looks like a QoS specification could become quite complex.  They also define a benefit function in the obvious way.  It is not clear how their scheduling algorithm deals with relative values or variance that their QoS specifications allow.

This work appears most suitable for rather tightly controlled situations where a high level of QoS is required.  Unlike the BBN work, their solution appears to not be open.

UltraSAN

AQuA is attempting to apply UltraSAN to availability management by building a SAN for a projected configuration (along with the reward functions), converting it to a Markov model, and solving to determine what level of availability it can provide.  I don't see how this could be done on the fly, so I presume they intend to do off-line evaluations of various configurations they think they can construct, rate each as being survivable or available to some degree, and then define "regions" around these precomputed configurations.  e.g., UltraSAN predicts that under a given set of transition assumptions, 3 replicas gives availability of 0.9999 for T seconds, so a region of high availability would be that 3 replicas are maintained.  Failure to do so constitutes a "reality" region change, which requires reconfiguration or change to a different "negotiated" region.  I don't think this can deal well with configurations not previously planned as desirable and not with changes to the transition parameters as would happen if the system came under attack.  This might allow a degree of "preplanned" survivability, but does not appear highly adaptive.

None of the papers directly talk about evaluating configurations for survivability under exceptional conditions.  All deal with expected behavior of a configuration to determine the "reward" from a particular configuration.

Limitations on the use of UltraSAN in AQuA or OIT appear to be:

• Modeling in UltraSAN looks quite complex, so not a lot of alternative configurations will be able to be tried.  Hence, they will not be able to employ as many survivability techniques as they might actually have available.
• UltraSAN analysis techniques are heavy weight, since they require repeated simulation or solution of huge Markov models.  This means that all analysis will have to be done in advance; i.e., when contract regions are established, not when something breaks.  This has the same disadvantage as above.
• UltraSAN models do not appear to be easily modified if the interconnect topology changes.  This is not a big problem in the original target environment of UltraSAN, where topology was based on physical interconnects, but is more of an issue in a service model, where the topology changes as easily as starting a new process.
• It is not clear how UltraSAN deals with a time-varying mix of tasks and loads.

Columbia - QoSME

SMARTS - MODEL & inCharge

Cornell - Horus

5 - Commonalities Between QoS and Survivability Techniques

QoS and Survivability Specified by Client; Managed by System

• While managing either of these is hard for a service developer to implement on a per service basis, the techniques used are generic enough that they can be developed well by QoS and survivability experts and applied to a wide variety of services and situations.
• QoS and survivability both require resource reservation, which in turn requires substantial knowledge about the resource environment. The environment is the same for all services in it, so it makes more sense to model it outside of any of the individual services. This especially true since the environment will be expected to evolve (for good or ill) over the lifetime of the services.
• Services cannot make unilateral decisions on resource reservation because they have to compete against other services, whose existence may be unknown to them. Every service will naturally attempt to maximize its own behavior, but in resource constrained conditions, this will be impossible. This will require at minimum a non service centric allocation mechanism.
• The relative values of the services themselves will change depending on the situation. Services that are valuable in peacetime may become considerably less valuable during combat. Unless a service is programmed to understand all the operational contexts in which it may find itself and adjust its demands accordingly, this is impossible to achieve. This is unreasonable to expect, especially for services that may be used for many years and be adapted to new contexts. It also does not handle greedy services that chose not to play by the rules, perhaps from malevolent intent.

Binding Specifications

Proxy Architecture Extensions

There are several advantages to extending CORBA proxies and server stubs:

• All communications between clients and servers must, by definition, pass through the proxies and server stubs. Arguments and return results are exposed and packaged for movement at this point as part of the normal argument marshaling. Together, this means that all communications can be mediated and that what is passing through the connection is easily accessible.
• A proxy and the server-side stub reside in different address spaces (and often on different machines). This gives some flexibility as to where a given extension should be placed. This can be an advantage for performance reasons. In addition, since functionality can only be provided reliably if the monitor is incorruptible, having the ability to place monitors and mediators out of harm's way is advantageous. This is especially true for things like security monitoring, where a client or service may wish to avoid the mediation and could attempt to corrupt local monitors; the OMG security Service does this. Finally, because proxies and stubs can fail independently, it is possible to place monitors in each to monitor the health of the other.
• The CORBA specification allows proxies and stubs to be extended to do other tasks besides message passing. Alternative proxies have been used to manage local caches, to distribute processing load among replicas, and to manage security (in the OMG Security Service). Commercial ORBs often provide server stub alternatives that wrap the server implementation via inheritance or delegation.
• Smart proxies can be generated automatically by an improved IDL compiler that either replaces or extends the IDL compiler that is provided with every ORB to generate proxies and server stubs. [Note: replacement is more likely than extension because, although they could be, these compilers are in general not open to extension.] IDL can be extended to allow definition of additional properties as in the case of BBN's QDL for defining QoS attributes.

Adopting BBN terminology, we call the entire collection of mechanisms between a client and a service a connection.

Connections

The need for increased abstraction is because the enhanced binding specifications allow considerably more binding alternatives and consequently more flexibility in the way the connections are established and managed. This additional flexibility makes it important to make not only the location and implementation of the object providing the service hidden from the client, but also which object is providing the service. Because of this, the client must not be allowed to act as it is connected to a specific object providing the service or to expect anything about the service other than what it requests in the binding specification it provides.

The increased activity is because the connection is attempting to guarantee far more things about the interaction than simply "best effort" to deliver requests and return results. It does this by maintaining information about the desired behavior of the connection in the form of a connection contract, measuring the actual behavior through a collection of monitors attached to the proxy and server stubs, and taking remedial action if the two do not match. Remedial actions include changing the implementation of the object providing service, changing which object provides the service, renegotiating the connection contract, or terminating the connection gracefully.

Because of the above, the connection itself becomes a first-class object and should have interfaces through which its activity can be monitored as well as the interfaces used by the client and server.

Monitors

6 - Issues in Merging QoS & Survivability

• If a service fails to be available, and hence doesn't respond when needed, isn't that a QoS failure?  How is the failure to deliver a timely response because of service crash different, from the client perspective, from failure to deliver a timely response due to any other cause that would be covered by QoS considerations?    Why should they be specified independently?
• A service that is up 100% of the time but provides low QoS isn't really "available".  Just the fact that a service is running is irrelevant.
• To meet a given QoS requirement, there is no requirement that a service be continually available; only that it do what it is supposed to do at the right time.   Assume that a service has a QoS requirement of 99% of its responses to be within a 10 second time window from method invocation.  As a QoS metric, that is pretty clear.  However, when mapped to availability, it is less obvious and there is not a clear correlation.  If a client sends 100 messages/hour and each takes 1 second to process, there is no requirement that the service be "up" 99% of the time.  The service will actually be doing useful work for 100/3600 seconds (<3% of the time).  So, as long as it can be brought up fast enough when needed, there is really no 99% "availability" requirement.  This false issue does not arise if the entire matter is couched as a QoS requirement.
• If the time to start a service was zero and all services could persistently save their current state for free, a service could be activated only and exactly when it had work to do.  In this case, there would never be a need to have a service running until it was needed, which would obviate the need for replication except for the persistent state.  Again, replication and availability is not exactly the right measure.
• High availability can be obtained by the use of many replicas.  This is not without overhead for replica coordination, so the result is likely to be reduced performance leading to possibly reduced QoS.  Treating QoS and availability separately makes this analysis harder.

• availability as a client concern
• too few reconfiguration strategies
• QoS not pushed through all levels of abstraction
• inadequate treatment of time
• configuration and QoS "fragility" not considered
• inadequate metrics

Problem: Availability as a Client Concern

• Case #1 - Service A determines that it must be available 99.99% of the time to satisfy 99% of the requests by a client.
• Case #2 - Service B determines that it can be booted quickly enough that it can be idle until needed and never has to be "available".
• Case #3 - Service C determines that it has enough resources that if available 99.9% of the time it can satisfy 99% of the requests of 10 clients.

Problem: To Few Reconfiguration Strategies

Problem: QoS Requirements Not Pushed Through All Levels of Abstraction

A related difficulty is that the QoS policies at higher layers need to somehow be reflected down to lower layers in meaningful form.  Consider this example.  A client requires high availability (in the BBN model) and fast response.  If availability was the only QoS requirement, the existence of the requisite number of replicas would be sufficient to maintain the contract.  However, this is not adequate, since response time also matters.  Different replication policies (primary copy, voting, etc.) give different QoS behaviors.  Further, the messaging policy within a replica group may vary depending on the QoS needs of the client.  For example, normally reads are sent only to a single replica to conserve bandwidth and processing.  However, if timely delivery is crucial, it makes sense to attempt reads from multiple replicas to ensure that at least one responds in time (assuming of course that the multiple reads will not compete for the same bandwidth and become even slower).  The policy to follow could vary based on a number of factors, including load on the resources, criticality of timely response, client value, and previous behavior of the connection (e.g., is it barely making the timing bound?).  To acheive this, it would appear that the high level QoS goal be somehow pushed down to the replication and messaging subsystem.

Problem: Inadequate Treatment of Time

Problem: Configuration & QoS Fragility

Contract #1

• 10 sec - 30 sec response
• 15 sec average response over any 10 invocation intervals
• no violations allowed

• 10 sec - 30 sec response
• 15 sec average response over any 10 invocation intervals
• no more than 1 timeliness failure per 100 invocations AND no more than 2 average responses over 20 sec per 100

          intervals

• in Contract #1, if the average response time is 14.9 seconds, that is not as safe as if it were 11 seconds, since a response time of 30 seconds on the next request would cause a violation in the former case but not the latter
• in Contract #2, if a timing goal has been missed, another timing goal cannot be missed until a certain number of responses have been made

• if the service configuration fails, there is an increased chance that the next QoS target will not be met; this is influenced by how long it takes to restart the service (if possible)
• if the threat environment becomes more hostile, the probability of missing a QoS target increases, even if no targets have been missed so far
• if load increases, missing QoS targets becomes more likely, even though none have been missed so far

The BBN work partially addresses this problem of brittleness by requiring a given availability for services based on a precomputed replication factor, which is made part of the QoS region contract.  By maintaining replicas, the service never becomes too brittle.  While this approach suffers from the limitations discussed above, it brings out an interesting point that we will exploit more fully in our work combining QoS and survivability.  In the base QuO work, all parts of the region contract were relevant to the client and all violations were seen by the client (although often they could be fixed by the proxy).  However, the replication factor is not relevant to the client except as a rough measure of the ability to deliver future QoS.  When a contract is violated due to replica failures, only the proxy is concerned.   We are working on extending and formalizing this notion that a contract should have parts relevant to both the client and the proxy so that QoS can be delivered and brittle states avoided.

Metrics

This has two principle effects.

• The survivability metrics must differ from the QoS metrics, since the latter measure only current state. To give an extreme example of the difference, consider that placing a service on a lightly loaded, but very vulnerable machine will score highly on the QoS metric, but low on the survivability metric. These metrics, and their relationship, are discussed later.
• A Survivability Service will need to take expected future behavior into account when allocating resources. This necessitates some sort of model of likely future events that could cause a configuration to change.

Bibliography of QoS Papers

Rome Laboratory

• Quality of Service for AWACS Tracking, Patrick Hurley ,Tom Lawrence, Tom Wheeler, Ray Clark, to appear 4^th International Command and Control Research and Technology Symposium, 14-16 September 1998, Nasby Park (Stockholm) Sweden
• Anomaly Management, Thomas F. Lawrence, AFRL, internal report, 1997

BBN Cluster Papers

QuO

• Project Overview (1995)

initial objectives
• Overview of Quality of Service for Distributed Objects (1995)

subsumed by Architectural Support for Quality of Service for CORBA Objects
• Object-Oriented QoS for C2 Adaptivity and Evolvability (1996)

overview
• Object-Oriented QoS: Some Research Issues (1996)

subsumed by  Architectural Support for Quality of Service for CORBA Objects
• Architectural Support for Quality of Service for CORBA Objects (1997)

key paper - defines QuO terminology & outlines the QuO proxy internals
• Specifying and Measuring Quality of Service in Distributed Object Systems (1998)

key paper - defines the QuO proxy architecture & the CDL contract language

DIRM

• AQuA and DIRM: QuO Projects Overview (1996)

context example of collaborative planning across a WAN
• 1997 DARPA Project Summary (1997)

describes integration of QuO + WAN (with RSVP + QoSME) in a test bed

AQuA

• Adaptive Quality of Service for Availability (AQuA) (1997)

project overview as seen by BBN
• 1997 DARPA Project Summary (1997)

QuO + Ensemble/Electra + UltraSan; improvements to Ensemble stack, control of replication level of service from QuO
• Adaptive Quality of Service for Availability (AQuA) (1998)

project overview as seen from Illinois; regions used for setting availability (replication) levels

OIT

• Toolkit for Adaptable Distributed Applications (OIT) (1997)

description of planned QuO internal refinements; new start

SRI Papers

• QoS Taxonomy  (1997)

good definitions of QoS parameters and benefit function
• Modeling for Adaptive QoS (1997)

describes a multi-level model for application-specific QoS specification that supports implementation alternatives and variable QoS
• QoS-Based Allocation(1997)

describes a scheduler for resource allocation in a network that is QoS aware

Illinois Papers

• Dependability Evaluation Using UltraSAN (1993)

best short introduction
• Specification and Construction of Performability Models (1989)

detailed introduction, but difficult to follow as a first exposure to the technology

SMARTS Papers

• "High Speed & Robust Event Correlation" - Yemini, Kiger, Mozes, Yemini, Ohsie.

Description of the SMARTS inCharge fault analysis system.