When adapting services in a SOA environment, not only the validity of the adapter may be of importance, but also non-functional properties like the costs of the adapter. We introduce an approach for nding cost-e cient adapters based on the operating guideline, which characterizes all valid adapters for the given services.
In the context of Service-Oriented Architectures (SOA) [
Especially in corporate environments costs like time, memory or money are relevant factors for components. So if a company decides to use an adapter, it may want that the overall runtime of the adapter stays below a certain limit in order to guarantee some real-time constraints or the costs for using third parties should be minimized. Besides this demand, the adapter still needs to be valid { the original goal to resolve incompatibilities must be maintained.
Our approach focuses on the minimization of the most expensive run of an adapter, meaning that for every other valid adapter the most expensive run is at least as expensive as for the calculated adapter.
The paper is structured as follows: In Sect. 3 we will describe the approach which covers both the validity and the cost optimization of adapters. Before it, we will introduce the basic formalisms in Sect. 2, namely open nets and operating guidelines. In the last section, we will summarize the obtained results and give an outlook on extensions of this approach.
An adapter is an artifact acting as mediator between services. This is necessary if the adapted services are incompatible regarding their interface or their behavior. ? Supported by German Research Foundation (DFG) under grant RE 834/18-1 (a) Provider (b) Adapter
D F
B
E (d) Cost-e cient adapter (c) Requester The adapter then should overcome these incompatibilities and guarantee a well behaved interaction of the services.
There are di erent approaches for adapters like [2{6] and recently also [
In [
Open nets The used adapter approach is based on open nets, an extension of Petri nets, where distinguished places act as interface.
De nition 1. The tuple (P; I; O; T; F; m0; ) is called an open net i { (P; T; F; m0) is a Petri net with a set of places P , a set of transitions T , a ow relation F P T [ T P and an initial marking m0 : P ! N, { I and O are disjoint sets of input I P and output O P places, I \O = ;, and { is a set of nal markings.
Two open nets can be composed ( ) by merging equally named input and output places. The ring rule is equivalent to the one of regular Petri nets. A marking is not called a deadlock if it is included in the set of nal markings.
The nets depicted in Fig. 1 are open nets. The places on the dashed border form the interface, all places belonging to the initial marking contain a black (!D +#!6E1+ !F) (!B +#!4E9+ !F) !D !F !B !E !B !F (!E#+54!F) (!D# +30!E) !F !D !E !B #!E23 (!B#+18!E) !D !E # 39 !F !E !F !D # 8 ifnal
!B !B !D (!A + !B + !C#+0!D + !E + !F) !F !E !C
!A (!A + !B +#!C1+ !D + !E) (!A + !B +#!C33+ !D + !F) !D !E !B !E !D !C !F !A !F !C (!D# +46!F) (!B#+34!F) (!A + !B#+2!C + !D) !F !B !E !F !B !D #!D15 #!B3
(!A#+26!E) !C !E !A !F # 11 !A (!A +#!5E7+ !F) !E
(!C +#!6E3+ !F) !A !F !A !E !C (!A# +42!F) (!C# +32!E) (!C# +48!F) (!E#+60!F) !E !A !C !F !A !C !F !E #!C17 #!E29 #!4F5 !A !C !E !F # 14 ifnal token and places belonging to a nal marking are shown with a two line border. If the nets in Fig. 1 are composed as implied by the gures' alignment, the composition will be deadlock free.
Adapters The open nets P and R represented in Figs. 1(a) and 1(c) are not
compatible, since the number of exchanged messages does not t. Based on
certain message transformation rules provided with the two services an adapter
like Fig. 1(b) might be build based on the considerations in [
In our example let A-F be such rules that transform messages. Instead of
executing these rules arbitrarily, we provide an interface such that these rules
can be triggered by an controller. This controller will ensure certain properties
like deadlock freedom, if wanted (see [
Figure 2 shows such a controller. The graph, called Operating Guideline, is a labeled transition system, where each edge label represents an event, namely the sending or receiving of a message. Furthermore each node n has an annotation over the labels of the edges leaving n. A satisfying assignment corresponds to a valid combination of edges, that have to be included in an controller, such that the controller is valid. In this paper we assume the operating guideline to be acyclic.
The controller part C can be transformed to an open net using the approach
in [
Looking at the possible adapters for P and R, besides some control structures we can mainly distinguish each single adapter by the transformation rules it can execute. It is legitimate to assume, that these transformation rules generate the costs in a corporate environment. In the simplest case, time is consumed to apply such a rule. In a more distributed scenario, such a transformation might be done by an external service provider, which will result in a fee which must be paid.
Just eliminating expensive transitions in the adapter is not an solution for
nding cost-e cient adapters. When changing the adapter, we have to ensure
that the correctness criterion like deadlock free communication is maintained.
Therefore approaches like [
The operating guideline calculated during the adapter synthesis contains all information about legal adapters. Therefore an cost optimization should be done on this structure. There are two points we have to take care of, namely i) the most expensive run of the adapter shall be minimized and ii) the resulting structure must still be a valid adapter (thus, P A R still must be deadlock free).
If we look at any given adapter A, it is still possible that A has di erent execution traces, i.e. sequence of events, depending on internal decisions in the services P and R.
The costs for one run of the adapter, a trace of events, is simply the sum of each applied message transformation. Thereby the cost function is a mapping of every transformation rule r 2 R to a natural number: c : R 7! N. De nition 2. The costs of a trace t is the sum of its contained events: c(t) = k P c(ri) for t = (r1; : : : ; rk). i=1
We will focus on the question, which is the worst case, meaning, which are the highest costs we have to anticipate regarding the possible traces of A. De nition 3. The costs of an adapter A is the maximum costs over all traces k of A: c(A) = max P c(t).
t2traces(A) i=1
Based on Def. 3 our optimization goal is to nd an adapter, whose costs are at most as expensive as for any other valid adapter.
De nition 4. An adapter A is cost-e cient if for any other adapter A0 yields c(A) c(A0).
The controller introduced in the previous section contains all information necessary for nding cost-e cient adapters. The annotations provide details about which other controllers are valid, and since every application of an transformation rule is communicated, it also contains all execution traces as a branching structure.
In order to nd an cost-e cient adapter we will annotated each edge with a set of traces as follows. Given these edge annotations, we will compute an assignment for each node's annotation.
The costs incurred by using an edge is the maximum (the worst case) costs of the traces that are possible via this edge.
De nition 5. The costs of an edge e is the maximum cost of its assigned traces: c(e) = max c(t).
t2traces(e)
Given a satisfying assignment for the annotation of a node n, states which edges leaving n have to be included in a controller in order to be valid. The node's costs regarding then is the maximum over the edges' costs (again, the worst case).
De nition 6. The costs for a node n and an assignment n is the maximum cost of the edges e leaving n, which corresponding literal is set to true in n: c n (n) = max c(e).
n(e)=true
Since every satisfying assignment yields in a valid adapter, we choose an assignment, which results in the minimal costs for a node.
De nition 7. The costs for a node n is the minimum costs over all assignments n satisfying n's annotation : c(n) = min c n (n).
( n)=true The assignment n, which minimizes c(n) is called the minimal n.
Given the previous de nitions the following algorithm will calculate a coste cient adapter.
Algorithm Let P and R be two open nets, E a partial adapter, and C the operating guideline for P E R. Then an cost-e cient adapter can be found as follows:
Initially all edges have no traces assigned, and all nodes have in nite costs, except for the leaf nodes (without successor), which have costs 0 (resulting from Def. 7). Then, as long as there are nodes with in nite costs, pick such a node n, so that each successor n0 of n has nite costs c(n0) < 1. Assign for each edge e = (n; n0) the set of traces according to the minimal n0 of n0: traces(e) = flabel (e) + t0 j t0 2 traces(e0); n0 (e0) = trueg (meaning: each new trace starts with label (e) followed by the events in the traces of e0). Afterwards the costs c(n) can be calculated.
The costs for resulting adapter A = E C are the costs of C's root node.
Since we assume the operating guideline to be nite and acyclic, it can be easily seen, that the suggested algorithm will terminate, and all nodes will have nite costs. Furthermore we gain a valid controller (implied by the found minimal assignments), which minimizes the costs.
Theorem 1. The provided algorithm nishes with a controller C such that A = E C is a cost-e cient adapter for P and R.
Proof. (Sketch.) This result yields mainly due to Def. 7. The adapter A is valid,
since for each node n of the controller, the minimal n satis es n's annotation
(see [
We have seen an approach which calculates a cost-e cient adapter based on an annotated graph which acts as controller for the application of the message transformation rules. By nding optimal assignments to the nodes' annotations we obtain a smaller, but valid adapter, where expensive runs can be excluded.
The time for nding such an adapter is exponential in the number of applicable message transformation rules in the worst case, since for every node all satisfying assignments must be checked. Nevertheless in most cases the approach should yield the result in a reasonable time, since the annotations are normally short and therefore quickly to be checked. In order to show its feasibility, this algorithm shall be implemented and checked with real-world examples.
As extension of this approach probabilities for the occurrence of events shall be introduced, so that the average costs of an adapter can be calculated. This extension would also allow to lift the optimization to cyclic controllers. Although cyclic adapters are nite, the have however in nite traces and therefore in nite costs.