When designing a publicly available Web service, a service designer has to take care of costs and revenue caused by this services. In the very beginning possible partners might only be vaguely known, or the service behavior contains arbitrary repetitions. Then the estimation of costs for running this service is difficult and decisions based on them can hardly be made. We propose a static analysis of the service's behavior. We over-approximate possible runs and therefore costs of the service. Our approach provides a basis for reasoning about nonfunctional properties as shown for costs.
A service provider in a service-oriented architecture (SOA) [
For two services A and B, question is: How much does it cost the provider of A to interact with B? As a prerequisite, we assume that each action a of A has a distinct cost. However prior to execution, it is impossible to give one discrete overall cost: Both A and B may contain non-determinism resulting in different runs of their interaction. So we propose an interval for the overall cost instead. Naively, we can explore the whole state space to determine the minimal and maximal overall costs, taking only into account the maximal runs, that is those that are either infinite or end in a deadlock state. This however can be very complex and may be impossible, if the state space is infinite or too big to fit into memory.
We thus propose a simplification of the previous question: If both A and B terminate, how much did the interaction cost the provider of A? If we further assume that termination always means reaching a final state ! of A, the question boils down to: How much does it cost the provider of A to reach ! from its initial state when A and B are coupled? We identify three core challenges:
(i) As for the overall cost, the cost of reaching ! is not one distinct number but a cost interval C = (cmin; cmax), because there typically exists not only one, but a set R of runs from to !, which can even be infinite. (ii) We find the nature of R not only being dependent on the behavior of A, but also on the behavior of B. (iii) ! is not necessarily reachable in the interaction of A and B, resulting in an undefined cost interval.
In this paper, we will tackle those three challenges with classical Petri net analysis.
We translate the model of the composition A B into a system of linear equations – the
state equation [
If B is not given as a model, but only as a set of constraints, we build the state
equation of A alone and augment it by the constraints in . Again, we use linear
optimization which yields a valid over-approximation X0 = (x0min; x0max) of C. We
observe that X0 is not as tight as X: X0 is valid for a whole set of partner services
B (induced by ) in contrast to only one explicitly given partner service B. However,
computation of X0 can be done in a less time critical phase, whereas X is computed after
B has been selected and also requires a complete behavioral model of B. Furthermore,
we attend the special case that = ;, resulting in the complete set of partners of A,
similarly to the work in [
The third challenge is harder to come by. In this paper we aim at ensuring, that if A reaches !, then the found cost interval applies. The found cost intervals for each final marking can be composed for a global overview over costs. To avoid complexity from this source, we draft a method to directly find minimal and maximal costs for given sets of final markings.
The rest of the paper is structured as follows: In Sect. 2 we introduce the necessary formal notions. Section 3 describes the approach itself together with the above announced specializations and generalizations. Finally we will conclude and will give an outlook for application. 2
Let f : A ! B be a function, then for A0 A, f (A0) is defined as ff (a) j a 2 A0g. For the rest of this paper, let us assume a set C of message channels and message exchange to be asynchronous, messages may even overtake each other. Sending a message over channel a is denoted by !a and receiving a message over channel a is denoted by ?a. Then E = f!c j c 2 Cg [ f?c j c 2 Cg denotes the set of all sending and receiving events, respectively. Furthermore, each service uses a channel in at most one direction: sending or receiving (viz. a service cannot unsent a message).
Now an open net N = (P; T; F; ; ; ev ) is a classical P/T-net [
t5 t4 ?abort p3 p4 !invoice t6 t7 !shippingData aborted p5 p6 t8
= f[aborted]; [done]g !add ?added !abort !checkout ?invoice shippingData usual, places are depicted by circles, transitions by rectangles and the flow relation by arcs. Tokens are black dots, labels are written inside the transitions, omitting .
initial t2 ?add t3 !added p2
p1 initial’ !login done done'
The open net shop models an online shop. After logging in, a customer can decide to add products by sending messages via channel add which are confirmed via added. The customer can either decide to send an abort message or to checkout. After receiving a message via checkout, the shop sends information about shipping and an invoice. The two final markings [done] and [aborted] specify the two expected results of the interaction. The open net customer is a partner of shop: Their interfaces are compatible.
We assume the standard firing semantics for transitions, thus !t 0 means a step
from to 0 by firing t. A transition sequence t0t1t2 : : : is called firing sequence of
N if there exists a sequence of markings 0 1 2 : : : , such that 0 = and for each
i = 0; 1; 2 : : : , i t!i i+1 is a step of N . Note that for each firing sequence, there
exists exactly one corresponding sequence of markings. We thus say that a finite firing
sequence t0t1t2 : : : tn ends in n+1. We call a finite firing sequence terminating, if it
ends in a final marking. The Parikh vector [
?a !a !b ?b ?b a
b
The composition of two partners N and N 0 to the open net N N 0 is realized by introducing buffer places and corresponding arcs as depicted in Fig. 3. Inspecting the structure of N N 0, we find that a firing sequence of N N 0 corresponds to one firing sequence of N as well as one of N 0, allowing us to analyze N in isolation and draw conclusions for the behavior of N in N N 0.
Thus, let N; N 0 be partners and ; 0 be markings of N; N 0 respectively. Then, r 2 Beh(N N 0; + 0) implies rjT 2 Beh(N; ) and rjT 0 2 Beh(N 0; 0).
We now introduce costs for actions of services into our formal model. Each transition t has a globally fixed integer cost, denoted as cost(t). The cost of a transition sequence only depends on its Parikh vector: cost(r) = cost(occ(r)) = Pt2T occ(r)(t) cost(t). Let be a marking of an open net N . If Beh(N; ) 6= ;, then the minimal and maximal cost of in N are defined as min(fcost(r) j r 2 Beh(N; )g) and max(fcost(r) j r 2 Beh(N; )g), denoted as ?(N; ) and >(N; ) respectively. Otherwise, the minimal and maximal cost are undefined. Let T 0 T , then ?(N; )jT 0 and >(N; )jT 0 denote the minimal and maximal cost for by only taking into account transitions in T 0.
As an example, consider that the transitions t1; : : : ; t8 of the open net shop in Fig. 1 have costs of 10; 5; 1; 10; 5; 20; 20; 1 respectively. Then, the firing sequence t1t2t3t2t3t4 has a cost of 32. For marking [p3] the cost interval is (15; 1). 3
The state equation [
The Parikh vector of any firing sequence ending in is a solution of the state equation. As an example, consider open net shop in Fig. 1: t1t2t3t2t3t5t6t7t8 is a firing sequence ending in the marking [done]. Its Parik vector is 1 2 2 0 1 1 1 1 , which is a solution of the state equation. The reverse does not hold for the general case: By solving the state equation tokens can be "borrowed" from and "given back" to places, leading to an effect of 0, although no firing sequence with this solution as a Parikh vector exists. Obviously, X(N; ) is a valid over-approximation of occ(Beh(N; )). Because the cost of a firing sequence is only dependent on its Parikh vector, the state equation is a valid mechanism to estimate costs for a given marking.
In this section, we present two approaches: First, we show how for two given services the costs for one provider can be estimated by solving the state equation of the composition of their models. Then, we explain how this approach can be generalized to the setting where the second partner is only represented by a set of constraints. For the second approach, we can shift the analysis effort to a time-uncritical phase. Ensuing, we have a critical look at both approaches, collecting results for the open net shop in Fig. 1. Finally, we draft how our general approach can be extended from estimating costs for a given state to a given (even infinite) set of states.
N 0; ! + !0) 6= ; implies min(cost(X(N >(N N 0; ! + !0)jT max(cost(X(N
Thus, the costs for the provider of N can be estimated by solving the linear problem
for each final marking of 0. From our experience, the number of final markings
is very small, if not 1. As an example, evaluating the state equation for the composite
shop customer, we find two cost intervals: (56; 74) for the final marking [done+done0]
and (20; 38) for [aborted + done0], which we can compose to an overall cost estimation
of (20; 74). We observe, that this is the actual cost interval. Obviously, the approach is
symmetrical: The costs for the provider of N 0 can be estimated analogously. We will now
generalize our approach from a completely known open net N 0 to a set of constraints,
describing a set of services.
Assume now that not an open net N 0 is given but a set of constraints of the following
syntax and semantics: A constraint is an inequality or equation l r where 2 f ; ; =g,
consisting of an integer linear combination l of event labels and an integer value r. An
open net N 0 solves l r if for any terminating firing sequence in N 0, its event occurrence
vector solves l r. N 0 solves the set of constraints, if N 0 solves each 2 . We
denote the set of open nets solving with B . As an example, the open net shop in
Fig. 1 solves the constraints ?login = 1 and ?add !added = 0. [
Intuitively, we take the state equation of N and augment it correspondingly with the given set of constraints : Because every message has been consumed in a final marking of the composite, we find that for each sent message of a partner of N , N has received the message and vice versa. Thus, for each message x sent (received) by N 0, a transition receiving (sending) x of N has fired once. This induces a set of constraints b(N ) = fPt2T l(ev (t)) t r j l r 2 g on the transition occurrence of N . As an example, consider the open net shop in Fig. 1 and assume = f!add 10g as well as N 0 2 B . Then, in any terminating firing sequence of N N 0 the only transition with label ?add, namely t2 fires only up to 10 times, thus b(N ) = ft2 10g.
Therefore, the state equation of N with respect to ! together with b(N ), its solutions denoted as X (N; !), over-approximates all firing sequences ending in ! + ! of N N 0 if N 0 2 B .
Lemma 2. N 0 2 B implies Beh(N
N 0; ! + !0)jT
X (N; !).
Analogously to our approach with full knowledge of N 0, we can conclude that for a given , the costs for the provider of N for N interacting with an N 0 2 B can be over-approximated by using the state equation: Theorem 2. N 0 2 B ?(N N 0; !)jT
and Beh(N >(N
N 0; !)jT
N 0; ! +!0) 6= ; implies min(cost(X (N; !)))
max(cost(X (N; !))).
Thus, solving the linear program for each ! 2 yields a valid cost estimation. Expecting j j to be small, this approach seems feasible for use in practice. Furthermore, we draft in Sect. 3.4 how a valid cost estimation can directly be computed for a set of final markings. We have collected a small number of results in Table 2. The table shows for the open net shop in Fig. 1 how the actual cost intervals (cmin; cmax) and the estimated cost intervals (xmin; xmax) for a selected final marking ! correspond for partners specified by . The results were gained manually; there does not exist an implementation yet. In the example, the estimated cost interval is identical with the actual cost interval for any . We also see that open net customer in Fig. 2 solves f1 !add 10g. Composing the second and fifth row in the table, we find an estimated cost interval of (20; 116), which is not as tight as the former result (20; 74), but still valid.
In the general case however, results are not necessarily this precise. A factor are t-invariants, transition vectors x, such that IN x = 0. For the open net shop in Fig. 1, 0 1 1 0 0 0 0 0 is a t-invariant. Obviously, if y is a solution of state equation S and x is a t-invariant, then for any n 2 N holds that y +n x is also a solution of S. One can create an example with a t-invariant that never fires, intuitively an unmarked loop structure. Thus, if a t-invariant x exists and cost(x) > 0 (cost(x) < 0), cost estimation yields unbounded for the upper (lower) bound, unless there is an additional constraint bounding it. For the t-invariant x = 0 1 1 0 0 0 0 0 , cost(x) is greater than zero. Constraining it through the constraint set f1 !add 10g bounds the cost interval because x can not be added arbitrarily often due to bounding the occurrence t2. It is up to future work to find a way to handle t-invariants and to use them as a starting point for narrowing down interesting . Solving one linear program for each ! 2 is not feasible for big or even infinite . For the case that we can express or approximate the given set of markings as a set of linear constraints, we build a system of linear inequalities similar to the state equation and use the same techniques as described above. 4
In this paper, we presented an approach to estimate the costs for the provider of a service A for interacting with a service B. Thereby, we concentrated on two scenarios: Either the partner B is known in detail, then the estimation process boils down to static analysis of the composed system A B. Or, B is not known and only narrowed down by a set of constraints . In this case, we analyze the behavior of A in isolation, constraining it according to . The downside of static analysis is a loss of precision, for which we identify t-invariants as an important factor. Still, we find that our approach tackles the first and the second challenge introduced in Sect. 1. For the case of a not reachable final marking, our approach might yield a cost interval although it is not defined. We consider this a low price to pay in contrast to the state space explosion problem. 5
In [
In this paper, we only considered a single fixed cost for each atomic action of a
service. As a start it is intuitive that a certain step has always the same costs. A natural
extension would be allow intervals [