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

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. Mostofa Akbar , Eric G. Manning , Gholamali C. Shoja , Shahadat Khan, Heuristic Solutions for the Multiple-Choice Multi-dimension Knapsack Problem, Proceedings of the International Conference on Computational Science-Part II, p.659-668, May 28-30, 2001
• 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: Eyhab Al-Masri , Qusay H. Mahmoud, Investigating web services on the world wide web, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367605]
• 5: Danilo Ardagna , Barbara Pernici, Global and Local QoS Constraints Guarantee in Web Service Selection, Proceedings of the IEEE International Conference on Web Services, p.805-806, July 11-15, 2005 [doi>10.1109/ICWS.2005.66]
• 6: Danilo Ardagna , Barbara Pernici, Adaptive Service Composition in Flexible Processes, IEEE Transactions on Software Engineering, v.33 n.6, p.369-384, June 2007 [doi>10.1109/TSE.2007.1011]
• 7: Cristina Aurrecoechea , Andrew T. Campbell , Linda Hauw, A survey of QoS architectures, Multimedia Systems, v.6 n.3, p.138-151, May 1998 [doi>10.1007/s005300050083]
• 8: Declarative Composition and Peer-to-Peer Provisioning of Dynamic Web Services, Proceedings of the 18th International Conference on Data Engineering, p.297, February 26-March 01, 2002
• 9: A. Soydan Bilgin , Munindar P. Singh, A DAML-Based Repository for QoS-Aware Semantic Web Service Selection, Proceedings of the IEEE International Conference on Web Services, p.368, June 06-09, 2004 [doi>10.1109/ICWS.2004.3]
• 10: Dynamic and adaptive composition of e-services, Information Systems, v.26 n.3, p.143-163, May 2001 [doi>10.1016/S0306-4379(01)00014-X]
• 11: Yi Cui , Klara Nahrstedt, Supporting QoS for ubiquitous multimedia service delivery, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500211]
• 12: Michael Gillmann , Gerhard Weikum , Wolfgang Wonner, Workflow management with service quality guarantees, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564718]
• 13: Fei Li , Fangchun Yang , Kai Shuang , Sen Su, Q-Peer: A Decentralized QoS Registry Architecture for Web Services, Proceedings of the 5th international conference on Service-Oriented Computing, September 17-20, 2007, Vienna, Austria [doi>10.1007/978-3-540-74974-5_12]
• 14: Yutu Liu , Anne H. Ngu , Liang Z. Zeng, QoS computation and policing in dynamic web service selection, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013379]
• 15: István Maros, Computational Techniques of the Simplex Method, Kluwer Academic Publishers, Norwell, MA, 2002
• 16: K. E. Michel Berkelaar and P. Notebaert. Open source (mixed-integer) linear programming system. Sourceforge. http://lpsolve.sourceforge.net/.
• 17: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 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: Matthias Wagner , Wolfgang Kellerer, Web services selection for distributed composition of multimedia content, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027546]
• 21: K. P. Yoon and C.-L. Hwang. Multiple Attribute Decision Making: An Introduction (Quantitative Applications in the Social Sciences). Sage Publications, 1995.
• 22: Tao Yu , Yue Zhang , Kwei-Jay Lin, Efficient algorithms for Web services selection with end-to-end QoS constraints, ACM Transactions on the Web (TWEB), v.1 n.1, p.6-es, May 2007 [doi>10.1145/1232722.1232728]
• 23: Liangzhao Zeng , Boualem Benatallah , Marlon Dumas , Jayant Kalagnanam , Quan Z. Sheng, Quality driven web services composition, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775211]
• 24: Liangzhao Zeng , Boualem Benatallah , Anne H.H. Ngu , Marlon Dumas , Jayant Kalagnanam , Henry Chang, QoS-Aware Middleware for Web Services Composition, IEEE Transactions on Software Engineering, v.30 n.5, p.311-327, May 2004 [doi>10.1109/TSE.2004.11]
• 25: Chen Zhou , Liang-Tien Chia , Bu-Sung Lee, DAML-QoS Ontology for Web Services, Proceedings of the IEEE International Conference on Web Services, p.472, June 06-09, 2004 [doi>10.1109/ICWS.2004.44]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Management, Measurement, Performance

Keywords:
QoS, optimization, service composition, web services