re s u lt
q u e ry ()
In v o k e_ W S _ 1
In v o k e _ W S _ 1 ...
... E n d U N IT
O u tp u t_ W S _ 1 I nte g e r
In p u t_ W S _ 1
In te g e r S ta rt ()
U N IT
In v o k e _ W S _ 1 ()
re s u lt () ()
5() ...
R e ce iv e_ W S _ 1
R e ce iv e_ W S _ 1
S e n d _ W S _ 1
S e n d _ W S _ 1 ...
... E n d U N IT
... U N IT
... U N IT O u tp u t_ W S _ 1In te g e r
In p u t_ W S _ 1 In te g e r S ta rt U N IT
S e n d _ W S _ 1 R e ce iv e_ W S _ 1
Figure 6: Example nets that present the main pages of CWS. On the left there is CWS with invoke operation and on the right there is CWS with send and receive operations.
- the place that represents the beginning of CWS should not contain input arcs, and the color of this place determines what are input parameters to this CWS,
- the place that represents the end of CWS should not contain output arcs, and the color of this place determines output from this CWS,
- transitions that represent the interactions with external WS have 1 input and 1 output arc (the interactions are functions),
- to allow faster identification of markings, which is used in the analysis of occurrence graphs, we should name the end place with ”End” and the transitions for the interactions with the name of used WS.
5 Analysis of CWS
One of the Petri Nets analysis methods are occurrence graphs [24]. In this work we use them to analyze composite web services to find out how failures of required WS may influence the overall CWS execution.
An occurrence graph is a graph, which has a node for each reachable marking (a distribution of tokens between places) and an arc for a transition and its binding (called binding elements) [24]. This graph is the basis for checking whether CWS can be executed successfully even if one or more used web services do not respond, which as described in Section 4 is modeled as a ”No response” type of output and in the colored Petri Nets as an output place of an interaction with the unit color set. To perform such checking we must infer the reachability of a marking that represents a success of CWS execution from markings that represent different outputs from external web services.
Occurrence graphs are a very useful tool for our purpose, the only problem is that even for simple CWS they may become very large. This happens because we model interactions with external components and we do not know what is the actual result of this interaction. For example for interaction from Figure 4 there can be as many different results as there are elements in the color set ”Integer”. If this interaction is the part of the CWS modeled in Figure 6 and the Integer color set consists of 100 elements, the occurrence
graph has 404 nodes and 30401 arcs. These values become greater if we have more parameters or more complex results from external web services. At some point the analysis may even be intractable.
To overcome the problem of very big occurrence graphs we use occurrence graphs with equivalence classes (OE-graphs) [24], which can reduce the number of nodes and make the state space analysis more tractable. An equivalence specification is a pair (≈M,≈BE), where≈M is equivalence relation on markings and ≈BE is an equivalence relation on binding elements [24]. In the context of modeling CWS we define those equivalence relations on results from used web services, according to how the results are used in CWS. Hence we can assume that all the results from the web service are equal, or we can define several classes of them. The equivalence for markings is:
M1≈M M2⇒ ∀p∈P : (M1(p) =M2(p) ∨ (p∈(X(TW S)∪P N) ∧ M1(p)≈resultM2(p))) where:
- P is a set of all places,
- P N is a set of port nodes (places between pages in a hierarchy),
- TW S is a transition that represents call to an external web service (as defined in the previous point), - X is function that maps a node to a set of its surrounding nodes,
- ≈result is an equivalence relation on results from the web service.
From the above definition two markings are the same if the only places they differ are the input or output from an interaction page or places surrounding a transition for an interaction with an external WS.
Additionally colors for those places are equal as we defined for the WS’s results. The binding elements equivalence is:
BE1≈BE BE2⇒(t(BE1) =t(BE2)∧ (∀v∈V ar(t(BE1))(b(BE1)(v)≈resultb(BE2)(v)))) where:
- tmapsBE to its transition, - bmapsBE to its binding,
- V ar(t) is set of variables for transitiont, - ≈result is the same as previously.
From the definition two binding elements are equivalent if they are for the same transition and the bindings for variables are equivalent according to the relation defined for the WS’s results.
For the CWS from Figure 4 and Figure 6 we can assume that all results from the web service are equal.
Figure 7 presents an occurrence graph with equivalence classes for this CWS. Each node is specified with a name of place that is not empty in a marking, binding elements (arcs) are omitted, because they are straightforward for this example. By the specification of equivalence relationships we reduced the number of nodes from 404 to 8, and the number of arcs from 30401 also to 8.
To use an OE-graph to check an influence of failures of other web services on CWS we need to check reachability of successful execution of CWS. A marking that represents this state is the one that contains token element only in a place named ”End”, thusmisMsuccess iff:
((m∈M) ∧(m(pEnd)6=empty) ∧(∀p6=pEndm(p) =empty)) where:
8
1 :0
E nd E nd
7
2 :1
O utpu t_ W S _ 1 O utpu t_ W S _ 1
4
1 :1
O u tp ut_ W S _ 1_ N o O u tp ut_ W S _ 1_ N o
5
1 :0
O utpu t_ W S _ 1_ Ex c O utpu t_ W S _ 1_ Ex c
1 :1
O u tp ut_ W S _ 1_ M sg O u tp ut_ W S _ 1_ M sg
3
1 :3
Inp u t_ W S _ 1_ M sg Inp u t_ W S _ 1_ M sg
2
1 :1
In pu t_ W S_ 1 In pu t_ W S_ 1
1
0 :1
S ta rt S ta rt
Figure 7: An example of an occurrence graph with equivalence classes (nodes are identified by names of non-empty places).
Figure 8: The preparation and analysis of an occurrence graph.
- M is a set of all markings in an OE-graph, - pEnd is a place named ”End”.
Analogously we can identify nodes and markings in an OE-graph that represent exceptional or no response types of output for each used external web service. Then we check the reachability ofMsuccess from all those states. If the success is reachable we can execute CWS even if there is an exception or no response, otherwise in case of a failure of a component we cannot execute CWS successfully. In the OE-graph in Figure 7 the successful marking is represented by a node 8. It can be concluded that even if the external web services is not responding (node 4) we can use it, but we cannot overcome exceptional messages (node 5).
The summary of the analysis of occurrence graphs in colored Petri Nets used in our approach is shown in Figure 8. The analysis consists of 2 main steps: preparation of OE-graphs and their usage. In the first step appropriate classes of equivalence are defined and then an OE-graph is constructed. In the second phase we first find a node in the graph that represents the successful state of execution and then nodes
dest
dest dest
{flight = flight, attractions = attr} attr
flight Invoke_ FindAttractions Invoke_FindAttractions Invoke_ Find Flight
Invoke_ FindFlight Flow
C reate plan FindAttractions_ InputD estination FindFlight_ InputDestinatio n
FindFlight_ O utput
FlightN o FindAttractions_ O utputAttractions
End Pla n S tart 1 `" "
D estination
Invoke_ FindFlight Invoke_FindAttractions
Figure 9: An example of CWS and WSDL descriptions for used operations
that represent each used web service’s failure or exception. We perform on those nodes the reachability analysis. The result of the analysis is the answer to question whether CWS can be executed if one or more external WS fail.