Efficient Algorithms for Web Services Selection with End-to-End QoS Constraints

Authors: Tao Yu, Yue Zhang, and Kwei-Jay Lin - University of California, Irvine

Complete Citation

• Tao Yu, Yue Zhang, and Kwei-Jay Lin. Efficient Algorithms for Web Services Selection with End-to-End QoS Constraints. ACM Transactions on the Web 1(1), 2007.

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 endto-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.

Annotations

Knapsack-related algorithms are leveraged to optimize service selection with respect to a utility function. The authors create a logical framework for service composition by employing atomic services and operators such as sequential dependence, AND, XOR, Loop, AND join (MERGE), XOR join (TRIGGER). They simulate the behavior of their heuristic algorithm. The general model for investigating these problems is useful, and heuristics employed give good results.

Tags (Wozniak): Web Services, Quality of Service, QoS, Optimization

Related Work

• Zeng, L. Benatallah, B., Ngu, A., Dumas, M., Kalagnanam, J., and Chang, H. Quality-aware middleware for Web service composition. IEEE Transaction on Software Engineering 30(5), 2004.

-- JustinWozniak - 13 Jun 2007