This paper deals with modeling and performance analysis of distributed applications, service compositions and workflow systems. From the functional perspective, the distributed application is modeled as an activity involving several roles, where behavior is defined in terms of compositions from several sub-activities using the standard sequencing operators found in UML Activity Diagrams. Each activity is characterized by a certain number of input and output events, and the performance of the activity is defined by the minimum delays that apply for a given output event in respect to each input event. We use a partial order to model these events, whose delays can be measured through testing. We also provide general formulas to calculate the performance of a composite activity from the performance of its constituent sub-activities and the control structure specifying the order of execution. Proofs of correctness for these formulas, along with a simple example are also given.
Many commercial systems rely on multiple communicating components for parts of their business processes. These are often structured as distributed systems, with components running on different processors or in different processes. For example, a multi-tiered system might start with requests from Web clients that invoke a process in a Web Application Server, which in turn makes calls to some “third party” servers – components involved in this system would be the client, Web-Application Server and the “third party” servers.
When developing such distributed reactive systems, there is a need to analyze performance of both from a global system perspective and a local or component-wise perspective. The global perspective specifies and analyzes the collaborative behavior of a distributed system in an abstract manner, while the local perspective identifies different system components along with their behaviour such that their interactions give rise to a behaviour satisfying the global perspective. Numerous methodologies have been employed for analyzing such systems, such as Queuing Models, Stochastic Petri Nets (SPN), Performance Evaluation and Review Technique (PERT) [4], and UML Profile: Modeling and Analysis of Real Time Embedded Systems (MARTE). Most of these notations, though, assume the basic activities in the decomposition to be allocated to a single system component. However, most of the applications have activities which are modeling collaborations between several system components, for instance an interaction between a client and a server.
Such distributed reactive systems are typically accompanied by performance specifications which are generally formalized by legal Service Level Agreements carrying financial penalties for non-compliance. Hence, it is becoming a commercial imperative to ensure that the participants in a workflow meet certain time criteria under all possible scenarios. McNeile in [6] modeled and analyzed end-to-end workflow delays but their analysis assumed that all the components are available at the beginning of the workflow, yielding a single workflow delay. This is not realistic as components become available at different time. This leads to relationships and delays between outputs and inputs of various components.
To this end, we introduced Partially Ordered Specification (POS) in [5], a modeling paradigm composed of UML Activity diagrams [7] and a partially ordered set of inputs and outputs. In this paper, we revise and extend the existing work done in [5] by considering performance characteristics of composite activities with independent inputs and outputs. We analyze and derive formulas for composite activities, composed of sub-activities with concurrency and alternatives.
We start off by reviewing modeling with partial orders. In Section 3, we review some of our previous work from [5] to describe POS and performance characteristics of basic operators. In Section 4, we propose formulas and provide proofs for calculating the performance of composite collaborations, composed with alternate and concurrency operators for independent input and output events. 2 2.1
In [5], we adapted the modeling methodology from [4] to model inputs and outputs of UML Activities (Collaborations) [7] as partially ordered events. We extend the previous work done in [5] by modeling events in sequence, alternatives and in a concurrent manner.
dependency on other events, and hence cannot occur until all the required events have occurred. Such is shown in Figure 1.0a, where event e4, is shown to be dependent on e1 and e3, while e2 is only dependent on e1.
modeling of alternative paths, inspired by the choice symbol in UCM [2], we introduce a new symbol in partial ordering to represent a choice in a behavior. As can be seen in Fig 1b, a UML “decisionNode” is modeled as a rectangular box with one incoming edge and multiple outgoing edges. The UML “mergeNode” is modeled as a similar rectangular box with multiple incoming edges and one outgoing edge.
single event e1 which leads to two events e2 and e3. Both events e2 and e3 must occur after e1, but they are incomparable between one another.
e1 e4 Sequential b) Alternative c) Concurrency Fig. 1. Modeling the Ordering of Events Using Various Operators e2 alternative
e3 merge
e1 e2 e3 e1 e2 a) e3 e4 2.2
Partially Ordered Specifications (POS) rely on UML Activity Diagrams (AD) to capture the dynamic behaviour of a system. This is comprised of actions and sequencing operators such as sequence, alternative, concurrency, and loops to define the relaFtioornsahgipivbeentwaecetinvitthye,sweeacctoionnssid.er input ienvpeuntt s i1 R1 Ri22 indirect and output events. Input (/output) events, dependency sehvoenwtns wahsicuhnmfilalrekd thceircbleegsininninFgi(g/en2d,inagre) ddierpeecntdency o1 o2 eovuetpnutst of the execution of actions by a specific Fig. 2. Partial Order Events role in a given activity. Note that a given activity has an input and an output event for each involved role.
These events form a partially ordered set, where a causal relationship may exist between some of these events, shown by arcs “”. The output events are not ordered relative to one another directly but each output event has a dependency on some corresponding input events.
Figure 2 illustrates an activity, with input events i1 and i2 and output events o1 and o2. As i1 and o1 are input and output events of the same role R1, o1 must occur after i1 due to local sequencing. Due to the relationship i1 i2 and i2 o2, there is an indirect dependency from i1 to o2, shown by the dashed arrow “-->.” Output events o1 and o2 are incomparable and may occur in any order. 2.3
We devised an approach to determine the dependencies amongst the input and output events within a given sub-activity in [5]. For a given sub-activity, according to this approach, one measures the delay between the time instance of the occurrence of input event i and a dependent output event o, provided all the other events on which o depends have occurred long time before. This delay is called Nominal Execution Time Delay (NETD), written as Δio.
This leads to the following formula which yields the performance of a collaboration D based on dependencies between input and dependent output events:
DTo = maxiεI(D) (DTi + DΔio) (
So far this paper provides a somewhat summarized version of modeling and performance analysis of composite activities given in [5]. The remainder of this paper is new material analyzing performance of activities composed of alternative and concurrent sub-activities with independent input and output events. 3.1
Formula (
Then the formula in (
We define control flow paths (cp) to depict a single execution of a given system. As an activity may have alternatives, interruptions and loops, this causes multiple control flow paths to exist. It is clear that different control flow paths, in general, lead to different execution time delays. For instance, the different branches of an alternative may result in different delays. In general, the number of different control flow paths is unlimited. For instance, the number of times a while loop executes may be unbounded, and/or the body of a loop or alternative may include other loops or alternatives, resulting in a recursive structure.
Therefore the Nominal Execution Time Delay (NETD) defined above depends on a particular control flow path that was followed during the execution of the collaboration. Throughout this paper, we only consider a single particular path, say cp. Then we write (cp)AΔio, for the Nominal Execution Time Delay between output event o and input event i for the control flow path cp of collaboration A.
We recognize the delays can be of a stochastic nature. However, for our work, we consider only fixed delays while considering a single control flow path. Shared Resources: We have assumed that the NETD will actually be attained during a control flow path, which may not be realistic if shared resources are involved in the processing of several inputs on which a single output depends. Hence we assume in the following that there are no shared resources and each role or all concurrent activities of a given role are implemented by an independent processor. 3.3
Events can be combined using various operators such as sequences, alternatives, concurrency, loops etc. We can define the basic performance characteristics involving partially ordered events.
three events in a sequence where the dependency e1 e2 e3 exists. If the delays
between these events are considered to be fixed delays, then it is quite clear that the
delay from e1 to e3 (Δe1e3) is the sum of the delays from e1 to e2 (Δe1e2) and e2 to e3
(Δe2e3): Δe1e3 = Δe1e2 + Δe2e3 (
e0 e1 e2 ...
en e1
... en e2 e0 a. SE SE b) SE ME
c) ME SE
Figure 3c shows a single event eo dependent on multiple events e1...en. Event e0 can
only occur when all of its dependencies are satisfied i.e. events e1...en, all, have
occurred. If we assume that all the events e1...en occur at the same time, then we can
calculate the delay for e0 to occur by taking the maximum of all the individual
NETDs: Δio = maxjε{e1,e2..en} (Δjo) (
alternative sequence, where the event e1...en occur with probability p1...pn,
respectively, each having a different control flow path. However, if we consider the control
flow path where a specific event em occurs, where emε{e1,..,en}, then the time delay
between event i and event em, is the measured/known NETD: Δim (
Notation: The set of roles involved in activity X is denoted by R(X). The set of input and output events in activity X are denoted by I(X) and O(X) respectively. We use activity D to abstract the sequence of sub-activities A and B. Hence, the set of roles involved in activity D consists of all the roles involved in sub-activities A and B, that is, R(D) = R(A) ∪ R(B). The set of roles common to both collaboration A and B is denoted by RC(D), where RC(D) = R(A) ∩ R(B). The non-common roles of A are the set of roles involved only in sub-activity A and not in sub-activity B, denoted by RNC(A) = R(A) – RC(A). A similar is used for output roles.
In [5], we proposed (and provided proofs for) definitions of Δio, for strong and weak sequencing operators for input and dependent output events. In the following, we extend this work by analyzing performance of sub-activity A and B using concurrency and alternative operators with independent input and output events. These compositions are abstracted by activity D. 4.1
Case Condition Fixed Delays
((21)) ((wwεεIICN(CD(A)a)nadndz εz OεCO((DA)))) or m(cpa)AxΔ((wcpz)AΔwz, (cp)BΔwz) ((89)) A B
(w ε I(A) and z ε ONC(A))
(
(w ε I(B) and z ε ONC(B))
(
(w ε INC(B) and z ε ONC(A))
Proof: We consider the proofs for all cases separately:
Case (
event w to output event z. There is no
other dependency which needs to be
satisfied for event z to occur. Hence, the NETD
for this case is NETD from w to z, AΔwz.
Similarly for a non-common output.
Case (
Case (
POS Equivalent
r’A rC r’C rB r’B AΔwx(t) iA oA oA’ iA’ A iB
iB’ B oB oB’
D BΔyz(t)
DΔwz(t) Fig 4b – POS of Concurrency
Figure 5 shows an alternative operator and its POS equivalent between two subactivities, A and B. We assume the choice, made by role c*, is done instantaneously and therefore does not directly add any delays. However, no action of the subactivities in the body of an alternative may start to execute until this choice is made. Hence, this causes a dependency between c* and all the other roles involved in the sub-activities of the alternative body, shown by the introduction of sub-activity Choice in Figure 5b. Note: this does not have any impact on NETD of sub-activities.
As discussed in section 3.3, there is a control flow path for each branch of an alternative, leading to different execution time delays.
NETD: The NETD for a composite activity D consisting of an alternate execution of
sub-activities A and B, (cp)DΔwz, is given by the following table:
CaseCondition Fixed Delays
(
(ep)BΔwz otherwise A B
(
–∞ if B is executed and w ≠ z
(
(w ε I(B) and z ε ONC(B)) (–ep∞)BΔwz iofthAeirsweixseecuted and w ≠ z CAolntetrronlaFtilvoew (8) (w ε INC(A) and z ε ONC(B) or –∞ if A or B is executed
(w ε INC(B) and z ε ONC(A))
Case 5: Either sub-activity A will execute or B will. From (
Case 6: If activity A executes then the delay is that of the execution in activity A. But if activity B executes, then when w = z, there is a dependency between the events due to local sequencing but there is no delay as there is no execution performed between these events. Hence the delay is 0. When w ≠ z, then there is no local sequencing dependency between the events and no delay. Hence, the delay is –∞. Case 7: This is similar to Case 6. rA r’A rC rC* r’C rB r’B Case 8: This is similar to Case 4. 5
Choice We analyzed performance of global collaborations composed from sub- iA iA’ collaborations with sequential, alter- AΔwx A DΔwz native and/or concurrent ordering, oA oA’ based on the delays of the constituent iB iB’ sub-activities. We believe that this B BΔyz approach to performance modeling of oB oB’ distributed systems is useful in many fields of application, including distributed work flow management systems, service composition for com- oC* munication services, e-commerce Figure 5b –POS of an Alternative applications, and Web Services. We have implemented a tool that takes as input an Activity Diagram including sub-activities with defined performance characteristics and provides as output the NETDs of the global collaboration.
In this paper, we have considered fixed delays. We plan on extending our work to consider different types of delays (stochastic and range of delays). We also plan to extend the here described work to include additional sequencing operators, such as strong and weak while loops [1] and interruptions.