skip to main content
10.1145/1526709.1526828acmconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
research-article

Combining global optimization with local selection for efficient QoS-aware service composition

Published: 20 April 2009 Publication History

Abstract

The run-time binding of web services has been recently put forward in order to support rapid and dynamic web service compositions. With the growing number of alternative web services that provide the same functionality but differ in quality parameters, the service composition becomes a decision problem on which component services should be selected such that user's end-to-end QoS requirements (e.g. availability, response time) and preferences (e.g. price) are satisfied. Although very efficient, local selection strategy fails short in handling global QoS requirements. Solutions based on global optimization, on the other hand, can handle global constraints, but their poor performance renders them inappropriate for applications with dynamic and real-time requirements. In this paper we address this problem and propose a solution that combines global optimization with local selection techniques to benefit from the advantages of both worlds. The proposed solution consists of two steps: first, we use mixed integer programming (MIP) to find the optimal decomposition of global QoS constraints into local constraints. Second, we use distributed local selection to find the best web services that satisfy these local constraints. The results of experimental evaluation indicate that our approach significantly outperforms existing solutions in terms of computation time while achieving close-to-optimal results.

References

[1]
M. M. Akbar, E. G. Manning, G. C. Shoja, and S. Khan. Heuristic solutions for the multiple-choice multi-dimension knapsack problem. In Proceedings of the International Conference on Computational Science-Part II, pages 659--668, London, UK, 2001. Springer-Verlag.
[2]
E. Al-Masri and Q. H. Mahmoud. The qws dataset. Web page. http: //www.uoguelph.ca/~qmahmoud/qws/index.html/.
[3]
E. Al-Masri and Q. H. Mahmoud. Qos-based discovery and ranking of web services. In Proceedings of the IEEE International Conference on Computer Communications and Networks, 2007.
[4]
E. Al-Masri and Q. H. Mahmoud. Investigating web services on the world wide web. In Proceedings of the International World Wide Web Conference, 2008.
[5]
D. Ardagna and B. Pernici. Global and local QoS constraints guarantee in web service selection. In Proceedings of the IEEE International Conference on Web Services, pages 805--806, Washington, DC, USA, 2005. IEEE Computer Society.
[6]
D. Ardagna and B. Pernici. Adaptive service composition in flexible processes. IEEE Transactions on Software Engineering, 33(6):369--384, 2007.
[7]
C. Aurrecoechea, A. T. Campbell, and L. Hauw. A survey of qos architectures. Multimedia Systems, 6(3):138--151, 1998.
[8]
B. Benatallah, Q. Z. Sheng, A. H. H. Ngu, and M. Dumas. Declarative composition and peer-to-peer provisioning of dynamic web services. In Proceedings of the International Conference on Data Engineering, pages 297--308, Washington, DC, USA, 2002.
[9]
A. S. Bilgin and M. P. Singh. A daml-based repository for QoS-aware semantic web service selection. In Proceedings of the IEEE International Conference on Web Services, pages 368--375, Washington, DC, USA, 2004.
[10]
J. Cardoso, J. Miller, A. Sheth, and J. Arnold. Quality of service for workflows and web service processes. Journal of Web Semantics, 1:281--308, 2004. {11} F. Casati and M.-C. Shan. Dynamic and adaptive composition of e--services. Information Systems, 26(3):143--163, 2001.
[11]
Y. Cui and K. Nahrstedt. Supporting qos for ubiquitous multimedia service delivery. In Proceedings of the ACM International Conference on Multimedia, pages 461--462, 2001.
[12]
M. Gillmann, G. Weikum, and W. Wonner. Workflow management with service quality guarantees. In Proceedings of the SIGMOD Conference, pages 228--239, 2002.
[13]
F. Li, F. Yang, K. Shuang, and S. Su. Q-peer: A decentralized qos registry architecture for web services. In Proceedings of the International Conference on Services Computing, pages 145--156, 2007.
[14]
Y. Liu, A. H. H. Ngu, and L. Zeng. Qos computation and policing in dynamic web service selection. In Proceedings of the International World Wide Web Conference, pages 66--73, 2004.
[15]
I. Maros. Computational Techniques of the Simplex Method. Springer, 2003.
[16]
K. E. Michel Berkelaar and P. Notebaert. Open source (mixed-integer) linear programming system. Sourceforge. http://lpsolve.sourceforge.net/.
[17]
G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. Wiley-Interscience, New York, NY, USA, 1988.
[18]
OASIS. Web services business process execution language, April 2007. http://docs.oasis-open.org/wsbpel/2.0/wsbpel-v2.0.pdf.
[19]
D. Pisinger. Algorithms for Knapsack Problems. PhD thesis, University of Copenhagen, Dept. of Computer Science, February 1995.
[20]
M. Wagner and W. Kellerer. Web services selection for distributed composition of multimedia content. In Proceedings of the ACM International Conference on Multimedia, pages 104--107, New York, NY, USA, 2004.
[21]
K. P. Yoon and C.-L. Hwang. Multiple Attribute Decision Making: An Introduction (Quantitative Applications in the Social Sciences). Sage Publications, 1995.
[22]
T. Yu, Y. Zhang, and K.-J. Lin. Efficient algorithms for web services selection with end-to-end qos constraints. ACM Transactions on the Web, 1(1), 2007.
[23]
L. Zeng, B. Benatallah, M. Dumas, J. Kalagnanam, and Q. Z. Sheng. Quality driven web services composition. In Proceedings of the International World Wide Web Conference, pages 411--421, 2003.
[24]
L. Zeng, B. Benatallah, A. H. H. Ngu, M. Dumas, J. Kalagnanam, and H. Chang. Qos-aware middleware for web services composition. IEEE Transactions on Software Engineering, 30(5):311--327, 2004.
[25]
C. Zhou, L.-T. Chia, and B.--S. Lee. Daml-qos ontology for web services. In Proceedings of the IEEE International Conference on Web Services, pages 472--479, Washington, DC, USA, 2004.

