The Grid has emerged as a new distributed computing infrastructure for advanced science and engineering. It aims at enabling resource sharing as means to facilitate a problem-solving approach for dynamic environments that is based on the integration of available resources. Wide agreement that a °exible Grid is not possible without the support of semantic technologies, has lead to the term \Semantic Grid\. Transparent service composition has a great potential to facilitate the integration of Web Services deployed in the Grid. However, discovering, dynamically composing and optimizing large-scale Web Services (e.g., in the rank of 1,000 to 100,000 services) is a challenging problem. We approached the problem of Web Service compositions in the Grid as an optimization problem, in which for a given request a good plan has to be generated. In this work, we propose the de¯nition of several optimization strategies to identify good orderings of Web Service compositions.
The Grid provides the protocols, services, and software development kits needed to enable °exible, controlled resource sharing on a large scale. Automatic discovery and coordination of services in the Grid is not only desirable, but necessary. Users need tools that assist them on taking full advantage of the possible large number of available services. Any form of automated composition needs an infrastructure where all resources are adequately described in a machine-processable form. Semantic Web technologies provide the means to incorporate such descriptions to the Grid infrastructure leading to the Semantic Grid. Thus, it is possible to apply Semantic Web technologies in grid-computing developments.
Numerous e®orts have focused on the task of service discovery and Web
Service composition (the WSC problem). However, few have addressed the problem
of identifying e±cient Web Service compositions in a large-scale scenario, as
the one presented in the Grid vision [
In Grid platforms requests are usually scheduled as batch processes, and real time constraints are relaxed. Thus, it is possible to do a greater exploration of the space of possible Web Service compositions, while the batch process is waiting to be evaluated.
On the other hand, some Grid resources can only be accessed at certain times. It may be required to incorporate into the space of alternatives, the possibility of executions where intermediate results are stored and retrieved according to time restrictions. In other words, all services used by a plan do not need to be available at the same time.
In this work, we propose the de¯nition of optimization strategies to identify good orderings of Web Service compositions in large-scale Web Serviceenvironments, e.g., in the rank of 1,000 to 100,000 available services. These strategies will follow di®erent meta-heuristics to explore the space of possibilities, while minimizing the estimated evaluation cost. We have already de¯ned two strategies that prune the space of possibilities. Our initial results show that the compositions identi¯ed by our algorithms, are close to the optimal solution. 2
The problem of identifying a good WSC in the Grid is related to problems that have been studied in query optimization and WSC. In this section we consider the main related approaches in each of these areas.
In the context of the Web, several strategies have been presented to identify
good evaluation plans where sources have limited query processing capabilities;
then, the optimizer task is to identify a good ordering of the sub-goals of a query
where limited processing capabilities of each considered source, are satis¯ed [
Typically, existing approaches achieve the challenge of identifying good plans by representing query capabilities as binding patterns and using these patterns and meta-heuristics to traverse the space of source plans. Each sub-goal in the query is rewritten in the plan by using sources that de¯ne the sub-goal; limited processing capabilities of the sources are satis¯ed in the plan with query bindings or attributes projected out by previous sources in the plan.
The WSC problem has been extensively treated in the literature, and diverse solutions that take advantage of AI techniques and Search Meta-Heuristics, have been proposed. First, in the context of AI, the WSC problem has been represented as a planning problem where actions to be taken by the planner are de¯ned in terms of service preconditions and e®ects.
The description of a planning domain includes a set of planning operators and methods that establish the way a task can be decomposed into smaller subtasks. The description of a planning problem contains an initial state as in classical planning. Instead of a goal formula, there is a partially-ordered set of tasks to accomplish. Planning proceeds by decomposing tasks recursively into smaller and smaller subtasks, until primitive tasks, which can be performed directly by using one planning operator, are reached. For non-primitive tasks, the planner chooses an applicable method, instantiates it to decompose the task into subtasks, and then chooses and instantiates other methods to decompose the subtasks even further. If the constraints on the subtasks or the interactions among them prevent the plan from being feasible, the planning system backtracks and tries other methods.
As any planning problem, the approach presented in [
An approach that uses Answer Set Programming is presented in [
In the context of Search Meta-Heuristics, the SAM (Service Aggregation
Matchmaking) algorithm is de¯ned [
SAM follows a greedy approach in which only one sub-plan is generated in each iteration. In each sub-plan, a sub-set of the output attributes is produced considering some of the bindings given in the query. The algorithm ends when all the output attributes are produced. In terms of time, SAM is able to scale up in environments with a moderate number of services (e.g., in the rank of 100 to 200 services). However, since SAM does not consider any cost metric or optimization criteria to compose the services, plans produced by SAM may be costly. To exacerbate this problem, SAM may add processes to the plan that are not needed to produce the output required by the user. Thus, the quality of generated plans may be far from optimal.
Semantic Grid [
Finally, in [
We hypothesize that if there is a large number of Web Services published in di®erent sites then, services' performance may vary. Thus, it is imperative that solutions to the WSC problem consider an estimate of the service evaluation cost. This cost is used to prune the space of possibly costly plans of services, and to identify the service composition with the lowest estimated cost.
We propose solutions to the WSC problem for large-scale platforms, e.g., Grids. These solutions will be adapted to consider the dynamic characteristic presented in such platforms. In particular, we address the problem of selecting and coordinating services that satisfy some of the constraints presented in the Grid, while the evaluation time is minimized.
Plans will be generated considering the time constraints of Grid resources. Thus, we will incorporate into the space of alternatives, the possibility of executions where intermediate results are stored and retrieved according to these constraints. 4
To validate the quality of our techniques, we plan to conduct experimental studies that compare our approach against some of the existing projects. We propose to use at least two available test sets - EEE05 and ICEBE051.
We will also analyze the performance of our solutions in real-world scenarios.
For this, we will generate a large number of ontological Web Service
descriptions for a given scientist community. WSBen[
We consider that the project can be achieved within the following stages:
1. We propose approaches that adapt some optimization techniques to the WSC
problem. We have already de¯ned two extensions to the algorithm SAM.
Initial results show that the extensions are e®ective. In terms of plan quality
and optimization time, our generated plans, outperform results produced by
SAM [