Optimal precomputation for mapping service level agreements in grid applications

A complicated task running on the grid system is usually made up of many services, each of which typically offers a better service quality at a higher cost. Mapping service level agreements (SLA) optimally is to find the most appropriate quality level for each service, so that the overall SLA of a task is achieved at the minimum cost. This paper considers mapping execution time SLA in the case of the discrete cost function, which is an NP-hard problem. Due to the high computation complexity of mapping SLA, we propose a precomputation scheme that computes the selection of service levels in advance for every possible SLA requirement, which reduces the response time of a request greatly. The precomputation employs (1 + ε) approximation, and its solution for any time bound is at most (1 + ε) times larger than the optimal cost. Simulations show the superiority of (1 + ε) approximation compared with other methods. © 2006 ACM.