Heuristics for QoS-aware Web Service Composition

TLDR

QoS‑aware composition of Web services requires selecting alternatives for each task to satisfy overall QoS and cost, a problem traditionally tackled by exact algorithms or complex heuristics that are too slow for real‑time workflow engines. The authors aim to introduce a fast heuristic that delivers near‑optimal QoS‑aware compositions and to assess its potential for further improvement by other heuristics. They propose a lightweight heuristic, evaluate it through simulations, and compare its performance to exact algorithms and other heuristics. Simulations show the heuristic achieves up to 99% of the optimal QoS while using less than 2% of the time required by standard exact algorithms.

Abstract

This paper discusses the quality of service (QoS)-aware composition of Web services. The work is based on the assumption that for each task in a workflow a set of alternative Web services with similar functionality is available and that these Web services have different QoS parameters and costs. This leads to the general optimization problem of how to select Web services for each task so that the overall QoS and cost requirements of the composition are satisfied. Current proposals use exact algorithms or complex heuristics (e.g. genetic algorithms) to solve this problem. An actual implementation of a workflow engine (like our WSQoSX architecture), however, has to be able to solve these optimization problems in real-time and under heavy load. Therefore, we present a heuristic that performs extremely well while providing excellent (almost optimal) solutions. Using simulations, we show that in most cases our heuristic is able to calculate solutions that come as close as 99% to the optimal solution while taking less than 2% of the time of a standard exact algorithm. Further, we also investigate how much and under which circumstances the solution obtained by our heuristic can be further improved by other heuristics