Efficient algorithms for Web services selection with end-to-end QoS constraints

TLDR

Service‑Oriented Architecture enables flexible composition of services via standard protocols, but selecting components that meet application‑specific QoS requirements requires dedicated algorithms. The authors introduce a broker‑based architecture designed to maximize an application‑specific utility function while satisfying end‑to‑end QoS constraints. They formulate service selection as a multidimensional 0‑1 knapsack problem and as a multi‑constraint optimal path problem, and propose efficient heuristic algorithms for different composition structures, comparing the two models. Simulation results demonstrate that the heuristics achieve good performance, and the comparison reveals the trade‑offs between the knapsack and path‑based formulations.

Abstract

Service-Oriented Architecture (SOA) provides a flexible framework for service composition. Using standard-based protocols (such as SOAP and WSDL), composite services can be constructed by integrating atomic services developed independently. Algorithms are needed to select service components with various QoS levels according to some application-dependent performance requirements. We design a broker-based architecture to facilitate the selection of QoS-based services. The objective of service selection is to maximize an application-specific utility function under the end-to-end QoS constraints. The problem is modeled in two ways: the combinatorial model and the graph model. The combinatorial model defines the problem as a multidimension multichoice 0-1 knapsack problem (MMKP). The graph model defines the problem as a multiconstraint optimal path (MCOP) problem. Efficient heuristic algorithms for service processes of different composition structures are presented in this article and their performances are studied by simulations. We also compare the pros and cons between the two models.