3rd International ICST Workshop on Advanced Architectures and Algorithms for Internet Delivery and Applications

Research Article

Optimal Service Selection Heuristics in Service Oriented Architectures

Download
431 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-10625-5_50,
        author={Emiliano Casalicchio and Daniel Menasc\^{e} and Vinod Dubey and Luca Silvestri},
        title={Optimal Service Selection Heuristics in Service Oriented Architectures},
        proceedings={3rd International ICST Workshop on Advanced Architectures and Algorithms for Internet Delivery and Applications},
        proceedings_a={AAA-IDEA},
        year={2012},
        month={10},
        keywords={Service Oriented Architecture Web services service composition QoS heuristics},
        doi={10.1007/978-3-642-10625-5_50}
    }
    
  • Emiliano Casalicchio
    Daniel Menascé
    Vinod Dubey
    Luca Silvestri
    Year: 2012
    Optimal Service Selection Heuristics in Service Oriented Architectures
    AAA-IDEA
    Springer
    DOI: 10.1007/978-3-642-10625-5_50
Emiliano Casalicchio1,*, Daniel Menascé2,*, Vinod Dubey2,*, Luca Silvestri1,*
  • 1: Università di Roma “Tor Vergata”
  • 2: George Mason University
*Contact email: casalicchio@ing.uniroma2.it, menasce@gmu.edu, vdubey@gmu.edu, silvestri@ing.uniroma2.it

Abstract

Service Oriented Architectures allow service brokers to execute business processes composed of network-accessible loosely-coupled services offered by a multitude of service providers, at different Quality of Service (QoS) and cost levels. To optimize their revenue and the offered QoS level, service brokers need to solve 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. This optimization problem is clearly NP-hard. Optimized algorithms that find the optimal solution without having to explore the entire solution space have been proposed to solve problems of moderate size. A heuristic search of the sub-optimal solution scales to problems of large size and is appropriate for runtime service selection. This paper evaluates the performance of three heuristic service selection algorithms that are candidates for implementation in scalable service brokers. Our goal is to identify which algorithm provides the solution closest to the optimal and how many selections are evaluated to find the solution. The comparison is made over a wide range of parameters including the complexity of the business process topology and the the tightness of the QoS and cost constraints.