Cited By

View all
  • (2024)Quality of Service (QoS)-Aware Microservices Selection Based on Local ConstraintsInternational Journal of Computer Theory and Engineering10.7763/IJCTE.2024.V16.135216:2(35-43)Online publication date: 2024
  • (2024)A Discrete Adaptive Lion Optimization Algorithm for QoS-Driven IoT Service Composition with Global ConstraintsJournal of Network and Systems Management10.1007/s10922-024-09808-w32:2Online publication date: 13-Mar-2024
  • (2024)Service Re-Selection for Disruptive Events in Mobile Environments: A Heuristic Technique for Decision Support at RuntimeInformation Systems Frontiers10.1007/s10796-023-10392-826:3(1063-1090)Online publication date: 1-Jun-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
WWW '09: Proceedings of the 18th international conference on World wide web
April 2009
1280 pages
ISBN:9781605584874
DOI:10.1145/1526709

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 April 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. QoS
  2. optimization
  3. service composition
  4. web services

Qualifiers

  • Research-article

Conference

WWW '09
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)21
  • Downloads (Last 6 weeks)2
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Quality of Service (QoS)-Aware Microservices Selection Based on Local ConstraintsInternational Journal of Computer Theory and Engineering10.7763/IJCTE.2024.V16.135216:2(35-43)Online publication date: 2024
  • (2024)A Discrete Adaptive Lion Optimization Algorithm for QoS-Driven IoT Service Composition with Global ConstraintsJournal of Network and Systems Management10.1007/s10922-024-09808-w32:2Online publication date: 13-Mar-2024
  • (2024)Service Re-Selection for Disruptive Events in Mobile Environments: A Heuristic Technique for Decision Support at RuntimeInformation Systems Frontiers10.1007/s10796-023-10392-826:3(1063-1090)Online publication date: 1-Jun-2024
  • (2023)LM2K Model for Hosting an Application Based on Microservices in Multi-CloudSensors10.3390/s2309445023:9(4450)Online publication date: 2-May-2023
  • (2023)LatenSeerProceedings of the 2023 ACM Symposium on Cloud Computing10.1145/3620678.3624787(502-519)Online publication date: 30-Oct-2023
  • (2023)Location‐aware scalable service compositionSoftware: Practice and Experience10.1002/spe.326053:12(2408-2429)Online publication date: 24-Aug-2023
  • (2022)Service composition based on genetic algorithm and fuzzy rulesInternational Journal of Knowledge-based and Intelligent Engineering Systems10.3233/KES-22001626:3(201-217)Online publication date: 20-Dec-2022
  • (2022)A Missing QoS Prediction Approach via Time-Aware Collaborative FilteringIEEE Transactions on Services Computing10.1109/TSC.2021.310376915:6(3115-3128)Online publication date: 1-Nov-2022
  • (2022)A Service Selection Method Based on Ordinal Classification for Historical RecordsIEEE Transactions on Services Computing10.1109/TSC.2020.298825815:3(1321-1333)Online publication date: 1-May-2022
  • (2022)Collaborative Agent Communities for Resilient Service Composition in Mobile EnvironmentsIEEE Transactions on Services Computing10.1109/TSC.2020.296475315:2(876-890)Online publication date: 1-Mar-2022
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media