A quality of service (QoS) management framework for systems is presented that satisfies application needs along multiple dimensions. In this model, end users' quality preferences are taken into account when system resources are apportioned across multiple applications such that the net system utility accrued to the end-users is maximized. The framework facilitates QoS tradeoff through a semantically rich QoS specification interface that enables the end users to give guidance on the qualities they care about and the tradeoffs they are willing to make under potential resource shortages. The interface also allows the user or system administrator to define fine-grained service requests easily for multi-dimensional complex QoS provisioning. Furthermore, by introducing the abstraction of Quality Index, which maps qualities to indices in a uniform way, and by the mathematical modeling of QoS Tradeoff and Resource Tradeoff, we transform the QoS management problem into a combinatorial optimization which ultimately enables us to quantitatively measure QoS, and to analytically plan and allocate resources.

A series of optimization algorithms is developed that tackle the QoS management problem which is provably NP-hard. The first set of algorithms treats the problem of maximizing system utility by allocating a single finite resource to satisfy the QoS requirements of multiple applications along multiple QoS dimensions. Two near-optimal algorithms are developed to solve this problem. The first yields an allocation within a known distance from the optimal solution, and the second yields an allocation whose distance bound from the optimal solution can be explicitly controlled by a QoS manager. We compare the run-times of these near-optimal algorithms and their solution quality relative to the optimal allocation, which in turn is computed using dynamic programming.

The second set of algorithms deals with apportioning multiple finite resources to satisfy the QoS needs of multiple applications along multiple QoS dimensions. Three strategies are evaluated and compared First, dynamic programming and integer programming with branch-and-bound compute optimal solutions to this problem but exhibit very high running times. Then the integer programming approach is adapt to yield near-optimal results with faster running times. Finally, an approximation algorithm based on an extended local search technique is presented that is less than a few percent from the optimal solution but which is more than two orders of magnitude faster than the optimal scheme of dynamic programming. Perhaps more significantly, the local search technique turns out to be very scalable and robust as the number of resources under management increases. These detailed evaluations provide practical insight into which of these algorithms can be used online in real-time systems.

125 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu