Abstract
Quality-of-Service (QoS) performance guarantee for service-oriented systems (SOS) has become a critical problem. With the increasing number of offered services comes the challenge of efficiently building large-scale SOS to meet the required QoS criteria. Optimization of QoS-driven semantic Web service composition is known to be NP-hard. We address the efficiency issue by developing a polynomial time algorithm (QDA) for shortest sequence composition. We use dynamic programming to find service candidates for each execution. When all the services are searched, we use a depth-first trace back to derive the execution plan. We have tested our approach under Web-scale demands 20,000 services and 150,000 semantic concepts. In comparison with existing approaches, our experimental results show that QDA can be used to solve large-scale service composition problem effectively and efficiently with QoS guarantee.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ponnekanti SR, Fox A (2002) Sword: a developer toolkit for web service composition. In: Proceedings of the 11th international WWW conference (WWW2002)
Sirin E, Parsia B, Wu D, Hendler J, Nau D (2004) Htn planning for web service composition using shop2. Web Semant Sci Serv Agents World Wide Web 1(4): 377–396
McIlraith S, Son T (2002) Adapting golog for composition of semantic web services. In: KR2002, Toulouse, France, pp 482–493, 22–25 April
Liang QA, Su SYW (2005) AND/OR graph and search algorithm for discovering composite web services. Int J Web Serv Res 2(4): 48–67
Hashemian SV, Mavaddat F (2006) A graph-based framework for composition of stateless web services. In: ECOWS, pp 75–86
Milanovic N, Malek M (2006) Search strategies for automatic web service composition. Int J Web Serv Res 3(2): 1–32
Web Service Challenge. http://www.ws-challenge.org
Gu Z, Xu B, Li J (2007) Inheritance-aware document-driven service composition CEC/EEE’07. IEEE Computer Society, Japan
Yan Y, Xu B, Gu Z (2008) Automatic service composition using AND/OR graph CEC/EEE’08. IEEE Computer Society, Washington D.C.
Ran S (2003) A framework for discovering web services with desired quality of services attributes. In: Proceedings of the international conference on web services. CSREA Press, Bogart, GA, pp 208–213
Singhera ZU (2004) Extended web services framework to meet non-functional requirements. In: Proceedings of the symposium on applications and the internet workshops. IEEE CS, Silver Spring, MD, pp 334–340
Ludwig H, Keller A, Dan A, King RP, Franck R (2003) Web Service Level Agreement (WSLA) language specification. http://www.research.ibm.com/wsla/WSLASpecV1-20030128.pdf/
Dan A, Davis D, Kearney R, Keller A, King R, Kuebler D, Ludwig H, Polan M, Spreitzer M, Youssef A (2004) Web services on demand: WSLA-driven automated management. IBM Syst J 43(1): 136–158
Skene J, Lamanna DD, Emmerich W (2004) Precise service level agreements. In: Proceedings of the 26th international conference on software engineering (ICSE’04)
Zeng L, Benatallah B (2004) QoS-aware middleware for web service composition. IEEE Trans Softw Eng 30(5): 311–327
Zeng L, Benatallah B, Dumas M, Kalagnanam J, Sheng QZ (2003) Quality driven web services composition. In: Proceedings of the 12th international conference on World Wide Web (WWW). ACM Press, Budapest, Hungary, May 2003
Cardoso J (2002) Quality of service and semantic composition of worklows. Ph.D. Thesis, University of Georgia, Georgia
Yu T, Zhang Y, Lin K-J (2007) Efficient algorithms for web services selection with end-to-end QoS constraints. ACM Trans Web 1(1), Article 6, May 2007
Xiao J, Boutaba R (2005) QoS-aware service composition and adaptation in autonomic communication. IEEE J Select Areas Commun 23(12): 2344–2360
Alrifai M, Risse T (2009) Combining global optimization with local selection for efficient QoS-aware service composition. WWW 2009, 20–24 April 2009
Jaeger MC, Ladner H (2005) Improving the QoS of WS compositions based on redundant services. In: Proceedings of the international conference on next generation web services practices (NWeSP 2005), pp 189–194
Lecue F, Mehandjiev N (2009) Towards scalability of quality driven semantic web service composition. In: Proceedings of th IEEE international conference on web services, July 2009
Stein S, Payne TR, Jennings NR (2009) Flexible provisioning of web service workflows. ACM Trans Internet Technol 9(1): 1–45
Google Mashup Editor. http://code.google.com/gme/
Microsoft’s Popfly. http://www.popfly.com/
IBMs QEDWiki. http://services.alphaworks.ibm.com/qedwiki/
Yahoo Pipes. http://pipes.yahoo.com/
Web Ontology Language. http://www.w3.org/TR/owl-features/
Web Service Level Agreements. http://www.research.ibm.com/wsla/
Cyc ontology. http://www.cyc.com/cyc/technology/whatiscyc_dir/maptest/
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Xu, B., Luo, S., Yan, Y. et al. Towards efficiency of QoS-driven semantic web service composition for large-scale service-oriented systems. SOCA 6, 1–13 (2012). https://doi.org/10.1007/s11761-011-0085-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11761-011-0085-8