All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

Performance Study of Workﬂow Patterns-Based Web Service Composition

Tags

Transcript

Procedia Computer Science 10 ( 2012 ) 728 – 735
1877-0509 © 2012 Published by Elsevier Ltd. doi: 10.1016/j.procs.2012.06.093
The 9th International Conference on Mobile Web Information Systems (MobiWIS)
Performance Study of Workﬂow Patterns-Based Web ServiceComposition
W. Ait-Cheik-Bihi
a,
∗
, A. Nait-Sidi-Moh
b
, M. Bakhouya
c
, J. Gaber
d
, M. Wack
d
a
Strasbourg University, Strasbourg, France
b
University of Picardie Jules Verne, Saint Quentin, France
c
Aalto University, School of Engineering, Helsinki, Finland
d
University of Technology Belfort-Montb´ eliard, Belfort, France
Abstract
Web services are currently used by organizations to share their knowledge over the network and facilitate business-to-business collaboration. However, combining Web services to satisfy user requests is a complex process. Workﬂowpatterns are widely used for Web service composition to allow the speciﬁcation of composite services. In this paper, theperformance evaluation and analysis of workﬂow patterns is presented. We use both (
max
,
+
) algebra and Petri Nets asformal modeling tools to describe the behavior of workﬂow patterns and analyze their properties and performances. Areal case study is worked out to represent and study the performances of integrated workﬂow patterns.c
2011 Published by Elsevier Ltd.
Keywords:
Web services composition, Workﬂow patterns, Performances evaluation, Petri Net, (Max,
+
) algebra.
1. Introduction
In Service-Oriented Computing (SOC), one of the main objectives is to create value-added services(i.e. composite service) [1], which is the result of composing many services. A composite service can bemodeled as a business process by using languages such as BPEL4WS or WSCI. The composite service isachieved through the invocation and coordination of its components [2], [3]. Service composition processis considered as a business process that must be made in an automatic fashion. Most of the languages usedto model the business process do not allow an automated composition and still based on manual deﬁnitionof new composed process that interacts with existing ones. A workﬂow pattern can be seen as the automaticmodeling and system management for all tasks and di
ﬀ
erent involved actors in a business process. In otherwords, a workﬂow pattern describes the tasks between the di
ﬀ
erent actors of a process, deadlines, validationmethods, and provides to each actor the information needed to fulﬁll its task. The use of workﬂow patternshas become a major asset providing a competitive advantage, as a way to reduce costs, automate processes,and reduce response times. Di
ﬀ
erent studies have sought to identify the basic needs for business processmodeling. The main result of these studies was the identiﬁcation of a set of control structures for describing
∗
Corresponding author. W. Ait-Cheik-Bihi, aitcheikbihi@unistra.fr
Available online at www.sciencedirect.com
729
W. Ait-Cheik-Bihi et al. / Procedia Computer Science 10 ( 2012 ) 728 – 735
workﬂow patterns, which are considered as modeling of a set of tasks performed by di
ﬀ
erent actors involvedin the realization of a business process. This process can be automated by invoking applications or externalservices and
/
or assigning manual tasks. In recent years much attention has been devoted to Web servicescomposition and their modeling in the form of a business process becomes increasingly popular. In thispaper, Petri net-based (PN) models and (max,
+
) algebra are combined for modeling and analyzing workﬂowpatterns. The developed models will be used to evaluate the performance of Web service composition basedon workﬂow patterns aggregation. We show that the complementarity of these formal tools leads to a high-level description of services composition and to the creation of a dynamic and transient relationships amongworkﬂow patterns.
2. Related work
ApproachesdealingwithformalmodelingofWorkﬂowpatternsforservicecompositioncanbeclassiﬁedinto two di
ﬀ
erent categories,
language-oriented approaches
and
model-oriented approaches
. The formerones focus on the veriﬁcation of
already existing
composite services expressed in a particular businessprocess modeling language, such as BPEL or WSCI. For example, a BPEL code can be translated into aformal description, and verify some properties. The main formalisms used are Petri nets, state transitionsystems (STS), and process algebras. For example, in [4], the authors proposed rules for complete andaccurate translation of BPEL process models to PN models. These translation rules were also widely usedin other tools such as WofBPEL, which is used for automatic veriﬁcation of BPEL processes.In the second category, the designer uses graphical representations, such as BPMN or UML, to spec-ify the service composition before generating the corresponding executable code. These business processmodeling languages are widely adopted or service composition, because of the design features they provide(support most of Workﬂow patterns) and being comprehensive enough to generate executable codes. How-ever, it is hard for designers to deal with formal veriﬁcation of service composition because neither BPMNnor UML are supported with suitable tools. Several approaches have been proposed to take this issue byproviding Workﬂow patterns models, and therefore designers can use them for specifying and verifying theservice composition. For example, Aalst et al. proposed over forty patterns in [5]. Among them, a varietymay be used to model communication and interaction between Web services. In the same context, authorsin [2] deﬁned fourteen of the twenty srcinal patterns and used them for the composition of Web services.They also deﬁned new patterns by composing existing ones. The new deﬁned patterns are mainly based onthe QoS as a selection criterion (e.g. cost and price ) in the composition of services. In [3], the authorsdeﬁned an approach based on workﬂow patterns, speciﬁcally nine patterns, to adapt the composition of ser-vices during the execution of business processes. Indeed, business processes are composed of Web servicesthat run in a volatile environment where the parameters of the QoS of participants can be changed duringthe execution time.Our contribution through this paper falls into the second category by using both Petri nets and (max,
+
)algebra to specify, verify, and evaluate the performance of workﬂow patterns. We will use P-Timed PNwherein ﬁxed times, called also temporizations are associated with places. These times are required for theexecution of services or tasks. (max,
+
) algebra is a linear mathematical algebra enabling the modeling andanalysis of certain systems whose behavior can be evolved in a discrete space. This tool has been used inthe literature to evaluate the performance and control the systems mostly with discrete events [6]. We willuse this algebra to manage and compute the occurrence dates of events. We refer readers to [7, 8] for moredetails about this algebra.
3. From Workﬂow patterns to (max,
+
) equations
In this section, we generate the (max,
+
) mathematical model of each considered pattern. Because weare constrained by the number of pages, we present only two potential patterns (e.g., multi-merge andconditional choice patterns) and their P-timed PN and (max,
+
) sate models. Other patterns used for theWeb services composition and associated models are detailed in [9]. The chosen patterns, are the most used
730
W. Ait-Cheik-Bihi et al. / Procedia Computer Science 10 ( 2012 ) 728 – 735
in the services composition process. In order to make easy the analysis of each pattern and evaluate itsperformances, we describe its behavior by using a (max,
+
) state system, which can be handled and solvedusing the techniques of matrix calculation in (max,
+
) linear algebra. Using a standard formalization, allpatterns may be expressed under the following matrix form:
∀
k
≥
1 :
X
(
k
)
=
A
0
⊗
X
(
k
)
⊕
A
1
⊗
X
(
k
−
1)
⊕
...
A
n
0
⊗
X
(
k
−
n
0
)
⊕
B
⊗
U
(
k
)
Y
(
k
)
=
C
⊗
X
(
k
) (1)With the marking of each place
P
of the PN model veriﬁes
m
(
P
)
≤
n
0
. The matrices
A
0
,
A
1
, ...,
A
n
0
,
B
and
C
are the characteristic matrices of the system whose components are the system data.
3.1. Multi-merge pattern
Multi-merge pattern is deﬁned by the merge of two or more incoming branches in a single downstreambranch, as shown in Fig. 1a. The activation of an incoming branch is enough for the activation of thedownstream branch. Although several execution paths are merged without any synchronization of controlﬂow, each active branch will therefore join the resulting merged branch. As illustrated in Fig. 1a, whenone of the transitions
x
1
,
x
2
, ...,
or
x
n
is ﬁred, the output transition
y
is activated and can be ﬁred afterthe temporization
τ
. However, it is not obvious to formally express the ﬁring number of the transition
y
according to the ﬁring number of its upstream transitions. With the aim to describe this functioning by(max,
+
) equations and to facilitate the mathematical analysis, we associated a place - called
counter
- toeach one of the transitions
x
1
,
x
2
, ..., and
x
n
. These counters (
P
1
,
P
2
, ...,
P
n
) are output places as shownin Fig. 1b. It is worth noting that the addition of these counter places will not inﬂuence the veriﬁcationof certain properties of PN model, including the boundedness. Indeed, these places, whose capacity isassumed to be inﬁnite, serve only to indicate the number of ﬁring of the upstream transitions at a given time.Finally, these counter places do not participate in any way to change the dynamic of PN model. Using thesecounter places, the behavior of the modeled pattern is represented by the system (2). This gives an explicitexpression of di
ﬀ
erent ﬁring dates of the transition
y
.
(a) without counter places
(b) with counter places
Fig. 1: Multi-merge patternIn a general way, the analytical behavior of the PN model of Fig. 1a with
n
incoming branches can bewritten in the following matrix form, knowing that
k
i
≤
k
,
∀
i
:
y
(
k
)
=
A
k
1
⊗
x
1
(
k
−
k
1
)
⊕
A
k
2
⊗
x
2
(
k
−
k
2
)
⊕
...
⊕
A
k
n
⊗
x
n
(
k
−
k
n
)
=
ni
=
1
A
k
i
⊗
X
(
k
−
k
i
) (2)Where
k
i
=
n j
=
1
,
j
i
m
P
j
for all
i
, 1
≤
i
≤
n
, where
m
P
j
is the marking of the place
P
j
, and
A
k
i
∈
R
1
×
nmax
, the
i
th
component of
A
k
i
equals to
τ
, and other components equal to
, and the
i
th
(for
i
=
1
..
n
) component of thevector
X
(
k
−
k
i
) is
x
i
(
k
−
k
i
).
731
W. Ait-Cheik-Bihi et al. / Procedia Computer Science 10 ( 2012 ) 728 – 735
3.2. Conditional choice pattern
The conditional choice pattern is represented by a conﬂict PN model without free choice as illustratedin the Fig. 2. In this model, if the place
P
2
contains only one token, then only one of two transitions
x
3
or
x
4
can be ﬁred. The conﬂict resolution is therefore made by choosing the transition to be ﬁred. Froma structural point of view, the transitions are validated and ﬁred based on the availability of tokens in theirupstream places. Indeed, for transitions
x
3
and
x
4
, where
x
3
∈
P
1
◦
P
2
◦
and
x
4
∈
P
2
◦
(where
P
◦
is theset of downstream transitions of the place
P
), the ﬁring rules are given as follows: f both places
P
1
and
P
2
contain a token, and the sojourn time
τ
1
and
τ
2
are expired, then the priority is given to
x
3
than
x
4
; If theplace
P
1
does not contain any token, while
P
2
contains one token and the sojourn time of
τ
2
is achieved,then
x
4
will be ﬁred but not
x
3
; If the place
P
1
contains one token and
P
2
does not contain any token, thenneither of these transitions will be validated. In this case, the ﬁring of
x
3
depends on the arrival of a tokeninto
P
2
. In order to describe the behavior of this pattern with (max,
+
) equations, we use the virtual ﬁring
Fig. 2: Conditional choice pattern(as detailed in [10]) of transitions in conﬂict situation. Indeed, for each ﬁring of
x
2
and after the completionof the time
τ
2
, one of the two transitions
x
3
or
x
4
will be really ﬁred, while the other one is assumed to bevirtually ﬁred. Furthermore, we deﬁne the two functions
Ψ
and
Ψ
by:
Ψ
a
≤
b
=
e if a
≤
b
otherwise
Ψ
a
≤
b
=
if a
≤
be otherwise
(3)We also deﬁne
m
P
(
x
i
(
k
)) as the marking of the place
P
at the time
x
i
(
k
). We assume that
∀
k
≤
0,
x
i
(
k
)
=
and the marking of a place at this time is zero. Di
ﬀ
erent ﬁring dates (including real and virtual ﬁring) of
x
3
and
x
4
according to those of
x
1
and
x
2
are given as follows:
∀
k
≥
1 :
x
3
(
k
)
=
[
τ
1
⊗
x
1
(
k
)
⊕
τ
2
⊗
x
2
(
k
)]
⊗
Ψ
τ
1
⊗
x
1
(
k
)
>τ
2
⊗
x
2
(
k
)
⊕
[
τ
1
⊗
x
1
(
k
−
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
))
⊕
τ
2
⊗
x
2
(
k
)]
⊗
Ψ
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
)
0
x
4
(
k
)
=
τ
2
⊗
x
2
(
k
)
⊗
[
Ψ
(
τ
1
⊗
x
1
(
k
)
>τ
2
⊗
x
2
(
k
))
∧
(
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
)
=
0)
](4)The operator ”
∧
” is deﬁned as ”and”,
a
∧
b
means that both conditions
a
and
b
must be satisﬁed simul-taneously. The terms expressing the ﬁring dates of
x
3
are given by:
•
[
τ
1
⊗
x
1
(
k
)
⊕
τ
2
⊗
x
2
(
k
)]
⊗
Ψ
τ
1
⊗
x
1
(
k
)
>τ
2
⊗
x
2
(
k
)
=
τ
2
⊗
x
2
(
k
)
, if
τ
1
⊗
x
1
(
k
)
≤
τ
2
⊗
x
2
(
k
) means that thereal ﬁring of
x
3
occurs when a token is present in
P
1
and another one arrives to
P
2
and their sojourntimes in these places are achieved. On the other side, if
τ
1
⊗
x
1
(
k
)
> τ
2
⊗
x
2
(
k
), the ﬁrst term of theequation becomes nil (
=
) by the impact of the function
Ψ
.
•
[
τ
1
⊗
x
1
(
k
−
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
))
⊕
τ
2
⊗
x
2
(
k
)]
⊗
Ψ
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
)
0
becomes zero when the marking of
P
1
at time (
τ
2
⊗
x
2
(
k
)
−
τ
1
) is zero. Otherwise, the ﬁring of
x
3
occurs by the token of
P
2
. In the term
τ
1
⊗
x
1
(
k
−
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
))
,
we introduce the tokens number
k
−
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
) to take intoaccount all tokens arrived in meantime to
P
2
until (
τ
2
⊗
x
2
(
k
)
−
τ
1
) and not only the last token arrivedbefore this time.The terms of the equation expressing the ﬁring dates of
x
4
, are given by:
•
x
4
(
k
)
=
τ
2
⊗
x
2
(
k
) if the both following conditions are satisﬁed: i)
τ
1
⊗
x
1
(
k
)
> τ
2
⊗
x
2
(
k
) which meansthat a token arrives to
P
2
and it its sojourn time is coming to the end before the arrival of anothertoken to
P
1
; ii)
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
)
=
0 which means that the marking of
P
1
at time (
τ
2
⊗
x
2
(
k
)
−
τ
1
)is zero. In this case, the ﬁring priority is given to
x
4
.
732
W. Ait-Cheik-Bihi et al. / Procedia Computer Science 10 ( 2012 ) 728 – 735
In the case where the transition
x
3
(resp.
x
4
) is really ﬁred for the
k
th
time,
x
4
(resp.
x
3
) is virtually ﬁredfor the
k
th
time. The matrix form of (4) is given by:
X
(
k
)
=
A
0
(
k
)
⊗
X
(
k
)
⊕
A
1
(
k
)
⊗
X
(
k
−
k
1
) (5)Where the matrices
A
0
(
k
) and
A
1
(
k
) are expressed as:
A
0
(
k
)
=
e
e
A
31
(
k
)
A
32
(
k
)
A
42
(
k
)
,
A
1
(
k
)
=
˜
A
31
(
k
)
(6)And :
A
31
(
k
)
=
τ
1
⊗
Ψ
τ
1
⊗
x
1
(
k
)
>τ
2
⊗
x
2
(
k
)
A
32
(
k
)
=
τ
2
⊗
[
Ψ
τ
1
⊗
x
1
(
k
)
>τ
2
⊗
x
2
(
k
)
⊕
Ψ
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
)
0
]
A
42
(
k
)
=
τ
2
⊗
Ψ
τ
1
⊗
x
1
(
k
)
>τ
2
⊗
x
2
(
k
)
∧
(
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
)
=
0)
˜
A
31
(
k
)
=
τ
1
⊗
Ψ
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
)
0
with k
1
=
m
P
1
(
τ
2
⊗
x
2
(
k
)
−
τ
1
)The system (5) is a non-stationary system whose matrices depend on the parameter
k
. This aspect of non-stationarity is due to the conﬂicts depicted in the associated PN model of the Fig.2.
4. Case study
In this section, a service composition scenario is proposed to illustrate the practical use of workﬂowpatterns and (max,
+
) algebra. In this scenario, several road-related services are composed and interact witheach other to minimize the emergency response time in the case of dangerous situations (e.g. accident, ﬁre).
4.1. Scenario description
The scenario used in our case study consists of four Web services that interact (see Fig. 3) to fulﬁllthe driver query when getting into an emergency situation. These services are described in the following.
Permanence WS
Dangeroussituation
AMBULANCE
n. cottin
AmbulanceWS
POLICE
POLICE
P O L I C E
n. cottin
PoliceWS TransportML BrokerWSItinerarycomputationItinerarycomputationHospitalWS
Accident
!
(1)ReportanincidentReach the incident location
R e a c h t h e i n c i d e n t l o c a t i o n
Permanence WS
AMBULANCE
n. cottin
Ambulance WS TransportML Broker WSHospital WS
Accident
!
(
3) Reach the hospital
R e a c h t h e i n c i d e n t l o c a t i o n
Itinerary computation
Fig. 3: The studied scenarioThe
Permanence
service is invoked by the user from its device [11] providing the incident location andthe incident type. The request is then submitted to other services such as Police service or hospital servicedepending on the nature of the incident (e.g. in case of accident Police, Ambulance, and Hospital servicesare invoked). The
Police
service receives from Permanence service the location of the incident and contactsthe nearest available police station to reach the incident location. This service use a cooperative plateforme

Related Search

Web service compositionSemantic Web Service CompositionPractice Based Approaches to the Study of KnoPerformance evaluation of UDP-based high-speeSociology of WorkTheology of workSociology of work and organizationsHistory of WorkTextual and Philological Study of Original BuStudy of Cultural Landscapes. Applied Archaeo

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks