Service Differentiation Based on Flexible Time Constraints in Market-Oriented Grids

Grid services provisioning requires the definition of suited business models taking into account the expectations of both end-users and service providers. Traditional resource management techniques mainly deal with end-users requirements but neglect the benefit that service providers may expect from the sharing of their equipments. In this paper, we propose a fairer management algorithm defending the interests of both end-users and service providers. We consider scheduled jobs in the context of layer-2 Virtual Private Networks (VPN). In practice, the instant of activation of a scheduled job may vary over a certain time window. Depending on the requirements and the budgets of end-users, the size of this time window may fluctuate, the job computing delay being fixed a priori. Our motivation is two-fold. First, we expect to serve a higher number of end-users while respecting each user´s job utility. Second, we aim to increase as best as possible the benefit of service providers. For that purpose, we introduce a weighted cost function enabling a service differentiation relying on time constraints disparity of the submitted jobs. Two approaches are considered to solve this problem: an exact Integer Linear Programming (ILP) formulation and a metaheuristic inspired from the Simulated Annealing (SA) algorithm. The obtained numerical results outline the impact of the flexible time window on the system performance, namely the number of executed jobs and the gain of the service provider.