As Web services become the dominant technology for integrating distributed information systems, enterprises are more interested by these environments. However, enterprises socio-economic environments are more and more subject to changes which impact directly business processes published as Web services. In parallel, if at change time some instances are running, the business process evolution will impact the equivalence and substitution classes of the actual service. In this paper, we present an equivalence and substitution analysis in dynamic evolution context. We suggest an approach to identify residual services that can substitute a modi ed one, where ongoing instances are pending. Our analysis is based on protocol schema matching and on real execution traces. The proposed approach has been implemented in a software tool which provides some useful functionalities for protocol managers.
Web services are the new generation of distributed software components. They
generate a lot of enthusiasm among different socio-economic operators’s which
favourite these environments to deploy applications at a large scale.
Standardization is a key concept, so actors uses standards like WSDL [
In Web services technology, two elements are fundamental for providing a high
interactivity level between service providers and service requesters. The first
one is service interface, described via the standard WSDL. The second element
is service protocol (Business Protocol), which describes the provider’s business
process logic. A Business process consists of a group of business activities
undertaken by one or more organizations in pursuit of some particular goal [
In dynamic protocol evolution, the evolved service protocol may not be able to
satisfy initial customer requirements. Furthermore, some services may fails and
clients must find new services that can replace actual one. Services substitution
analysis deal with checking if two services satisfy the same functionalities; if
they support the same conversation messages [
In this paper we are interested to dynamic evolution and we focus on change impact analysis on service protocol substitution. A set of methods are exposed to check if new service version, can be yet substituted by the hole (or partially) set of services that were discovered corresponding to the obsolete version. The remainder of the paper is structured as follow. We start by describing the problem and exposing our motivations, in section 2. In section 3, we propose our formal approach and algorithms for managing substitution aspects in dynamic evolution context. Section 4, describes system architecture and software tool implementation. We expose related works in section 5 and conclude with a summary and directions for future works in section 6.
Every organisation (enterprises, administrations, banks, ...etc.) is an open system which is, eventually, impacted by environment changes. In order to survive, organization must adapt there business processes. Today’s organizations information systems -reflecting business processes- are exposed on the Web as services (interfaces and protocols) and every business process changes induce, immediately, these two descriptions update. The challenge in dynamic protocol evolution context is to identify, among the set of already identified class substitution services, the subset of those that can, yet, replace an actual service after its specification changes, with respect to past interactions. Addressing service protocols substitution analysis, after protocol evolution, responds to the following motivations: 1. Ensuring service execution continuation for active instances. 2. Ensuring correct interactions between customers and providers by specifying the new service substitution class. 3. In dynamic environments, like Web services, transactions are long duration and resources consumer. It’s not conceivable to restart execution from scratch because loss of work is catastrophic for customers. 4. In real time systems and critical applications (aeronautics, e-commerce, medical systems, control systems, manufacture,. . . ), brutal service stop is catastrophic for organizations. It is imperative to treat with precision and accuracy services that can substitute an evolved or failed one. 5. In large public applications (e-libraries, e-government, e-learning. . . ), a large number of active instances are pending, at a time. Manual management of these instances is cumbersome and an automatic support is required to ensure that only pertinent services are proposed for substitution process. The main issue is to manage protocol substitution with respect to historical traces. Starting a new search query for locating new services, based on the new version, is expensive and in addition, returned services that can be inconsistent with old version.
To illustrate our motivations, we present in Fig.1 a real world scenario. In this scenario, service protocol P have some equivalent services (P1, P2, . . . , Pn) and other services (P3, P4, . . . Pm) can substitute it. However, service P has evolved to a new version P ′ (for different reasons). Evolution operations added a new message cancelOrder and removed the message Order validated. At evolution time, active instances (instance 1, instance 2,. . . ), are running and have reached a particular execution level. In order to be able to substitute service P in case of problems, protocol manager want to know: Which protocols remain in conformance with the new protocol speci cation and can replace it ? 3
Analysing Substitution in Dynamic Protocol Evolution
One of the most challenging issues in dynamic protocol evolution context is to
find potential protocols for substitution, where instances are running
according to old protocol. To address this analysis, we introduce three fundamental
concepts: service protocol model, execution path and execution trace.
{ A service protocol: We use finite state machine to represent service
protocols. In this model states represent different phases that a service may
go through during its interaction with a requester. Transitions are triggered
by messages sent by the requester to the provider or vice versa [
S : A finite set of states; s0 2 S: is the protocol initial state; F : Set of final states machine, with F S; M : Finite set of messages; R (S S M ): Transitions set. Each one involves a source state to a target state following the message receipt. { Execution trace: Service behaviour traces is a finite sequence of operations (a, b, c, d, e, ...). It represents events that service have invoked, from its beginning to the actual state. We note : trace(P, i) to express the execution trace performed by an active instance i in a protocol P . { Complete Execution path: Represents the sequence of states and messages from an initial state to a final one. We note : expath(P ). 3.1
Let P and P ′ respectively, old and new service versions, after operating changes. EP = fPi (i = 1 . . . n)g: Is the services set equivalent to P . We note Equi(Pi, P ), the equivalence relationship between services.
Two service are equivalent if they can be used interchangeably and they provide the same functionalities in every context. Every service P i 2 EP can replace P . Equi(Pi, P ) , 8(i = 1 . . . n)(expath(Pi) expath(P ))^(expath(P ) expath(Pi)). (^ is the logic and operator). (1) Let SP = fPj (j = 1 . . . m)g: The services set that can substitute P . We note Subst(Pj, P ), the substitution relationship.
A service can substitute an other one if it provides, at least, all the conversations
that P supports [
Subst(Pi, P ) , 8(i = 1 . . . m)(expath(P ) expath(Pi) (2).
Based on this formalization we notice that if protocol P has evolved to a new version P ′, equations (1) does not remain valid. So we want to identify the protocols subset that satisfy equation (2), in order to provide services that can replace the evolved protocol.
From equation (2):Subst(Pi, P ′) , 8(i = 1 . . . m) (expath(P ′) expath(Pi). (3) . We conclude: Lemma 1:: If the changes related to protocol evolution are reductionist, all protocols (Pi) that can substitute P , can substitute the new reduced version P ′. Reducing Protocol description is an application of change operations including: { Loops removal. { Final sub-paths removal. { Operations and messages removal.
{ Complete paths removal and sub-protocols removal.
This change operation goals are motivated by procedures cancellation,
reducing tasks, business processes alignment, and so one. However, when changes are
additive, substitution analysis must consider the protocol difference. Protocol
difference between two protocols P ′ and P describe the set of all complete
execution paths of P ′ that are not common with P [
In order to replace P ′, each protocol Pi 2 SP must be able to replace the new requirements (the difference P ′/P ).
Subst(Pi, P ′) ) Subst(Pi, P ′/P ) , 8(i = 1 . . . m) (expath(P ′/P ) expath(Pi) (4). We conclude: Lemma 2: If changes are additive, protocols subset SP which are containing the difference P ′/P can substitute the new extended version P ′. Additive changes are operations performing: { Adding loops. { Adding sub-paths { Adding messages and operations .
{ Adding new complete paths and sub-protocols.
Protocol schema based analysis is rigid and does not take into account the actual execution for active instances. Really, it’s possible that a protocol Pi 2 SP can’t substitute an evolved one in general, but by taking into account execution traces, it can do that for specific instances. As an example, let a protocol P and its active instances i1, i2, . . . , in, as mentioned in Fig.1. In parallel, protocol changes have added new states and messages to a particular path: part-path. After analysing active instances execution traces, we see that all instances have’t executed this unexpected path part-path. In this case, even if we can’t replace P ′ with a protocol Pi 2 SP , basing on protocol schema analysis, we can substitute it basing on real execution traces, because changes do not impact real instances. We notice that execution traces may inform protocol managers on how to proceed with substitution analysis. We propose two substitution analysis based execution traces: Historical execution paths and state execution paths.
Let histpath a protocol p historical execution path executed by an active instance i, during its execution, instance i has invoked an operations sequence : a, b, c, d, e, . . .. And, let futurpath: future paths not yet executed by this instance. If P ′ is the new version of P , after changes and SP is the protocol set that can substitute P . We are interested by filtering instances that are not concerned with changes. We consider protocol changes as the difference between P ′ and P : P ′/P . In this situation, if protocol Pi 2 SP can’t substitute P ′, contrarily, it can substitute it for the instances subset that have not executed this difference. We note: Subst(Pi, P ′)/Occurj: The substitution of P ′ by Pi for occurrence j. Subst(Pi, P ′)/Occurj(i = 1 . . . n), j = 1 . . . m)is is possible if : (histpath(occurj) 2/ allpaths(P ′/P ) .(5),where Allpaths(P ′/P ) is the hole possible paths set generated by protocol difference P ′/P . This means that, substitution is possible if actual instance i had executed an old path not affected by changes.
Historical execution path analysis is more general and based on the hole historical execution paths. Although, protocols P ′ 2 SP can’t replace P in the general case, substitution is possible for some states. We need to compute which states are not affected by changes. Substitution analysis must deal with this kind of traces by selecting protocol services that substitute active service by considering actual state and future execution path.
As an example, consider the execution path from Fig. 1: If a subset of actual instances are in the state: Order made, so their execution trace are : begin.order made. A service Pi 2 SP can substitute P ′ if it can replace it from the actual state and future execution paths. We don’t consider past execution paths because changes occurs after the state (Order made). We formalize this analysis as follows: Let futurpaths the future execution path set of an active instance (all future paths), and s the actual instance i state.
Subst(Pi, P ′)/state(s) : (i = 1 . . . n) if : (f uturpaths(state(s)) allpaths(P ′/P )) ^ (trace(P, i) 2 histpath(P i)) .(6) 3.3
System Architecture and Software tool presentation
We have implemented the software performing substitution analysis in
JavaEclipse environment. Service protocols are implemented as automata and saved
in XML files. The software performs some operational functions useful for
protocol manager like protocol description and correctness specification. Furthermore,
it allows final users performing different changes operations. The system kernel
provides checking static equivalence and substitution. Fig. 3. Based on schema
definitions or on execution traces, the system strength is dynamic analysis. This
analysis allows user to select a particular protocol, operate changes and then
proceed to change impact analysis on protocol substitution. The system filters
the protocol database, analysis logs directory and searches for the remaining
service protocols which can substitute the evolved version Fig. 4. We visualize,
below some screen-shots of the the software tool.
Protocol management and analysis had benefited for a lot off contributions, from
protocol schema matching to static evolution. But, dynamic protocol analysis did
not receive all the interest it deserves. In [
In this article we have formalized substitution problem inherent to dynamic protocol evolution. We have proposed an approach and a software tool for providing service protocols that can, yet replace an evolved one.
As future work, we plan to address protocol substitution analysis for richer protocols descriptions, such as timed and transactional constraints automata. In addition, we aim to specify protocol changes more formally by identifying evolution patterns and by their classification with respect to induced impact on protocol substitution and compatibility.