Tao Yu
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.
- 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. Google Scholar
- BPMI.org. 2002. Business Process Modeling Language (BPML), version 1.0. http://www.bpmi.org/bpml.esp.Google Scholar
- Cardoso, J. SWR algorithm. http://lsdis.cs.uga.edu/proj/meteor/Composition/SWR_Algorithm.htm.Google Scholar
- 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.Google Scholar
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms 2nd Ed. MIT Press. Google Scholar
- 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.Google Scholar
- 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. Google Scholar
- Khan, S. 1998. Quality adaptation in a multisession multimedia system: Model, algorithms and architecture. Ph.D. dissertation, Department of ECE, University of Victoria. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Martello, S. and Toth, P. 1987. Algorithms for Knapsack problems. Ann. Discrete Math. 31, 70--79.Google Scholar
- Menasce, D. A. 2004. Composing Web services: A QoS view. IEEE Internet Comput. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Xiao, J. and Boutaba, R. 2005. QoS-aware service composition and adaptation in autonomic communication. IEEE J. Select. Areas Comm. 23, 12, 2344--2360. Google Scholar
- Yu, T. 2006. Quality of service (QoS) in Web services: Model, architecture and algorithms. Ph.D. thesis, University of California, Irvine, CA. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
Index Terms
- Efficient algorithms for Web services selection with end-to-end QoS constraints
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 SecurityWeb 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