Heuristics for Provisioning Services to Workflows in XaaS Clouds

In XaaS clouds, resources as services (e.g., infrastructure, platform and software as a service) are sold to applications such as scientific and big data analysis workflows. Candidate services with various configurations (CPU type, memory size, number of machines and so on) for the same task may have different execution time and cost. Further, some services are priced rented by intervals that be shared among tasks of the same workflow to save service rental cost. Establishing a task-mode (service) mapping (to get a balance between time and cost) and tabling tasks on rented service instances are crucial for minimizing the client-oriented cost to rent services for the whole workflow. In this paper, a multiple complete critical-path based heuristic (CPIS) is developed for the task-mode mapping problem. A list based heuristic (LHCM) concerning the task processing cost and task-slot matching is developed for tabling tasks on service instances based on the result of task-mode mapping. Then, the effectiveness of the proposed CPIS is compared with that of the previously proposed CPIL, the existing state-of-the-art heuristics including PCP, SC-PCP (an extension to PCP), DET, and CPLEX. The effectiveness of the proposed LHCM is evaluated with its use with different task-mode mapping algorithms. Experimental results show that the proposed heuristics can reduce 24 percent of the service renting cost than the compared algorithms on the test benchmarks at most for non-shareable services. In addition, half of the service renting cost could be saved when LHCM is applied to consolidate tasks on rented service instances.