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