On Quality of Service Management
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.