In Appendix-A How the Proposed Methodology Works Is Illustrated with an Example

Appendix - A

In Appendix-A how the proposed methodology works is illustrated with an example.

To illustrate the working of Constraint Decomposition and Service Selection phases of the proposed approach, consider the combinational workflow given in the following Fig. A-1.

Fig. A-1 Sample workflow taken for illustrating the proposed methodology

Constraint Decomposition Phase

Conversion

The given workflow consists of one AND unit with three sequential paths, one OR unit with two sequential paths, one Loop consisting of single task with three iterations and one individual task.The example is illustrated with a QoS attribute, response time. The details of the workflow are given in Table A-1.

Table A-1 Details of tasks present in the workflow

Task ID / / / / / / / /
1 / 1 / 1 / 1 / 10 / 200 / 0
2 / 1 / 1 / 1 / 10 / 300 / 0
3 / 1 / 1 / 1 / 20 / 400 / 0
4 / 1 / 1 / 2 / 20 / 100 / 0
5 / 1 / 1 / 2 / 10 / 500 / 0
6 / 1 / 1 / 3 / 10 / 300 / 0
7 / 1 / 1 / 3 / 20 / 400 / 0
8 / 1 / 1 / 3 / 40 / 500 / 0
9 / 3 / 1 / 0 / 10 / 100 / 3
10 / 2 / 1 / 1 / 60 / 400 / 0
11 / 2 / 1 / 1 / 70 / 700 / 0
12 / 2 / 1 / 2 / 40 / 700 / 0
13 / 2 / 1 / 2 / 50 / 600 / 0
14 / 2 / 1 / 2 / 60 / 800 / 0
15 / 4 / 0 / 0 / 10 / 100 / 0

Conversion of AND unit

Let denote the AND pattern. Let , and denote the sequential paths present in . The values of minimum response time and maximum response time of each path of AND unit are computed using equations (5) and (6)

Now the minimum response time and maximum response time of , denoted by and are computed using equations (8) and (9) as

Now is replaced with a new task with minimum response time and maximum response time as 70 and 1200 respectively.

Conversion of Loop

Let Loop in Fig be denoted by . The Loop contains only one task, . The number of iterations that the Loop takes is 3 (i.e. ). The minimum response time and maximum response time of denoted by and are computed using equations (9) and (10) as

Conversion of OR unit

Let denote the OR pattern in Fig. The pattern contains two sequential paths, denoted by and. Let and denote the minimum response time and maximum response time of . Let and denote the minimum response time and maximum response time of .The values of , , and are computed using equations (5) and (6) as

Now the minimum response time and maximum response time of denoted by and are computed using equations (7) and (8) as

Now is replaced with a new task with minimum response time and maximum response time as 150 and 2100 respectively.

Conversion of given workflow in sequential workflow

The sequential workflow equivalent to the given workflow, denoted by is constructed using the new-tasks and sequential tasks present in the original workflow (in this example, ) as given in Fig. A-2.

Fig. A-2 Converted sequential workflow

Now the minimum response time and maximum response time of new-tasks and old-tasks are given in Table A-2.

Table A-2Minimum response time and maximum response time of old- tasks and new-tasks

task / Minimum response time / Maximum response time
/ 70 / 1200
/ 30 / 300
/ 150 / 2100
/ 10 / 100

For discussion, consider a typical value for global response time, . Let

Decomposability Check

The minimum response time of converted workflow, and maximum response time of , are computed using equations, (11) and (12) as

Now the given constraint satisfies the minimum response time of the converted workflow and hence the workflow is found as a feasible workflow. Next, the given constraint is decomposed to local constraints of the new-tasks and old-tasks present in the workflow.

Assignment of constraint to old task

Let denote the lower bound constraint of response time of old task, . The value of is computed using equation (13) as

Let denote the lower bound constraint of response time of old task, . The value of is computed using equation (16) as

The constraint values are rounded to floor value as

Assignment of constraints to new-tasks

Let, and denote the lower bound constraint of response time of , and respectively. Let, and denote the lower bound constraint of response time of , and respectively. The values of , , , , and are computed using equations (17) and (19)

Computation of constraints of AND, Loop and OR patterns corresponding to new-tasks

The AND pattern corresponding to is . Let denote the lower bound constraint of response time of . The value of , and are computed based on (20) and using (21)as

Similarly, the upper bound constraint of response time of AND pattern, Loop pattern, and OR pattern, denoted by,, and . The upper bound constraints are found out using (22) as

Now from the constraints of patterns, constraints of corresponding sequential paths and the tasks present in the sequential paths are computed.

Consider the AND pattern, . Let denote the lower bound constraint of response time of an ith task. The lower bound constraint of response time of tasks present in are computed using equations (21) as given below.

Let denote the upper bound constraint of response time of an ith task. The upper bound constraints of response time of individual tasks of are computed using equations (22) as given below.

Consider the Loop pattern . The Loop pattern contains only one task, . Let and denote the lower bound constraint of response time and upper bound constraint of response time of . The value of and are computed using equations (23) and (24) as

Consider the OR pattern, . The values of minimum response time and maximum response time of various tasks present in are computed using equations (21) and (22) as follows.

The above example shows how the method decomposes global constraints into local constraints.

Service Selection Phase

To explain how the best available service is selected for a particular task, two QoS attributes, say, response time and cost are considered. Let denote the value response time of ith service of jth service class. Let denote the value of cost ith service of jth service class. Let us consider user’s QoS preferences as: 0.6(or 60%) preference to response time and 0.4(or 40%) preference to cost.

From equation (25) the utility function of an ith service of jth service class is expressed as

In the above expression and denote the maximum response time and maximum cost of jth service class. Let and , denote the maximum response time and maximum cost of sequential equivalent of the given workflow. Let and , denote the minimum response time and minimum cost of sequential equivalent of the given workflow.

Let us consider some typical values for , , , , and . Let

Now is expressed as, . Now the service which produces the maximum value for is found out as the best service for jth service class. Let us assume that there are 4 services which satisfy the local constraints of response time and cost. The values of response time and cost of these 4 services are given in Table A-3. The utility values produced by these services are given in Table A-4.

Table A-3 Response time and cost of services which satisfy the constraints

Service / Response time / Cost
/ 70 / 120
/ 30 / 150
/ 50 / 100
/ 60 / 110

Table A-4Utility of services which satisfy the constraints

Service / Utility value
/ 0.17
/ 0.26
/ 0.25
/ 0.21

As the service, gives the maximum value for utility, is chosen the best available service.