Approach

The QoS architecture [7] we consider is composed of a QoS specification interface, a quality trade-off specification model, and a unified QoS-based admission control and resource allocation model. The QoS specification allows multiple QoS requirements to be specified. The trade-off model allows the applications and the users to assign quantitative values called ``utilities'' to the different levels of service. Finally, a QoS resource manager makes resource allocations to those applications so as to maximize the global utility as a weighted sum of the utilities of the individual applications.

In [7], we presented a QoS management framework that enabled system developers and application developers to quantitatively define QoS, and to analytically plan and allocate resources. The system resources are distributed among multiple applications of different quality levels such that the net utility that accumulates to the end-users is maximized.

Using this architecture, the problem of maximizing system utility by allocating a single finite resource and multiple finite resources to satisfy the QoS requirements has been studied in [7] and [5] respectively. It was also proved in [5] that an optimal solution for allocation of multiple resources is NP-hard.

In this MURI project, we consider a more refined problem of apportioning multiple resources with many choices on resource-types. We then present three solutions to the problem. All these solutions are the variants of the local search technique for multiple resource multiple-dimension scheme presented in [5].

We consider a distributed system with multiple resources that services n independent applications denoted by $T_1,..,T_n$. There are m shared resources which are allocated across $n$ applications. The resources could be of same or of different types, such as processors (as sources of computation) or network links (as sources of network bandwidth). We let $R_i$ denote the set of possible allocation choices for the $i^{th}$ resource. Each of the shared resources has a maximum quantity or size denoted by $r^{max}=(r^{max}_1,..,r^{max}_m)$. Each application or task has a quality of service (QoS) requirements across one or many dimensions. For example, a video conferencing application can have the dimensions such as Cryptographic security, Data delivery reliability, video related quality (resolution, frame rate etc.) and audio related quality (sampling rate, audio timeliness etc.).

An user derives satisfaction through these various qualities. Higher the quality along any dimension, higher is the satisfaction. We quantify this in the form of a parameter called utility. The value of this parameter along different quality dimension depends on the application as well as the user. For example, for a fast-moving video application, the frame rate may provide higher utility to the user than the resolution. It may reverse if it happens to be very slow-moving video. Depending on the constraints of various resources, we may need to make trade-offs among these different quality-dimensions.

Thus, we have application profile that is divided into two components, viz., QoS profile and Resource profile. The QoS profile has the following components:

1. Quality Space: $Q_i$

2. Quality Index: For the jth component if $Q_i$ we define a bijective function, $f_{ij}$ which maps to the elements of $Q_{ij}$ into integer valued labels, i.e.

   $f_{ij}:Q_{ij}\rightarrow{1,2,..\vert Q_{ij}\vert}$

   The labels preserve the quality ordering so that $q_1$ is better than $q_2$ if $f_{ij}(q_1) > f_{ij}(q_2)$.

3. Dimension-wise Utility: $u_{ij}:Q_{ij}\rightarrow \Re$, a numerical assessment of the utility achieved by setting $q_{ij} \in Q_{ij}$ for application $t_i$ on quality dimension j.

4. Application Utility: a utility or quantitative measure associated with application $\tau_i$.

   $u_i:Q_i \rightarrow \Re$

   The function $u_i$ could, for example, be defined as a weighted sum of $u_{ij}$.

The resource profile for a task defines the relation between resource $R$ and $Q_i$, $r \models q$. This is a list of resource allocation combinations that can be used to achieve a certain level of QoS point $q$.Since there is a combination of resources that can give rise to the same quality point $q$, we define a relation between $r$ and $q$ instead of a function.

In addition to Application Profile, each task has a User Profile. This dictates the user-specific quality requirements associated with a particular session. An User profile could be a collection of a few templates supplied with the Application profile.