A heuristic approach to optimal service selection in service oriented architectures

ABSTRACT

Service Oriented Architectures (SOA) enable a multitude of service providers (SP) to provide loosely coupled and interoperable services at different Quality of Service (QoS) and cost levels. This paper considers business processes composed of activities that are supported by service providers. The structure of a business process may be expressed by languages such as BPEL and allows for constructs such as sequence, switch, while, flow, and pick. This paper considers the problem of finding the set of service providers that minimizes the total execution time of the business process subject to cost and execution time constraints. The problem is clearly NP-hard. However, the paper presents an optimized algorithm that finds the optimal solution without having to explore the entire solution space. This algorithm can be used to find the optimal solution in problems of moderate size. A heuristic solution is also presented and experimental studies that compare the optimal and heuristic solution show that the average execution time obtained with a heuristic allocation of providers to activities does not exceed 6% of that of the optimal solution.

REFERENCES

• 1: "Web Service - Business Process Execution Language (WS BPEL)," Version 2.0 - OASIS Committee Draft, 17th May, 2006.
• 2: D. Ardagna and B. Pernici, "Global and Local QoS Guarantee in Web Service Selection," Proc. of Business Process Management Workshops, pp. 32--46, 2005.
• 3: Rainer Berbner , Michael Spahn , Nicolas Repp , Oliver Heckmann , Ralf Steinmetz, Heuristics for QoS-aware Web Service Composition, Proceedings of the IEEE International Conference on Web Services, p.72-82, September 18-22, 2006 [doi>10.1109/ICWS.2006.69]
• 4: M. Brian Blake, Decomposing Composition: Service-Oriented Software Engineers, IEEE Software, v.24 n.6, p.68-77, November 2007 [doi>10.1109/MS.2007.162]
• 5: Jan Bosch , Stefan Friedrichs , Stefan Jung , Johannes Helbig , Alexander Scherdin, Service Orientation in the Enterprise, Computer, v.40 n.11, p.51-56, November 2007 [doi>10.1109/MC.2007.399]
• 6: G. Canfora, M. Di Penta, R. Esposito, and M. L. Villani, "An Approach for QoS-aware Service Composition Based on Genetic Algorithms," Proc. Genetic and Computation Conf., June 2005.
• 7: V. Cardellini, E. Casalicchio, V. Grassi, and L. P. Francesco, "Flow-based service selection for web service composition supporting multiple qos classes," ICWS 2007. IEEE Intl. Conf. Web Services, pp. 743--750, July 9-13,2007.
• 8: Francisco Curbera, Component Contracts in Service-Oriented Architectures, Computer, v.40 n.11, p.74-80, November 2007 [doi>10.1109/MC.2007.376]
• 9: Thomas H. Davenport, Process innovation: reengineering work through information technology, Harvard Business School Press, Boston, MA, 1993
• 10: H. David, "Order Statistics," John Wiley & Sons, 1981.
• 11: Casey K. Fung , Patrick C. K. Hung , Guijun Wang , Richard C. Linger , Gwendolyn H. Walton, A Study of Service Composition with QoS Management, Proceedings of the IEEE International Conference on Web Services, p.717-724, July 11-15, 2005 [doi>10.1109/ICWS.2005.19]
• 12: M. Hammer and J. Champy, "Reengineering the Corporation: A Manifesto for Business Revolution," Harper Business, 1993.
• 13: Michael C. Jaeger , Gero Muhl , Sebastian Golze, QoS-Aware Composition of Web Services: A Look at Selection Algorithms, Proceedings of the IEEE International Conference on Web Services, p.807-808, July 11-15, 2005 [doi>10.1109/ICWS.2005.95]
• 14: H. J. E. Johansson, "Business Process Reengineering: BreakPoint Strategies for Market Dominance," John Wiley & Sons, 1993.
• 15: Philippe Lalanda , Cristina Marin, A Domain-Configurable Development Environment for Service-Oriented Applications, IEEE Software, v.24 n.6, p.31-38, November 2007 [doi>10.1109/MS.2007.154]
• 16: Matthias Kaiser, Toward the Realization of Policy-Oriented Enterprise Management, Computer, v.40 n.11, p.57-63, November 2007 [doi>10.1109/MC.2007.406]
• 17: Tiziana Margaria, Service Is in the Eyes of the Beholder, Computer, v.40 n.11, p.33-37, November 2007 [doi>10.1109/MC.2007.398]
• 18: D.A. Menascé and V. Dubey,"Utility-based QoS brokering in service oriented architectures," IEEE 2007 Intl. Conf. Web Services (ICWS 2007), Application Services and Industry Track, Salt Lake City, Utah, July 9-13, 2007, pp. 422--430.
• 19: Daniel A. Menascé , Honglei Ruan , Hassan Gomaa, QoS management in service-oriented architectures, Performance Evaluation, v.64 n.7-8, p.646-663, August, 2007 [doi>10.1016/j.peva.2006.10.001]
• 20: Olivier Nano , Andrea Zisman, Guest Editors' Introduction: Realizing Service-Centric Software Systems, IEEE Software, v.24 n.6, p.28-30, November 2007 [doi>10.1109/MS.2007.166]
• 21: Randolph Nelson, Probability, stochastic processes, and queueing theory: the mathematics of computer performance modeling, Springer-Verlag New York, Inc., New York, NY, 1995
• 22: Michael P. Papazoglou , Paolo Traverso , Schahram Dustdar , Frank Leymann, Service-Oriented Computing: State of the Art and Research Challenges, Computer, v.40 n.11, p.38-45, November 2007 [doi>10.1109/MC.2007.400]
• 23: M. Papazoglou, "Web Services: Principles and Technology," Prentice Hall, 2008.
• 24: M. Adel Serhani , Rachida Dssouli , Abdelhakim Hafid , Houari Sahraoui, A QoS Broker Based Architecture for Efficient Web Services Selection, Proceedings of the IEEE International Conference on Web Services, p.113-120, July 11-15, 2005 [doi>10.1109/ICWS.2005.13]
• 25: T. Yu and K. J. Lin, "Service Selection Algorithms for Composing Complex Services with Multiple QoS Constraints," Proc. of 3rd Int'l Conf. on Service Oriented Computing, pp. 130--143, Dec. 2005.
• 26: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Patterns (e.g., client/server, pipeline, blackboard)
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Stochastic analysis

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Experimentation, Performance

Keywords:
heuristic, optimization, qos, service composition, service oriented architecture