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.

Chen Lee Last modified: Tue Jun 15 21:20:56 EDT 1999