# A Model for Automated Service Composition System in SOA Environment

Pawel Stelmach, Adam Grzech, Krzysztof Juszczyszyn

► To cite this version:

Pawel Stelmach, Adam Grzech, Krzysztof Juszczyszyn. A Model for Automated Service Composition System in SOA Environment. 2nd Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Feb 2011, Costa de Caparica, Portugal. pp.75-82, 10.1007/978-3-642-19170-1_8 .
hal-01566564

HAL Id: hal-01566564

https://inria.hal.science/hal-01566564

Submitted on 21 Jul 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Model for Automated Service Composition System in SOA Environment

Paweł Stelmach¹, Adam Grzech¹, Krzysztof Juszczyszyn¹

¹ Wrocław University of Technology, Institute of Computer Science, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland
{ Pawel.Stelmach, Adam.Grzech, Krzysztof.Juszczyszyn } @pwr.wroc.pl

**Abstract.** In this paper a holistic approach to automated service composition in Service Oriented Architecture is presented. The model described allows to specify both functional and non-functional requirements for the complex service. In order to do so a decomposition of the complex service composition process into three stages is proposed, in which a structure, a scenario and an execution plan of a complex service is built. It is believed that service composition tool based on the proposed model will be able to create complex services satisfying efficiently both functional and nonfunctional requirements.

**Keywords:** service oriented architecture, service composition, SOA.

## 1 Introduction

The current trend in business is increasingly leading to the use of external services. The number of such services is growing and will grow even faster in the future. Soon delegated services will not be limited to simple tasks performed by individual providers, but they will be complex services performing complex business processes.

Business process designers are rarely experts in web-services technology. More often they can specify the business process in the form of functional requirements that are abstract to the underlying software infrastructure. As a consequence a service composition system should focus on formalization and interpretation of the functional and non-functional requirements in order to find services that fulfill them at a given time and are not hardcoded into the business logic.

The composition of Web services makes that a reality by building complex workflows and applications on the top of the SOA model [5, 8, 3, 13]. However, literature shows a wide range of composition approaches [1, 2]. In [4] it is mentioned that, rather than starting with a complete business process definition, the composition system could start with a basic set of requirements and in the first step build the whole process, whereas many approaches (i.e. [6]) require a well-defined business process to compose a complex service.

Current work often raises the topic of semantic analysis of user requirements, service discovery (meeting the functional requirements) and the selection of specific services against non-functional requirements (i.e. execution time, cost, security). Review of the literature indicates, however, that these methods have not yet been successfully combined to jointly and comprehensively solve the problem of
composition of complex services that satisfy both functional and non-functional requirements. In many cases only one aspect is considered. For example [9] focuses on services selection based only on one functional requirement at a time. [6, 14, 15, 16, 17] show that non-functional requirements are considered to be of a key importance, however many approaches ignore the aspect of building a proper structure of a complex service which is key to optimization of i.e. execution time. Many AI Planning-based approaches ([7]) focus on functionalities of the complex service but leave no place for the required non-functionalities satisfaction.

The following sections will present an approach to service composition which models functional and non-functional requirements (in section 3) and in section 3 the decomposition of the service composition task that fulfills both functional and non-functional requirements. Section 5 shows an example to visualize the composition process.

## 2 Contribution to Sustainability

Service Oriented Architecture (SOA) is an approach which prolongs the life of applications, increasing their reusability by publishing them as web services which can be accessed independent of the system (i.e. its programming language) that wants to use them. They are accessible through their web-enabled interfaces by the means of XML message system. In the case of SOA legacy applications or their parts can be searched and executed whenever functionalities are needed but those functionalities have to be properly modeled in order to conduct a successful search. In this context automatic service composition allows for sustainability of the system through the re-use of various web-services in a form of complex web-services.

## 3 Complex Service Composition Problem Definition

### 3.1 Service Level Agreement

The Service Level Agreement (SLA) is a contract that specifies user requirements:

$$SLA_l = (SLA_{lf}, SLA_{lnf}) \qquad (1)$$

where $SLA_{lf}$ are the functional requirements, $SLA_{lnf}$ are the non-functional requirements and $l$ stands for a $l$-th complex service request.

The functional requirements have to be fulfilled by functionalities offered by a set of atomic services. Those services composed in a specific structure form a complex service fulfilling both functional and non-functional requirements (like availability, performance etc.).

