of 8

Performance Study of Workflow Patterns-Based Web Service Composition

5 views
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 Workflow 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 Workflow 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. Workflowpatterns are widely used for Web service composition to allow the specification of composite services. In this paper, theperformance evaluation and analysis of workflow patterns is presented. We use both ( max , + ) algebra and Petri Nets asformal modeling tools to describe the behavior of workflow patterns and analyze their properties and performances. Areal case study is worked out to represent and study the performances of integrated workflow patterns.c   2011 Published by Elsevier Ltd. Keywords:  Web services composition, Workflow 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 definitionof new composed process that interacts with existing ones. A workflow pattern can be seen as the automaticmodeling and system management for all tasks and di ff  erent involved actors in a business process. In otherwords, a workflow pattern describes the tasks between the di ff  erent actors of a process, deadlines, validationmethods, and provides to each actor the information needed to fulfill its task. The use of workflow patternshas become a major asset providing a competitive advantage, as a way to reduce costs, automate processes,and reduce response times. Di ff  erent studies have sought to identify the basic needs for business processmodeling. The main result of these studies was the identification 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 workflow patterns, which are considered as modeling of a set of tasks performed by di ff  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 workflowpatterns. The developed models will be used to evaluate the performance of Web service composition basedon workflow 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 amongworkflow patterns. 2. Related work ApproachesdealingwithformalmodelingofWorkflowpatternsforservicecompositioncanbeclassifiedinto two di ff  erent categories,  language-oriented approaches  and  model-oriented approaches . The formerones focus on the verification 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 verification 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 Workflow patterns) and being comprehensive enough to generate executable codes. How-ever, it is hard for designers to deal with formal verification of service composition because neither BPMNnor UML are supported with suitable tools. Several approaches have been proposed to take this issue byproviding Workflow 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] defined fourteen of the twenty srcinal patterns and used them for the composition of Web services.They also defined new patterns by composing existing ones. The new defined patterns are mainly based onthe QoS as a selection criterion (e.g. cost and price ) in the composition of services. In [3], the authorsdefined an approach based on workflow patterns, specifically 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 workflow patterns. We will use P-Timed PNwherein fixed 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 Workflow 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 verifies  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 defined 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 controlflow, 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 fired, the output transition  y  is activated and can be fired afterthe temporization  τ . However, it is not obvious to formally express the firing number of the transition  y according to the firing 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 influence the verificationof certain properties of PN model, including the boundedness. Indeed, these places, whose capacity isassumed to be infinite, serve only to indicate the number of firing 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 ff  erent firing 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 conflict 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 fired. The conflict resolution is therefore made by choosing the transition to be fired. Froma structural point of view, the transitions are validated and fired 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 firing 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 fired 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 firing 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 firing         Fig. 2: Conditional choice pattern(as detailed in [10]) of transitions in conflict situation. Indeed, for each firing of   x 2  and after the completionof the time  τ 2 , one of the two transitions  x 3  or  x 4  will be really fired, while the other one is assumed to bevirtually fired. Furthermore, we define the two functions Ψ and Ψ by: Ψ a ≤ b  =   e if a  ≤  b    otherwise  Ψ a ≤ b  =      if a  ≤  be otherwise  (3)We also define  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 ff  erent firing dates (including real and virtual firing) 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 defined as ”and”,  a ∧ b  means that both conditions  a  and  b  must be satisfied simul-taneously. The terms expressing the firing 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 firing 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 first 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 firing 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 firing dates of   x 4 , are given by: •  x 4 ( k  )  =  τ 2 ⊗  x 2 ( k  ) if the both following conditions are satisfied: 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 firing 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 fired for the  k  th time,  x 4  (resp.  x 3 ) is virtually firedfor 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 conflicts 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 workflowpatterns 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, fire). 4.1. Scenario description The scenario used in our case study consists of four Web services that interact (see Fig. 3) to fulfillthe 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
Advertisements
Related Docs
View more...
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