CMU-CS-99-165Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-99-165
Chen Lee August 1999 Ph.D. Thesis (Department of Electrical and Computer Engineering)
CMU-CS-99-165.ps
Keywords: QoS management and optimization, QoS index and utility
model, QoS tradeoff, resource tradeoff, real-time, multi-media,
policy-driven and adaptive systems
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 This page maintained by reports@cs.cmu.edu |