Functional requirements consist of request of functionalities and some time dependencies among them:

$$SLA_{lf} = (\Phi_l, R_l) = (\{\phi_s, \phi_{l1}, \phi_{l2}, \dots, \phi_{lk}, \dots, \phi_k\}, R_l) \qquad (2)$$
where:

* $\Phi_l$ is a set of functionalities $\phi_{li}$, in which $\phi_s$ and $\phi_k$ are starting and ending functionalities

* $R_l$ is a set of time dependencies among functionalities such that:

$$r_{ijl} = \begin{cases} 1 & \text{when } \phi_{li} < \phi_{lj} \\ 0 & \text{otherwise} \end{cases} \text{ and } r_{ijl} \in R_l, \text{ where } i, j \in \{1, 2, \dots, n_l\}$$

* $n_l$ is a number of required functionalities in $SLA_{lf}$

Non-functional requirements are represented by a set of constraints:

$$SLA_{lnf} = \{\psi_{l1}, \psi_{l2}, \dots, \psi_{lk}, \dots, \psi_{lm_l}\} \quad (3)$$

where $\psi_{li}$ is a requirement of a single non-functionality – a constraint put on the composed complex service (i.e. required execution time of the whole service) and $m_l$ is a number of required non-functionalities in $SLA_{lnf}$.

## 3.2 Service Composition Task

The service composition task is formulated as follows:

**for a given**

* request of a complex service $SLA_l$

* repository of services AS: $as_k$ is a k-th atomic service,

* family of execution graphs $\{G(V, E)\}$ representing all possible execution plans of the requested complex service in which vertices contain services ($as_k \in V$) and edges from E define the succession of services in a complex service,

**find** an optimal execution plan G(V,E) of a complex service, fulfilling the functional and non-functional requirements by minimizing the quality criterion:

$$G(\{as_1^*, as_2^*, \dots, as_k^*\}, E^*) \leftarrow \min_{as_1, as_2, \dots, as_k, E} Q(G(\{as_1, as_2, \dots, as_k\}, E), SLA_l) \quad (4)$$

where:

* $as_1^*, as_2^*, \dots, as_k^*$ are the selected optimal services that belong to corresponding k-th vertex of graph G (each vertex contains one service that fulfils one functional requirement), where optimal means that all services fulfill functional requirements and no other set of services gives better non-functional properties of the complex service (given a set of edges E)

* $E^*$ is an optimal set of edges that determines the succession of services $as_1^*, as_2^*, \dots, as_k^*$. Optimal means here that no other set of edges gives better non-functional properties of the complex service and that the set of edges is minimal, meaning no edge could be rejected without the loss of consistency of the graph.
# 4 Problem Decomposition

Service composition process can be described as a series of graph transformations beginning with the transformation of users requirements (SLA<sub>l</sub>) to the graph form and ending with an execution graph representing the complex service fulfilling the functional and non-functional requirements of the SLA<sub>l</sub>. The service composition problem can be decomposed into three stages:

* **structure**: SLA<sub>l</sub> is given a graph form, where all functionalities are embedded in vertices and time dependencies are expressed in the form of edges (preferably in the minimal number of edges possible without loss of information),

* **scenario**: the set of edges of the graph is extended so that the graph is consistent (complete information about order of execution of all functionalities is known) and service repository is searched in order to find services capable of providing requested functionalities,

* **execution plan**: for each vertex only one service is chosen (from candidates gathered in the previous step), so that all the services in the structure fulfill the non-functional requirements.

## 4.1 Complex Service Structure Stage

At this stage users requirements are transformed into the form of the graph. Each vertex contains one functionality required by the user and each edge represents the order dependency between two requirements (services that fulfill them). In the resulting graph there can be less edges that would appear from the set of time dependencies $R_l$. This is because a simpler structure is preferred if the simplification does not change the correct order defined in $R_l$. Fig. 1 depicts the situation where in the left side there is a graph with dependencies defined by the user while graph on the right after simplification has a serial structure (with edge (c) omitted). All the dependencies are still valid.

<figure><img src="image_2.png" /><figcaption>Fig. 1 Reduction of complexity of the structure.</figcaption></figure>

The task is formulated as follows:

