On Quality of Service Optimization with Discrete QoS Options


We present a QoS management framework that enables us to quantitatively measure QoS, and to analytically plan and allocate resources. In this model, end users' quality preferences are considered when system resources are apportioned across multiple applications such that the net utility that accrues to the end-users is maximized. In [23] [24] we primarily worked with continuous QoS dimensions, and assumed that the utility gained by improvements along a QoS dimension were always representable by concave functions. In this paper, we relax both assumptions. One, we support discrete QoS operating points. Two, we make no assumptions about the concavity of the utility functions. Using these as the basis, we tackle the problem of maximizing system utility by allocating a single finite resource to satisfy the QoS requirements of multiple applications along multiple QoS dimensions. We present two near-optimal polynomial algorithms to solve this problem. The first yields an allocation within a provably known bounded distance from the optimal solution, and the second yields an allocation whose distance from the optimal solution can be explicitly controlled (with provable bound as well) by the 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. These detailed evaluations provide practical insight into which of these algorithms can be used online in real-time systems.

Chen Lee
Last modified: Wed Jun 16 15:11:11 EDT 1999