The selection of services of a workflow based on Quality of Service (QoS) attributes is an important issue in service-oriented systems. QoS attributes allow for a better selection process based on non-functional quality criteria such as reliability, availability, and response time. Past research has mostly addressed this problem with optimal methods such as linear programming approaches. Given the nature of service-oriented systems where large numbers of services are available with different QoS values, optimal methods are not suitable and therefore, approximate techniques are necessary. In this paper, we investigate Genetic algorithms and particle swarm optimization for the service selection process. In particular, both methods are combined with an optimal assignment algorithm (Munkres algorithm) in order to achieve higher solution qualities (success ratios) and to form a so called memetic algorithm. Experiments are conducted to investigate the suitability of the approaches and to compare the memetic algorithms with their non-memetic counterparts. The results reveal that the memetic algorithms are very suitable for the application to the workflow selection problem.
The distribution of software systems has increased over the last decade. There are many different reasons for this increase, and one of them is the need to integrate and connect heterogeneous applications and resources within organizational, but also across organizational boundaries. In particular, most legacy systems and applications were designed for their specific purpose, but not with the view in mind that they need to be integrated with and adapted to different application scenarios. This lack in the design of these legacy systems require new paradigms and approaches to be integrated to cope with these challenges.
Service-orientation provides the conceptual principle necessary to deal with the integration challenges as well as with the increasing complexity by providing adaptive software units referred to as services. Services are characterized by properties such as loose coupling, well-defined service contracts, and standardization that allows them to be independent of any particular implementation technology [1].
The idea behind service-oriented computing is that businesses offer their application functionality as services over the Internet, and users or companies can make use of these services by composing and integrating these services into their applications. Service-oriented architecture is the concept that combines this idea. Fig. 1 describes the basic components of the service-oriented architecture that are the providers, requesters and registries. The service provider publishes the service description in a service registry, and a service requester can query a service from the registry, and dynamically bind it to one of the services that are returned by the search query.The main idea of service-orientation is to compose these services by discovering them and then dynamically invoking them when building applications, rather than building them from scratch or reusing other applications. Service composition (also called orchestration) enables the development of building service-oriented applications using existing services. The result of this composition process is referred to as a composite service. In this paper, we assume that all available services are validated pre-runtime, so that failure cannot occur during the composition process due to incompatibility. The standard orchestration language is WS-BPEL (Web Service Business Process Execution Language) [2]. Choreography is another term used in service-oriented environments that describes the message interchanges between the different participants in service-oriented systems. It provides the global distributed model of message exchanges without the need of a central coordinator [3]. The Web Service Choreography Description Language (WS-CDL) [4] is one of the first languages for describing the global model of service interactions.
One primary requirement of service-oriented systems is the ability of self-adaptivity [5]. Self-adaptivity in the area of service-oriented environments means that the system should be able to adapt its behavior depending on the changes within its environment. A possible solution for this adaptability, in particular for service composition, is the concept of Quality of Service (QoS). All non-functional attributes of a service, such as performance-specific attributes, are described by QoS. QoS attributes can be categorized into deterministic and non-deterministic attributes [6]. Non-deterministic QoS attributes, such as response time, have uncertain values during service invocation. It is necessary to provide as accurate as possible values for all QoS attributes for composite applications and their execution.
A Service Level Agreement (SLA) is a contract between a service provider and a service consumer that captures the agreed-upon terms with respect to QoS parameters. Considering a service-oriented computing environment, capabilities are shared via the implementation of web services exposed to by a service provider. When a service requester requires a specific functionality, which cannot be provided by one single service, the composition of multiple services needs to be done thereby creating a workflow. The composition of web services should not only be functionally compatible, but should also be compatible with regards to the defined service levels. In particular, QoS attributes need to be considered for the dynamic binding process of the concrete services available. Therefore, QoS-aware composition is necessary given the changing and dynamic environment of service-oriented systems (services come online or go offline, new services become available, or existing services change their characteristics).
This paper addresses the workflow selection using approximate algorithms such as Genetic algorithms (GA) and Particle Swarm Optimization (PSO) for the optimization process. Furthermore, the selection of services is based on QoS parameters as well as on service level agreements. Preliminary results have shown that the approximate algorithms achieved an optimized service selection that were higher than that of a random selection and took less time than the optimal algorithm, however, the solution quality needs to be further improved. In order to address this, we apply the memetic algorithm idea of combining an evolutionary algorithm or swarm intelligence algorithm with a local search technique in order to balance the exploration and exploitation of the search space, and therefore, achieving higher solution quality. GA as well as a PSO approach is combined with an optimal search method called the Munkres algorithm. Both algorithms are implemented and experiments show that the combination achieves much higher solution qualities applied to the workflow selection problem than the basic GA and PSO. In particular, it balances the high computational complexity of the Munkres algorithm is balanced with the stochastic advantages of the GA and PSO.
This paper is structured as follows. Section 2 describes related work in the area. In Section 3, background information on workflows, quality of service, and service level agreements are given. Section 4 outlines and describes the approaches implemented and the experiments conducted. The results are displayed in Section 5. And last but not least, Section 6 summarizes the findings and gives an account to future work.
6. Conclusions
This paper addressed the service composition task of workflows applying the concept of memetic algorithms to GA and PSO. Memetic algorithms are usually a combination of an evolutionary algorithm with a local search method. In this paper, given that we have a combinatorial optimization problem, GA and PSO have been combined with the Munkres algorithm, which is an optimal combinatorial assignment algorithm.
In the area of service-oriented systems, the service selection process has been done primarily using linear programming methods. However, given that linear methods do not scale well with increasing problem sizes, i.e., workflow sizes, an approximate method is paramount. The approximate methods such as GA and PSO achieve an optimized assignment in a reasonable amount of time. However, in order to further improve the solution quality, and tackling the problems the approximate methods face, namely the balance between exploitation and exploration, we have combined GA and PSO with the Munkres algorithm, therefore, achieving the benefits the memetic algorithms enjoy.
The results show that the memetic algorithms achieve higher success ratios than their non-memetic counterparts. The execution times of the memetic algorithms are as expected higher than the non-memetic algorithms.
Comparing the success ratio of both MA and MPSO showed that MPSO has slightly higher success ratios than MA. Furthermore, analyzing MA for increasing population sizes revealed a slight upward trend towards higher success ratios. Similarly, looking at MPSO a slight improvement in success rations is observed for increasing particle sizes.
The effect of different Munkres portions on both memetic algorithms was investigated. In terms of execution times, the high computational cost the Munkres portion places on both algorithms can be observed when the portion gets larger. As for the success ratio, larger increases are seen first with smaller increases following. This reveals that a good balance between improved success ratio and execution time needs to be chosen.
Given that scalability is a very important issue in service-oriented environments, different workflow sizes were investigated. The success ratio dropped substantially for larger workflow sizes. This shows that if the success ratio needs to remain constant for different numbers of workflow sizes the number of generations needs to be increased, as well as the population size and particle size for MA and MPSO needs to be increased, respectively. However, this comes at the cost of higher execution times, and therefore, need to be traded off carefully.
Overall, a general recommendation is to make use of the memetic algorithms for the workflow selection optimization since they achieve very good success ratios with slightly larger execution times than the non-memetic algorithms, by having an improved execution time as opposed to using an optimal algorithm such as the Munkres algorithm.
Future work will expand this line of research by taking the following constraints imposed by the real world setting of service-oriented systems into consideration. First of all, service invocations of a particular service are limited, and therefore, need to be taken into account. In addition, failure of the service execution and recomposition needs to be addressed, and a solution needs to be implemented and evaluated. Furthermore, since the workflows and concrete services were fairly similar in terms of range, the effects of larger variations on the QoS values of the workflow services need to be investigated.