**for a given** SLA<sub>lf</sub> = ({φ<sub>s</sub>, φ<sub>l1</sub>, φ<sub>l2</sub>, ..., φ<sub>lk</sub>, ..., φ<sub>k</sub>}, R<sub>l</sub>)

**find:**

$$GB_l(VB_l, EB_l = EB_l^*): EB_l^* = \arg\min_{EB_{lk}} \|EB_{lk}\| \quad (5)$$

where:

- $VB_l = \{v_s, v_{b1}, v_{b2}, ..., v_{bk}, ..., v_{b_{nl}}, v_k\}, v_s = \phi_s, v_{b1} = \phi_{b1}, v_k = \phi_k$

- $EB_l \ni eb_{ijl}$, such that $\forall r_{ijl} \in R_l$ if $r_{ijl} = 1$, then exists a path $d(v_{b_i}, v_{b_j})$
## 4.2 Complex Service Scenario Stage

**Adding missing edges.** The graph obtained at the previous stage rarely is consistent. However, there cannot be any functionalities that have no connection with the rest of the graph, because this would result in them not being executed at all. The task is formulated as follows:

**for a given** $GB_l(VB_l, EB_l)$ **find** a consistent graph $GC_l(VC_l, EC_l = EC_l^*)$ such that:

$$EC_l^* = \arg\min_{EC_{ls}} d_{max}(GC_l(VC_l, EC_{ls}), vb_s, vb_k) \quad (6)$$

where:

* $d_{max}(GC_l(VC_l, EC_{ls}), vb_s, vb_k)$ – length of the longest path from vertex $vb_s$ to vertex $vb_k$ in graph $GC_l(VC_l, EC_{ls})$

* $VC_l = VB_l$

* $EB_l \subset EC_{ls} = EB_l + EA_{ls}$

The criterion in (6) ensures that structures with a higher degree of parallelization are preferred. This will directly influence the non-functional properties of the complex service i.e. execution time.

**Services selection.** Based on the users functional requirements atomic services are selected from the services repository. Services are found after semantic and structural comparison of their descriptions and functionalities from graph $GC_l$. The problem of services selection could not approached in depth in this paper. For more information please refer to [10] and [11]. The task of services selection is formulated as follows:

**for a given**

* consistent graph $GC_l(VC_l, EC_l)$ (in each vertex containing functional requirements)

* service repository AS

**find:**

* graph $GS_l(VS_l = \{AS_{l1}, AS_{l2}, ..., AS_{lk}, ..., AS_{lnl}\}, ES_l)$ of valid realizations (services fulfilling the functional requirements) such that:

$$\exists j \in \{1, 2, ..., j\} as_j = as_{lk_u} \in AS_{lk} \text{ if } \varphi(as_{lk_u}) \supset \varphi_{lk} \text{ for each } u = \{1, 2, ..., u_{lk}\} \quad (7)$$

where:

* $as_{lk_u}$ is a service that fulfills requirement $\varphi_{lk}$ and $u_{lk}$ is a number of services that fulfill that requirement (and will replace it in appropriate vertex $AS_{lk}$ in graph $GS_l$)

* $\varphi(as_{lk_u})$ are functionalities offered by the service and $\varphi(as_{lk_u}) \supset \varphi_{lk}$ means that service $as_{lk_u}$ offers more or equal functionalities than required

* $AS_{lk} = \{as_{lk_1}, as_{lk_2}, ..., as_{lk_{u_{lk}}}, AS_{lk} \subset AS, AS_{lk} \in VS_l\}$
## 4.3 Complex Service Execution Graph

After the scenario construction stage, each vertex of graph GS contains a number of services that satisfy the corresponding functional requirements. To obtain the execution graph $G_1$ in each node of graph $GS_1$ one service has to be selected, such that – with regard to the edges that create the structure of the graph – the complex service consisting of selected services fulfills the non-functional requirements. The task is formulated as follows:

**for given**

* graph $GS_l(VS_l = \{AS_{l1}, AS_{l2}, ..., AS_{lk}, ..., AS_{lnl}\}, ES_l)$,

* non-functional requirements $SLA_{lnf} = \{\psi_{l1}, \psi_{l2}, ... \psi_{lk}, ... \psi_{lml}\}$,

* weight $w_{lk}$ of k-th non-functionality of $SLA_{lnf}$.

