article

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

Authors:

Kwei-Jay LinAuthors Info & Claims

ACM Transactions on the Web (TWEB), Volume 1, Issue 1

Pages 6 - es

https://doi.org/10.1145/1232722.1232728

Published: 01 May 2007 Publication History

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.

References

[1]

Aggarwal, R., Verma, K., Miller, J., and Milnor, W. 2004. Constraint driven Web service composition in METEOR-S. In Proceedings of the IEEE International Conference on Service Computing (SCC'04). Shanghai, China.

[2]

BPMI.org. 2002. Business Process Modeling Language (BPML), version 1.0. http://www.bpmi.org/bpml.esp.

[3]

Cardoso, J. SWR algorithm. http://lsdis.cs.uga.edu/proj/meteor/Composition/SWR_Algorithm.htm.

[4]

Casati, F., Ilnicki, S., Jin, L., Krishnamoorthy, V., and Shan, M. 2000. Adaptive and dynamic service composition in eflow. Tech. Rep. HPL-200039, Software Technology Laboratory, Palo Alto, CA.

[5]

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms 2nd Ed. MIT Press.

[6]

Curbera, F. Goland, Y., Klein, J., Leymann, F., Roller, D., Thatte, S., and Weerawarana, S. 2003. Business Process Execution Language for Web Services, Version 1.1. http://www-106.ibm.com/developerworks/webservices/library/ws-bpel.

[7]

Jaeger, M. C., Rojec-Goldmann, G., and Mhl, G. 2004. QoS aggregation for service composition using workflow patterns. In Proceedings of the 8th IEEE International Conference on Enterprise Distributed Object Computing (EDOC'04). Monterey, CA.

[8]

Khan, S. 1998. Quality adaptation in a multisession multimedia system: Model, algorithms and architecture. Ph.D. dissertation, Department of ECE, University of Victoria.

[9]

Khan, S., Li, K. F., Manning, E. G., and Akbar, M. 2002. Solving the knapsack problem for adaptive multimedia systems. Studia Informatica Universalis 2, 1, 157--178.

[10]

Korkmaz, T. and Krunz, M. 2001. Multi-constrained optimal path selection. In Proceedings of 20th Joint Conference of IEEE Computer and Communications Societies (INFOCOM'01). 834--843.

[11]

Ludwig, H., Keller, A., Dan, A., King, R. P., and Franck, R. 2003. Web Service Level Agreement (WSLA) Language Specification. http://www.research.ibm.com/wsla/WSLASpecV1-20030128.pdf.

[12]

Martello, S. and Toth, P. 1987. Algorithms for Knapsack problems. Ann. Discrete Math. 31, 70--79.

[13]

Menasce, D. A. 2004. Composing Web services: A QoS view. IEEE Internet Comput.

[14]

Rao, J. 2004. Semantic Web service composition via logic-based program synthesis. PhD thesis. Department of Computer and Information Science, Norwegian University of Science and Technology.

[15]

Winick, J. and Jamin, S. 2002. Inet 3.0: Internet topology generator. Tech. Rep. UM-CSE-TR-456-02 (http://irl.eecs.umich.edu/jamin/), University of Michigan.

[16]

Xiao, J. and Boutaba, R. 2005. QoS-aware service composition and adaptation in autonomic communication. IEEE J. Select. Areas Comm. 23, 12, 2344--2360.

[17]

Yu, T. 2006. Quality of service (QoS) in Web services: Model, architecture and algorithms. Ph.D. thesis, University of California, Irvine, CA.

[18]

Yu, T. and Lin, K. J. 2005. A broker-based framework for QoS-aware Web service composition. In Proceedings of the 2005 IEEE International Conference on e-Technology, e-Commerce and e-Service (EEE'05), Hong Kong, China.

[19]

Zeng, L. Benatallah, B., Ngu, A., Dumas, M., Kalagnanam, J., and Chang, H. 2004. Quality-aware middleware for Web service composition. IEEE Trans. Softw. Eng. 30, 5, 311--327.

Cited By

Hameche SKhanouche MTari A(2024)Mobility and energy efficient services composition algorithm with QoS guarantee for large scale Cyber–Physical–Social SystemsExpert Systems with Applications10.1016/j.eswa.2024.123683249(123683)Online publication date: Sep-2024
https://doi.org/10.1016/j.eswa.2024.123683
Hamzei MKhandagh SJafari Navimipour N(2023)A Quality-of-Service-Aware Service Composition Method in the Internet of Things Using a Multi-Objective Fuzzy-Based Hybrid AlgorithmSensors10.3390/s2316723323:16(7233)Online publication date: 17-Aug-2023
https://doi.org/10.3390/s23167233
Zhang YIsaacs RYue YYang JZhang LVigfusson Y(2023)LatenSeerProceedings of the 2023 ACM Symposium on Cloud Computing10.1145/3620678.3624787(502-519)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3620678.3624787
Show More Cited By

Index Terms

Efficient algorithms for Web services selection with end-to-end QoS constraints
1. Information systems
  1. Information systems applications

Recommendations

An Efficient Approach for QoS-Aware Service Selection Based on a Tree-Based Algorithm
ICIS '08: Proceedings of the Seventh IEEE/ACIS International Conference on Computer and Information Science (icis 2008)

Service Oriented Architecture (SOA) has become a new software development paradigm because it provides a flexible framework that can help reduce development cost and time. SOA also promises loosely coupled, interoperable, and composable services. In ...
Optimal selection of web services for efficient qos driven web service compositions
ADCONS'11: Proceedings of the 2011 international conference on Advanced Computing, Networking and Security

Web services architecture enables the creation of larger composite services from simpler services. The providers of composite Web services with predefined composition plan involving different composition (flow or workflow) patterns, dynamically select ...
A relaxable service selection algorithm for QoS-based web service composition

Context: Web Services are emerging technologies that enable application to application communication and reuse of autonomous services over Web. Composition of web services is a concept of integrating individual web services to conduct complex business ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on the Web

ACM Transactions on the Web Volume 1, Issue 1

May 2007

164 pages

ISSN:1559-1131

EISSN:1559-114X

DOI:10.1145/1232722

Issue’s Table of Contents

Copyright © 2007 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2007

Published in TWEB Volume 1, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

836
Total Citations
View Citations
5,227
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)6

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hameche SKhanouche MTari A(2024)Mobility and energy efficient services composition algorithm with QoS guarantee for large scale Cyber–Physical–Social SystemsExpert Systems with Applications10.1016/j.eswa.2024.123683249(123683)Online publication date: Sep-2024
https://doi.org/10.1016/j.eswa.2024.123683
Hamzei MKhandagh SJafari Navimipour N(2023)A Quality-of-Service-Aware Service Composition Method in the Internet of Things Using a Multi-Objective Fuzzy-Based Hybrid AlgorithmSensors10.3390/s2316723323:16(7233)Online publication date: 17-Aug-2023
https://doi.org/10.3390/s23167233
Zhang YIsaacs RYue YYang JZhang LVigfusson Y(2023)LatenSeerProceedings of the 2023 ACM Symposium on Cloud Computing10.1145/3620678.3624787(502-519)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3620678.3624787
Wang L(2023)The establishment and adaptive iteration of service community based on context association mining2023 IEEE 3rd International Conference on Electronic Technology, Communication and Information (ICETCI)10.1109/ICETCI57876.2023.10176565(160-164)Online publication date: 26-May-2023
https://doi.org/10.1109/ICETCI57876.2023.10176565
Choi JRyu D(2023)QoS-Aware Graph Contrastive Learning for Web Service Recommendation2023 30th Asia-Pacific Software Engineering Conference (APSEC)10.1109/APSEC60848.2023.00027(171-180)Online publication date: 4-Dec-2023
https://doi.org/10.1109/APSEC60848.2023.00027
Ji YTeng STownsend R(2023)Dynamic Bank Expansion: Spatial Growth, Financial Access, and InequalityJournal of Political Economy10.1086/724112Online publication date: 1-Feb-2023
https://doi.org/10.1086/724112
Hameche SKhanouche MChibani ATari A(2023)A Group Teaching Optimization-Based Approach for Energy and QoS-Aware Internet of Things Services CompositionJournal of Network and Systems Management10.1007/s10922-023-09779-432:1Online publication date: 28-Oct-2023
https://dl.acm.org/doi/10.1007/s10922-023-09779-4
Bouhouche ABenmohammed M(2023)A New Collective Simulated Annealing with Adapted Objective Function for Web Service Selection12th International Conference on Information Systems and Advanced Technologies “ICISAT 2022”10.1007/978-3-031-25344-7_2(8-17)Online publication date: 5-Feb-2023
https://doi.org/10.1007/978-3-031-25344-7_2
Pozas García NDurán FMoreno Berrocal KPimentel E(2023)Location‐aware scalable service compositionSoftware: Practice and Experience10.1002/spe.326053:12(2408-2429)Online publication date: 24-Aug-2023
https://doi.org/10.1002/spe.3260
Liu JXie RKang GWen Y(2023)Spatial‐temporal aware service composition for production factors under industrial internetConcurrency and Computation: Practice and Experience10.1002/cpe.768935:12Online publication date: 8-Mar-2023
https://doi.org/10.1002/cpe.7689
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents