In this paper, we consider a provider that offers an application implemented as a composite service to several users with (possibly) different Quality of Service (QoS) requirements. To this end, the provider negotiates with both the clients and the service providers Service Level Agreements (SLAs), which define the respective QoS-related obligations along with the interval of time over which such obligations are to be met.

We present an efficient SLA provisioning scheme which allows to determine for each client the constituent services that best meet its QoS goal as well as the services effective usage. Differently from most of the current approaches, which consider independently each single request and often require the solution of an NP-hard problem, we take into account the simultaneous and concurrent client accesses to the application and optimize the aggregated QoS of all incoming client requests by means of a simple linear programming problem. As a result, the proposed approach is scalable and lends itself to an efficient implementation.