**find**

* an optimal execution graph $G_l(V_l, E_l)$ such that:

$$G_l(V_l, E_l) \leftarrow \min_{G_{lp}(V_{lp}, E_l)} \sum_{k=1}^{m_l} w_{lk} [\psi_{lk} - f_{\psi_k}(G_{lp}(V_{lp}, E_l))] \quad (8)$$

where:

* $G_{lp}(V_{lp}, E_l) \in FG_1(V_l, E_l)$ – family of valid execution graphs (each vertex contains one service selected from $AS_{lk}$ : $V_{lp} \ni v_{lpk} = \{as_j \in AS_{lk}\}$ and the set of edges stays the same as in $GS_1$ graph: $E_l = ES_l$)

* $m_l$ – length of vector of non-functional requirements $\Psi_l$ of l-th service request

* $f_{\psi_k}(G_{lp}(V_{lp}, E_l))$ is a function aggregating non-functionalities (corresponding to $\psi_k$) of atomic services embedded in the execution graph $G_{lp}(V_{lp}, E_l)$

with subject to the following constraints:

$$\forall_{k=1}^{m} : f_{\psi_k}(G_{lp}(V_{lp}, E_l)) \leq \psi_{lk} \quad (9)$$

# 5 Example

**For given:**

$SLA_{lf} = (\{\varphi_1, \varphi_2, \varphi_3\}, R_l)$, where $r_{ijl} \in R_l: r_{ijl} = \begin{cases} 1 & \text{for } i = 1 \text{ and } j = 2 \\ 0 & \text{otherwise} \end{cases}$
(for simplicity $\varphi_s$ and $\varphi_k$ are omitted in this example)

$SLA_{lnf} = \Psi_l = [7,4]$; $w_{l1} = 1, w_{l2} = 2, \psi_{l1}$ – cost, $\psi_{l2}$ – time,
Service repository $AS = \{as_j\}, j = 1,2, ... J$, where:

$\varphi(as_1) = \varphi_1, \varphi(as_2) = \varphi_2, \varphi(as_3) = \varphi_3, \varphi(as_4) = \varphi_3, \varphi(as_5) = \varphi_3, ...$ \\
$\psi(as_1) = [2,1], \psi(as_2) = [3,2], \psi(as_3) = [2,2], \psi(as_4) = [1,4], \psi(as_5) = [3,1]$
**Find** optimal complex service execution graph $G_1(V_1, E_1)$ that fulfills the SLA.

**Solution:**

In the **structure** stage from the given SLA$_{lf}$ only one possible can be obtained:

$$GB_l = GB_l(\{\varphi_1, \varphi_2, \varphi_3\}, \{(\varphi_1, \varphi_2)\})$$

In the **scenario** stage there are numerous possible consistent graphs (Fig. 3). As (6) ensures the more parallel structure is preferred (here: $d_{max}(GC_l^*, vb_s, vb_k) = 1$) and the optimal graph $GC_l^*$ is obtained:

$$GC_l^* = GC_{ln}(\{\varphi_1, \varphi_2, \varphi_3\}, \{(\varphi_1, \varphi_2), (\varphi_1, \varphi_3)\})$$

<figure><img src="image_3.png" /><figcaption>**Figure 2** Possible scenarios of a complex service.</figcaption></figure>

In step two of scenario stage for each functional requirement services that fulfill it are selected from the repository AS and so graph $GS_1$ is as follows:

$$GS_1(\{AS_1 = \\ \{as_1\}, AS_2 = \{as_2, as_3\}, AS_3 = \{as_4, as_5\}\}, \{(AS_1, AS_2), (AS_1, AS_3)\})$$

In the **execution graph** stage based on the non-functional parameters of selected service an optimal execution graph can be found:

$$G_l(V_l^*, E_l) = G_l(v_{l1}^* = \{as_1\}, v_{l2}^* = \{as_3\}, v_{l3}^* = \{as_5\}, \{(v_{l1}^*, v_{l2}^*), (v_{l1}^*, v_{l3}^*)\})$$

For the above execution graph G the value of quality criterion (8) is minimal:

$$\sum_{k=1}^{2} w_{lk} [\psi_{lk} - f_{\psi_k}(G(V^*, E_l))] = 1 * (7 - 7) + 2(4 - 3) = 2$$

