A Scalable Solution to the Multi-Resource QoS Problem
Abstract
The problem of maximizing system utility by allocating a single finite resource to satisfy discrete Quality of Service (QoS) requirements of multiple applications along multiple QoS dimensions was studied in 6. In this paper, we consider the more complex problem of apportioning multiple finite resources to satisfy the QoS needs of multiple applications along multiple QoS dimensions. In other words, each application, such as video-conferencing, needs multiple resources to satisfy its QoS requirements. We evaluate and compare three strategies to solve this provably NP-hard problem. We show that dynamic programming and mixed integer programming compute optimal solutions to this problem but exhibits very high running times. We then adapt the mixed integer programming problem to yield near-optimal results with smaller running times. Finally, we present an approximation algorithm based on a local search technique that is less than 5% away from the optimal solution but which is more than two orders of magnitude faster. Perhaps more significantly, the local search technique turns out to be very scalable and robust as the number of resources required by each application increases.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1999
- Accession Number
- ADA367891
Entities
People
- Chen Lee
- Dan Siewiorek
- Jeff Hansen
- John Lehoczky
- Ragunathan Rajkumar
Organizations
- Carnegie Mellon University