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.
- 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. Google ScholarDigital Library
- E. Al-Masri and Q. H. Mahmoud. The qws dataset. Web page. http: //www.uoguelph.ca/~qmahmoud/qws/index.html/.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- D. Ardagna and B. Pernici. Adaptive service composition in flexible processes. IEEE Transactions on Software Engineering, 33(6):369--384, 2007. Google ScholarDigital Library
- C. Aurrecoechea, A. T. Campbell, and L. Hauw. A survey of qos architectures. Multimedia Systems, 6(3):138--151, 1998. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- M. Gillmann, G. Weikum, and W. Wonner. Workflow management with service quality guarantees. In Proceedings of the SIGMOD Conference, pages 228--239, 2002. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- I. Maros. Computational Techniques of the Simplex Method. Springer, 2003. Google ScholarDigital Library
- K. E. Michel Berkelaar and P. Notebaert. Open source (mixed-integer) linear programming system. Sourceforge. http://lpsolve.sourceforge.net/.Google Scholar
- G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. Wiley-Interscience, New York, NY, USA, 1988. Google ScholarDigital Library
- OASIS. Web services business process execution language, April 2007. http://docs.oasis-open.org/wsbpel/2.0/wsbpel-v2.0.pdf.Google Scholar
- D. Pisinger. Algorithms for Knapsack Problems. PhD thesis, University of Copenhagen, Dept. of Computer Science, February 1995.Google Scholar
- 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. Google ScholarDigital Library
- K. P. Yoon and C.-L. Hwang. Multiple Attribute Decision Making: An Introduction (Quantitative Applications in the Social Sciences). Sage Publications, 1995.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- Combining global optimization with local selection for efficient QoS-aware service composition
Recommendations
Selecting skyline services for QoS-based web service composition
WWW '10: Proceedings of the 19th international conference on World wide webWeb service composition enables seamless and dynamic integration of business applications on the web. The performance of the composed application is determined by the performance of the involved web services. Therefore, non-functional, quality of ...
A hybrid approach for efficient Web service composition with end-to-end QoS constraints
Dynamic selection of Web services at runtime is important for building flexible and loosely-coupled service-oriented applications. An abstract description of the required services is provided at design-time, and matching service offers are located at ...
QoS-Aware Service Composition: A Survey
ECOWS '10: Proceedings of the 2010 Eighth IEEE European Conference on Web ServicesService compositions build new services by orchestrating a set of existing services. In the Internet of Services there may be many functional similar services, but with different Quality of Service (QoS). Thus a significant research problem in service ...
Comments