# 6 Conclusions

The model for service composition presented in this paper allows for specification of both functional and non-functional requirements. The decomposition of the task allows for specification of three problems: transformation of user requirements into the structure of the graph, creating a scenario for the complex service by making the graph consistent and selecting services and at last finding the execution graph for the service that fulfills all requirements. The proposed approach takes into consideration the fact that constructing an appropriate structure for the complex service and selection of services with various non-functionalities are crucial to the problem of fulfilling non-functional requirements and should not be solved separately.

During the next stage of development the security assessment of atomic services will be taken into account, according to formal approach recently presented in [12]. This will allow to address security as an important non-functional property of complex services, barely covered in recent research and practical applications.

A composition framework based on the presented model is developed and will be made available in the form of package of tools for service composition.

The incoming stage of the project also assumes the application and evaluation of the framework in an industrial scenario.
Acknowledgments.

The research presented in this paper has been partially supported by the European Union within the European Regional Development Fund program no. POIG.01.03.01-00-008/08.

References

1. Jinghai R., Xiaomeng S., A Survey of Automated Web Service Composition Methods, Semantic Web Services and Web Process Composition, First International Workshop, SWSWPC, San Diego, CA, USA, 43-54 (2004)

2. Milanovic N. and Malek M., Current Solutions for Web Service Composition, IEEE Internet Computing 8(6), 51-59 (2004)

3. Charif Y., Sabouret N., An Overview of Semantic Web Services Composition Approaches, Electronic Notes in Theoretical Computer Science 146 33–41 (2006)

4. Aggarwal R., Verma K., Miller J., Milnor W., Constraint Driven Web Service Composition in METEOR-S, Proceedings of the 2004 IEEE International Conference on Services Computing, 23 – 30 (2004)

5. Blanco E. Cardinale Y., VIDAL M., GRATEROL J., Techniques to Produce Optimal Web Service Compositions, IEEE Congress on Services, 553-558 (2008)

6. Jong Myoung K., Chang Ouk Kim, Ick-Hyun Kwon, Quality-of-service oriented web service composition algorithm and planning architecture, The Journal of Systems and Software 81, 2079–2090 (2008)

7. McIlraith S., Son T., Adapting Golog for composition of semantic web services, Proceedings of 8th Intl. Conf. of Knowledge Representation and Reasoning (2002)

8. Ponnekanti S. R. and Fox A.,: SWORD: A developer toolkit for Web service composition. In Proceedings of the 11th World Wide Web Conference, Honolulu, HI, USA (2002)

9. Klusch M., Fries B., Sycara K., OWLS-MX: A hybrid Semantic Web service matchmaker for OWL-S services, Web Semantics: Science, Services and Agents on the World Wide Web 7, 121–133 (2009)

10.Stelmach, P.; Prusiewicz, A., An improved method for services selection, XVII International Conference on Systems Science, Wrocław (2010)

11.Stelmach P.; Juszczyszyn K., Grzelak T., The scalable architecture for the composition of soku services, 31st International Conference on Information Systems, Architecture, and Technology, Szklarska Poręba (2010)

12.Kolaczek G., Juszczyszyn K: Smart Security Assessment of Composed Web Services. Cybernetics and Systems 41(1): 46-61 (2010)

13.Agarwal V., Chafle G., Dasgupta K., Karnik N., Kumar A., Mittal S., Srivastava B., Synthy: A system for end to end composition of web services, Web Semantics: Science, Services and Agents on the World Wide Web In World Wide Web Conference 2005, Semantic Web Track, Vol. 3, No. 4., 311-339 (2005)

14. Zeng L., Kalagnanam J., Quality Driven Web Services Composition, 12th International Conference on the World Wide Web, 411-421 (2003)

15. Huang A.F.M., Lan C., Yang S.J.H., An optimal QoS-based Web service selection scheme

16. Karakoc E., Senkul P., Composing semantic Web services under constraints, Expert Systems with Applications. Vol. 36, No. 8, 11021-11029 (2009)

17. Jong Myoung Ko, Chang Ouk Kim, Ick-Hyun Kwon, Quality-of-service oriented web service composition algorithm and planning architecture, Journal of Systems and Software Vol. 81, No. 11., 2079-2090 (2008)