Service orchestrations are a common means to compose individual services to either higher-level services or potentially complex composite applications. The Web Service Business Process Execution Language (WS-BPEL) is an example for a language that allows for de ning automatically executable orchestrations of Web services. As of today, BPEL process are typically executed in a centralized manner; the process model is deployed on a single work ow management system which, during process instance execution, interprets the process de nition and interacts with the orchestrated Web services on behalf of the user. In previous work, we have presented an approach which enables decentralized execution of BPEL processes based on a decentralized process model and supporting runtime infrastructure. In this paper we describe a method for automatic splitting of a process among the partners participating in its execution, referred to as process partitioning.
One of the key aspects of the Service-oriented Architecture (SOA) are service
compositions following the so-called two-level programming paradigm where
individual reusable services are composed into high-level services or potentially
complex service orchestrations which can executed automatically using work ow
management systems (WfMS). The means for de ning the \wiring" between the
compound services is provided by work ow de nition languages such as the Web
Service Business Process Execution Language (WS-BPEL) [
However, a number of reasons, ranging from outsourcing of process fragments
to runtime performance optimizations without the need for process model changes,
motivate the need for a decentralized execution environment for BPEL processes.
Hence, in previous work [
The remainder of the paper is structured as follows. In Section 2 the EWFN process model provides the basis for the proposed approach is described to the extend necessary for the discussion of the partitioning procedure. Based on this foundation, Section 3 introduces the general idea of process partitioning, discusses various parameters that in uence process partitioning and outlines a procedure that addresses each of the de ned partitioning parameters. In Section 4 a brief overview of a few related approaches which are either particularly relevant to the problem discussed in the paper due to either addressing the concrete problem of partitioning BPEL processes or similar parameters in uencing process partitioning are presented. 2
Coordinating a number of distributed clients, where each of those clients realizes a de ned part of an overall process requires communication of both process control ow and process instance data among the clients participating in the process' execution. In this context, control ow refers to the individual client's execution being started according to the order de ned in the process model; the term instance data characterizes both data being \visible" in process models such as BPEL variables, partner links (which can be source or destination of assignment operations) or correlation sets as well as \invisible" instance data such as the state of a scope or the state of incoming message activities. While this information is provided in the WS-BPEL speci cation through a description of the language's operational semantics, this description is { due to its informal textual nature { neither suitable for automatic execution by WfMSs nor may it serve as input for process partitioning.
As a result, the formalism of Executable Work ow Networks (EWFN) has
been developed on the basis of colored, non-hierarchical Petri nets [
PartnerLinks Assign Variables
Ended
Check for open IMA tu3 Check Correlation Consistency t2 te5 Failed IMA States tu4
te2 te6 te6
Finalize Reply tu7 3 t Ended Ended WS t4Endpoint t4 Reply
Correlations
Variables PartnerLinks
Figure 1 depicts the EWFN representation of a BPEL sequence activity with two contained activities. Activities are depicted as dashed rectangles and comprise (similar to Petri nets) transitions and places. Following the EWFN formalism, transitions represent a piece of application logic and carry out the actual processing. Transitions coordinate themselves by consuming tokens from and producing tokens to places which provide passive bu ers for tokens; the tokens are self-contained in the sense that they provide enough information to uniquely identify each token communicated in an EWFN. On the level of the infrastructure supporting execution of EWFNs, places are realized by tuplespaces, transitions by tuplespace clients. The arcs between transitions and places represent the individual operations supported by the tuplespace interface and may be annotated with a weight representing the operation cost, resulting e.g. from the volume of the data being communicated as part of that operation.
As an example, transition t1 of the assign activity represents an assignment of a value to either a BPEL variable or a partner link. To represent process control ow t1 is activated by a token becoming available in its Start place; once t1 has nished its execution is signals its successful completion to the subsequent activity by producing a corresponding token to its Ended activity. Consuming and producing process control ow information is depicted as directed black arcs between places and transitions and transitions and places respectively. During execution of their application logic, transitions may consume and produce further tokens representing instance data; in case of the depicted assign activity this might include the modi cation of the value of a variable or the endpoint reference assigned to a partner link. Similar to BPEL activities, EWFNs can be nested as presented in the example with the sequence activity surrounding the assign and receive activities. The operational semantics of the sequence activity is de ned as each contained activity becoming ready to execute once its preceding activity has completed its execution. In the EWFN this is represented by collapsing the Ended place of the assign activity and the Start place of the receive activity into one place. 3
The term process partitioning refers to the procedure of assigning information about the partner the corresponding node of the EWFN is executed by during instance runtime to each transition and place of an EWFN. This process is in uenced by a number of parameters which can be classi ed in three groups. Process model As outlined before, the EWFN of a BPEL process provides a formal description of (i) the steps carried out during process instance execution and (ii) the data being communicated along the way. As a result it is one of the major parameters of the process partitioning procedure. Service infrastructure Through BPEL's interaction activities (e.g. invoke and receive) the BPEL process may interact with Web service clients and the Web services it orchestrates. As the partners providing a service used by the process are in any event process participants they are potentially suitable candidates for executing a part of the processes orchestration logic as well. Organizational factors Organizational factors re ect parameters that are not necessarily a result of the process structure or its service landscape, but are de ned manually by users. It might e.g. be desired to manually de ne the partition of a certain place that contains BPEL variable data for data ownership reasons.
The proposed process partitioning approach comprises three phases and is
an extension of the procedure presented in [
Fixed nodes represent nodes with partitioning information de ned a priori by manual user input and re ect organizational partitioning parameters. To allow for maximum exibility, each node of an EWFN { transitions and places { can become a xed node. Interaction activities, i.e. those points of a BPEL process Phase 1. Fixed Nodes
Examined Arbitrary nodes Interaction activities: Non-interaction
Objects invoke, receive, activities; instance
pick, reply data
Partitioning Manual assignment by Automatic service Graph partitioning
Method user; rules discovery and service applied to the process'
selection; rules EWFN
where interaction with its service landscape occurs, are referred to as heavy
nodes. Their partitioning information is determined automatically using means
for service discovery (based on the service's functional characteristics through its
WSDL description) and service selection (based on the service's non-functional
properties such as service invocation cost, service response time, etc. re ected
through WS-Policy descriptions). In addition, partitioning information of heavy
nodes might be dependent on deployment information (e.g. for de ning on which
endpoint the process can receive incoming messages) or other heavy nodes (e.g.
in case of receive-reply pairs to support synchronous Web service bindings).
Light nodes re ect non-interaction activities as well as process instance data
for which no partitioning information has been de ned until this point. Their
partitioning is performed by migrating them to the partition of adjacent xed
or heavy nodes as de ned in the process' EWFN. Since an EWFN is a directed
weighted graph and the problem is a variant of the well-known graph partitioning
problem with the optimization criteria of minimizing the cost of inter-partition
interactions, existing optimization algorithms such as Simulated Annealing [
In [
In this paper we have outlined a process model that enables decentralized execution of BPEL processes and allows for nearly arbitrarily fragmented process execution. Thereby we have stressed the need for an algorithm for de ning process partitions based on a number of in uential factors and have presented a high-level overview of the proposed algorithm and how it addresses the individual process partitioning parameters.