Qos-Aware Web Services Composition Using Grasp with Path Relinking

QoS-aware Web Services Composition using GRASP with Path Relinking Jos´ e Antonio Parejoa, Sergio Seguraa, Pablo Fernandeza, Antonio Ruiz-Cort´ esa aDepartment of Computing Languages and Systems, University of Sevilla, Spain. Abstract In service oriented scenarios, applications are created by composing atomic services and exposing the resulting added value logic as a service. When several alternative service providers are available for composition, quality of service (QoS) properties such as execution time, cost, or availability are taken into account to make the choice, leading to the creation of QoS-aware composite web services. Finding the set of service providers that result in the best QoS is a NP- hard optimization problem. This paper presents QoS-Gasp, a metaheuristic algorithm for performing QoS-aware web service composition at runtime. QoS-Gasp is an hybrid approach that combines GRASP with Path Relinking. For the evaluation of our approach we compared it with related metaheuristic algorithms found in the literature. Experiments show that when results must be available in seconds, QoS-Gasp improves the results of previous proposals up to 40%. Beside this, QoS-Gasp found better solutions than any of the compared techniques in a 92% of the runs when results must be available in 100ms; i.e. it provides compositions with a better QoS, implying cost savings, increased availability and reduced execution times for the end-user. Keywords: QoS, Composite Web Service, SOA, GRASP, Path Relinking 1. Introduction1 Service Oriented Computing (SOC) is a software de-2 velopment paradigm based on assembling web services3 to implement dynamic business processes and agile ap-4 plications that spread across multiple organizations (Pa-5 pazoglou et al., 2007). The potential of SOC lies in6 three of the key benefits of web services: loose cou-7 pling between consumer and provider, composability of8 services, and dynamic binding. Loose coupling means9 that web services are consumed through a contract hid-10 ing implementation details to users. Composability11 means that web services can be composed to create12 more complex and valuable services, so-called Com-13 posite Web Services (CWS). Finally, dynamic binding14 provides flexibility to the applications by enabling the15 selection of the specific web services to be invoked at16 runtime.17 Web services may include information about the non18 functional properties that affect to their quality, so-19 called Quality of Service (QoS) attributes, e.g. cost,20 availability, etc. When several providers expose web21 services that are functionally equivalent through com-22 patible interfaces, QoS properties can be used to drive23 Email address: [email protected] (Jos´ e Antonio Parejo) the selection of the candidate service to invoke. For in- 1 stance, one may choose the most reliable and expensive 2 service, the cheapest one, or a third service that provides 3 a balance. 4 The QoS-aware binding of CWS enables the cre- 5 ation of context-aware and auto-configurable applica- 6 tions, that can adapt itself depending on available ser- 7 vices and user preferences (Ardagna and Pernici, 2007). 8 For instance, consumers could specify constraints like 9 “The total cost per invocation must be lower than 1$” 10 and QoS criteria such as “choose the faster providers”. 11 Given a CWS, a relevant problem is how to determine 12 the optimal binding; i.e. the set of service providers to 13 invoke that meet user constraints and optimizes the QoS 14 according to some QoS criteria. This problem, named 15 QoS-aware Service Composition (QoSWSC) (Strunk, 16 2010), is NP-hard (Bonatti and Festa, 2005; Ardagna 17 and Pernici, 2005), and has been identified as a main 18 research problem in the SOC field (Papazoglou et al., 19 2007). 20 The QoSWSC problem can be solved when the com- 21 position is created (i.e. at design time), just before start- 22 ing the execution of the composition (i.e. at invocation 23 time) or while the composite web service is running (i.e. 24 at runtime). When this problem is solved at run time 25 taking into account the current state of invocations, it 26 Preprint submitted to Expert Systems with Applications December 23, 2013 is named a rebinding (Zeng et al., 2004; Ardagna and1 Pernici, 2007). Solving rebinding problems is crucial in2 dynamic services markets where providers become un-3 available, new providers emerge and QoS levels change4 frequently (Canfora et al., 2008). In this scenarios, the5 time spent to solve the QoSWSC problem is a critical6 issue that influences the overall service response time7 and it should be kept as low as possible (Canfora et al.,8 2005b).9 Metaheuristic search techniques are algorithmic10 frameworks which use heuristics to find approximate11 solutions to hard problems at an affordable compu-12 tational cost. Typical metaheuristic techniques are13 Genetic Algorithms (GA), Hill Climbing (HC), Tabu14 Search (TS), Simulated Annealing (SA), GRASP and15 Path Relinking (PR) (Gendreau and Potvin, 2010). Sev-16 eral heuristic (Berbner et al., 2006) and metaheuristic17 techniques has been proposed in the literature to solve18 the QoSWSC problem, such as GA (Canfora et al.,19 2005b) and SA(Wang et al., 2007).20 This article proposes QoS-Gasp, a novel metaheuris-21 tic algorithm for solving the QoSWSC problem. This22 algorithm is a hybrid approach that combines GRASP23 and PR. QoS-Gasp is especially suitable for rebinding24 problems where short solving times are a must. In or-25 der to evaluate our algorithm we compared it with sev-26 eral metaheuristic algorithms proposed in the literature27 (GA (Canfora et al., 2005a) and hybrid TS with SA(Koa28 et al., 2008)) in rebinding scenarios. The comparison29 was made using several experiments with two different30 optimization criteria and 22 service compositions. The31 results show that QoS-Gasp find solutions with up to32 40% higher quality than those found by related algo-33 rithms in rebinding problems that must be solved in less34 than one minute. Moreover, QoS-Gasp found better so-35 lutions than any of the runs of the techniques compared36 in a 92% of the runs when results must be available in37 100ms. As a part of our evaluation we performed a rig-38 orous statistical analysis of the data that supports our39 conclusions.40 The remainder of this article is organized as follows:41 Section 2 presents a formal description of the QoSWSC42 problem and the metaheuristics used in our proposal43 (GRASP and PR). Section 3 describes QoS-Gasp in44 depth. The empirical evaluation of our approach is pre-45 sented in section 4, along with a brief description of46 the previous proposals used for comparison. Section 547 presents the threats to validity of our work. The related48 works are presented in section 6. Finally, Section 7 de-49 scribes our conclusions and future work. An extended50 version of the article is available as a technical report51 (Parejo et al., 2013).52 1.1. A motivating example 1 In order to illustrate the QoSWSC problem, a goods 2 ordering service inspired in the example provided in 3 (Zheng et al., 2012) is depicted in Fig. 1 using BPMN. 4 The diagram specifies a business process exposed as a 5 composite web service that uses 7 services with alterna- 6 tive providers (henceforth named tasks, t1,...,t7). Ta- 7 ble 1 shows the available service providers for each task 8 and their corresponding QoS attributes. As illustrated, 9 two candidate services are available for each task. 10 The composition starts when a client sends an order. 11 First the order is registered. Next if the payment type of 12 the order is “Credit Card”, the card is checked (t1) and 13 the payment (t2) is performed. As depicted in Table 1, 14 two banks providers are available, Aand B, and each of 15 them provide candidate services for the tasks t1and t2,16 denoted as s1,A,s2,A,s1,Band s2,B. Different providers 17 could be chosen in the binding of the CWS for each 18 task; e.g. Afor t1, and Bfor t2.19 Next the stock is checked (t3) and the products are 20 reserved for pick-up (t4). If any product in the order 21 is not in stock, the user is informed of the delay and the 22 CWS waits for some time until activities t3and t4are re- 23 peated (creating a loop). It is worth noting that the same 24 provider must be chosen for the tasks t3and t4, since 25 the reservation in t4refers to the stock of the specific 26 provider queried in t3. Once the order is ready for deliv- 27 ery two branches are performed in parallel. The pick-up 28 and delivery (t5) to the client is requested, and an e-mail 29 is sent to the client with an enclosed digitally signed in- 30 voice (t6). Once the activities on both branches are per- 31 formed, the completion of an user satisfaction survey 32 (t7) is requested. 33 Additionally, Fig. 1 shows a QoS constraint that must 34 be fulfilled. Specifically, the constraint specifies that 35 “The total execution time of the remainder activities af- 36 ter having the order ready for delivery must be lower 37 than 0.5 seconds”. 38 The QoSWSC problem can be stated as finding the 39 bindings that meet all the QoS constraints and maxi- 40 mize or minimize certain user-defined optimization cri- 41 teria, e.g. minimize cost. Note that this may become ex- 42 tremely complex as the number of candidate services in- 43 creases. In this example two providers are available for 44 each task, thus 128 (27) different bindings are possible. 45 This problem becomes especially convoluted in rebind- 46 ing scenarios where providers can become unavailable 47 and QoS levels may change unexpectedly. 48 2 Figure 1: Goods Ordering Composite Service Table 1: Service providers per Role and their corresponding QoS Guarantees Actor BANK PROVIDER DELIVERY DIG. SIGN. SURVEYING Provider A B C D E F G H I J Task t1t2t1t2t3t4t3t4t5t5t6t6t7t7 Candidate Service s1,As2,As1,Bs2,Bs3,Cs4,Cs3,Ds4,Ds5,Es5,Fs6,Gs6,Hs7,Is7,J Cost (in cents) 1 2 1.5 5 1 2 1 5 1 2 1 2 1.5 5 Execution Time 0.2 0.2 0.1 0.15 0.2 0.2 0.4 0.25 0.2 0.2 0.2 0.2 0.1 0.15 2. Preliminaries1 2.1. QoS-aware Binding of Composite Web Services2 The QoS-aware binding of a CWS is performed as3 follows: When the CWS is invoked or a rebinding is4 needed (Canfora et al., 2008), the set of tasks is identi-5 fied. For each task ti, the set of service providers avail-6 able Si=si,1,...,si,m(named candidate services) is7 determined by performing a search on a service registry.8 For each candidate service si,j, the QoS information is9 retrieved; e.g. according to Table 1 the cost of invoking10 the payment service of provider A is 0.02$. Given that11 some registry technologies do not support QoS infor-12 mation, a QoS-enriched registry or alternative QoS in-13 formation source (such as a Service Level Agreements14 Repository or a Service Trading Framework (Fernandez15 et al., 2006)) is needed. The set of QoS properties taken16 into account is denoted as Q.17 Taking into account this information the expected18 QoS provided by the application can be optimized. The19 goal of this optimization is to find the binding that max-20 imizes the utility of the global QoS provided according21 to the consumers’ preferences. Such preferences de-22 termine which binding is more valuable based on the23 global QoS levels (Qq) provided for each QoS property 1 q. For instance, a total execution time of 2seconds 2 could be fair for some users but too much for others. 3 User preferences are expressed as weights wqand util- 4 ity functions Uqfor each QoS property q. The weights 5 define the relative importance of each property. For in- 6 stance, wCost =0.2and wExTime =0.1means cost is 7 twice as important as execution time for the user. Utility 8 functions Uqdefine which values of the specific prop- 9 erty are more useful for the user. For instance, for avail- 10 ability the utility function would be linear, since the 11 higher the availability the better. 12 Thus, our goal translates in to finding the binding χ∗13 that maximizes the global user utility computed as: 14 GlobUtil(χ)=X q∈Q Uq(Qq(χ)) ∗wq(1) having Pq∈Qwq=1. Similar schemes for express- 15 ing user preferences and global utility functions have 16 been used extensively in the literature (Zeng et al., 17 2004; Ardagna and Pernici, 2007; Canfora et al., 2005b; 18 Strunk, 2010). 19 3 2.2. QoS Model1 2.2.1. QoS properties2 The set of quality properties Q={C,T,A,R,S}con-3 sidered in this article has been used extensively in re-4 lated work (Zeng et al., 2004; Ardagna and Pernici,5 2007; Canfora et al., 2005b). It comprises of:6 Cost (C). Fee that users must pay for invoking a service.7 Execution Time (T). Expected delay between service8 invocation and the instant when result is obtained.9 Availability (A). Probability of accessing the service10 per invocation, where its domain is [0,1].11 Reliability (R). It measures the trustworthiness of the12 service. It represents the ability to meet the quality13 guarantees for the rest of the properties. Its value is14 usually computed based on a ranking performed by end15 users. For example, in www.amazon.com, the range is16 [0,5] where 0means that QoS guarantees are systemat-17 ically violated, and 5means that guarantees are always18 respected. In this article we assume its domain is [0,1].19 Security (S). It represents the quality aspect of a ser-20 vice to provide mechanisms to assure confidentiality,21 authentication and non-repudiation of the parties in-22 volved. Consequently, this property usually implies the23 use of encryption algorithms with different strength, dif-24 ferent key sizes on underlying messages, and some kind25 of access control. In this article we use a categorization26 of the security, where the use of an encryption algorithm27 and key size in a service implies a numerical value as-28 sociated to this property for the service. Its domain is29 [0,1], where value 0means no security at all and value30 1means maximum security.31 QoS properties are usually classified as negative or positive. A quality property is positive if the higher the value, the higher the user utility. For instance, availability is a positive property, since the higher the availability the better. A quality property is negative if the higher the value, the lower the utility. For instance, cost is a negative property. We apply definitions of the utility functions widely used in the literature (Zeng et al., 2004; Ardagna and Pernici, 2007; Canfora et al., 2005b). For instance, for positive QoS properties the utility of the value xfor a QoS property qis defined as: Uq(x)=            1if qmax −qmin =0 x−qmin qmax−qmin if qis positive qmax−x qmax−qmin if qis negative (2) where qmax and qmin are the maximum and minimum32 values of the QoS property qfor all candidate services.33 2.2.2. Computing the Global QoS 1 Apart from the specific providers chosen for each 2 task, the global QoS values for the CWS depend on: 3 The workflow of the composition and the type of 4 QoS property. Global QoS is computed by recursively 5 applying a QoS aggregation function according to the 6 building blocks that define the structure of the compo- 7 sition. Table 2 summarizes the aggregation functions 8 applied for each QoS property qand type of building 9 block1. These functions are widely applied in literature 10 (Zeng et al., 2004; Ardagna and Pernici, 2007; Canfora 11 et al., 2005b; Wang et al., 2007; Strunk, 2010). For in- 12 stance, the total execution time of the parallel branches 13 is computed as the maximum execution time of any 14 branch, but the execution time of a sequence of tasks is 15 computed as the sum. In a very similar way, the aggre- 16 gation function depends on the specific QoS property to 17 be aggregated. For instance, given a specific workflow 18 such as the parallel branches of our motivating example 19 (tasks t6and t5), the total cost is computed as the sum of 20 the costs of the tasks in each branch, but the total avail- 21 ability is computed as the product of the availability of 22 the tasks in each branch. 23 The specific branches chosen for execution and the 24 number of iterations performed in loops. Since in 25 general the specific run-time behaviour of loops and 26 alternative branches is unknown in advance, an esti- 27 mate of this behaviour is needed to perform QoS-aware 28 binding (Canfora et al., 2008). For instance, given 29 that probability of using credit card is 0.8, and 2iter- 30 ations of stock reservation are performed, the estimated 31 global cost for the binding χ=(A,B,D,D,F,H,J)32 is: QCost(χ)=Cost of switch(χ)+Cost of Loop(χ)+33 Cost of fork(χ)+Cost7(χ)=0.8∗0.025+2∗0.06+0.09 =34 0.23$ 35 Since those values are estimations, the actual global 36 QoS values provided can differ significantly from the 37 estimations in some invocations. In the worst case 38 this deviation can lead to the violation of the global 39 QoS constraints. To avoid this problem, the re-binding 40 triggering approach proposed in (Canfora et al., 2008) 41 could be used. 42 2.3. Constraints of the QoSWSC problem 43 The QoSWSC problem has three types of constraints 44 (Zeng et al., 2004; Ardagna and Pernici, 2007): 45 Global QoS constraints. They affect the QoS of the 46 CWS as a whole; e.g. the total cost of the composition 47 must be lower than five ≡Qcost(χ)<5.48 1In this table kmeans the average number of iterations performed in loops and Pimeans the probability of executing branch i 4 Table 2: QoS Aggregation functions Sequence (S) Loop (L) Branch (B) Fork (F) Cost (C) Pm i=1C(ai)k·Pn i=1C(ai)Pm i=1Pi·C(sb i)Pp i=1C(sf i) Time (T) Pm i=1T(ai)k·Pn i=1T(ai)Pm i=1Pi·T(sb i)max nT(sf i)o Reliability (R) Qm i=1R(ai) (Qn i=1R(ai))kPm i=1Pi·R(sb i)Qp i=1R(sf i) Avaliability (A) Qm i=1A(ai) (Qn i=1A(ai))kPm i=1Pi·A(sb i)Qp i=1A(sf i) Security (S) min(S(ai))i∈{1...m}min(S(ai)) Pm i=1Pi·S(sb i) minp i=1S(sf i) Custom attribute (F) fS(F(ai))i∈1...mfL(sL,k)) fB(hFS(sb i)i,pi)fF(F(sf i))i∈1...p Figure 2: GRASP working scheme Local QoS Constraints. They affect the QoS values1 provided by the service chosen for a specific tasks; e.g.2 the cost of payment (t2) must be lower than 1.3 Service dependence constraints. A CWS may use sev-4 eral services that must be bound to the same provider.5 This situation creates a dependence, i.e. if the provider6 is selected for one of the tasks, then it must be selected7 for the rest of tasks it implements. In our motivating8 example there exists a dependence constraint between9 tasks t3and t4(stock management and reservation).10 2.4. GRASP11 The Greedy Randomized Adaptive Search Procedure12 (GRASP) (Resende, 2009) is an iterative optimization13 algorithm. GRASP has been successfully applied in a14 plethora of real life applications and research problems15 (Festa et al., 2002). Its working scheme is shown in Fig.16 2. Each GRASP iteration consists of two main steps:17 (i) building a solution and (ii) improving such solution18 using a local search algorithm.19 In the building phase, GRASP begins by creating an20 empty solution. Elements are added iteratively to it un-21 til a complete and feasible solution is found. For in-22 stance, in case of the QoS-aware web service compo-23 sition problem, the empty solution contains no bindings24 to any candidate services; i.e. in our motivating example25 the empty solution would be (?,?,?,?,?,?,?), meaning26 that no tasks are bound to an specific candidate service.27 The elements added are specific bindings to candidate28 services for each task, for instance, for task t1two can- 1 didate services are available, leading to partial solutions 2 (A,?,?,?,?,?,?) and (B,?,?,?,?,?,?).3 In order to add an element to the partial solution the 4 algorithm performs three steps. First, the set of valid 5 elements that could be added to the partial solution is 6 determined. For instance, in our motivating example 7 the element Dis a candidate provider for task t4, but 8 given the partial solution (B,A,C,?,?,?,?),Dis not a 9 valid element, since a constraint states that tasks t3and 10 t4should have the same provider. Thus the single valid 11 element for task t4in that case is C.12 Next, a subset of promising candidates is chosen from 13 the set of valid elements. This subset is referred to as 14 the Restricted Candidate List (RCL). The selection of 15 the elements in the RCL should be greedy and adaptive. 16 By greedy we mean that criterion should promote the 17 inclusion of the most promising elements in the RCL.18 For instance, a greedy criterion in our problem would 19 be to include the best candidate services according to 20 any of the QoS properties, the cheapest, the faster, the 21 most secure, etc. In our example, for task t7service s7,I22 from provider Iis faster and cheaper than service s7,J23 form provider J, thus the RCL according to this criterion 24 would be {I}. On the contrary, for task t1service s1,A25 from provider Ais the cheapest but service s1,Bfrom 26 provider Bis the fastest, thus the RCL according to this 27 criterion would be {A,B}.28 By adaptive we mean that the selection criterion 29 should take into account the current partial solution. As 30 an example, a greedy and adaptive criterion in our prob- 31 lem would be the inclusion of the services whose QoS 32 values are better that the average value for the elements 33 in the current partial solution for any QoS property, and 34 all the possible elements if such element does not ex- 35 ist. In our motivating example, given the partial solu- 36 tion (A, , ?,?,?,?,?,?), the RCL for task t2would be {B},37 since the execution time of corresponding service s2,Bis 38 0.15, better than the average execution time in the com- 39 position (0.2). However, if the current partial solution is 40 5 Figure 3: Path Relinking working scheme (A, , ?,?,?,?,?,I), the RCL for task t2would be {A,B},1 since none of the valid candidates improves the average2 value for any of the QoS properties.3 At the end of the iteration a randomly chosen element4 of the RCL is added to the current solution.5 In the improvement phase, a local search algorithm6 is executed using as starting solution the result of the7 construction phase.8 2.5. Path Relinking9 Path Relinking (PR) is an metaheuristic optimization10 technique that generates new solutions by exploring tra-11 jectories connecting promising solutions. The basic hy-12 pothesis is that by exploring the region of the search13 space between promising solutions we will find more14 promising solutions. The working scheme of PR is15 shown in Fig. 3. PR manages a set of promising so-16 lutions named the “elite set”. In each iteration, un-17 til the meeting of a termination criterion, PR randomly18 chooses two solutions from the elite set, named the ini-19 tiating and guiding solution. Then, PR generates a se-20 quence of successive solutions from the initiating to the21 guiding solution (Laguna and Mart´ ı, 1999). Each step22 is generated by replacing elements of the initial solution23 with the corresponding elements of the guiding solu-24 tion. For instance in our motivating example, having the25 bindings (A,B,D,D,F,H,J)and (B,B,D,D,F,H,I)as26 initiating an guiding solutions respectively, the elements27 to be incorporated are Bas provider for task t1, and Ias28 provider for task t7. The order of element replacement29 is significant, since different orderings define different30 paths in the solution space. For instance, in our exam-31 ple we could choose to incorporate Bor Ifirst, leading32 to solutions (B,B,D,D,F,H,J)and (A,B,D,D,F,H,I)33 respectively.34 After reaching the guiding solution the elite set is op-35 tionally updated. For instance, the best solution found36 could be added, the initiating and/or guiding solutions37 could be removed, etc. The key parameters of PR are38 the number of paths explored Npaths between each pair39 of initiating and guiding solutions, and the number of 1 steps explored per path Nsteps.2 3. QoS-Gasp 3 In this section we present QoS-Gasp a novel pro- 4 posal for solving the QoSWSC problem. It stands for 5 “QoS-aware GRASP+PR algorithm for service-based 6 applications binding”. It is an hybrid algorithm, where 7 GRASP is used for initializing the elite set used in Path 8 Relinking. 9 Next we describe how GRASP and PR have been 10 adapted for solving the QoSWSC problem. 11 3.1. Solution encoding 12 In order to apply metaheuristic optimization algo- 13 rithms to solve or problem, a suitable encoding of solu- 14 tions is needed. An encoding is the mechanism used for 15 expressing the characteristics of solutions in a form that 16 facilitates its manipulation by the algorithm. In QoS- 17 Gasp a vector-based encoding structure is used. This 18 encoding has been used extensively in literature (Can- 19 fora et al., 2005a; Gao et al., 2007). Specifically, solu- 20 tions are encoded as a vector of integer values, with a 21 size equal to the number of tasks. Thus, value jat po- 22 sition iof this vector encodes the choice of service jas 23 provider for task i.24 For instance, in our motivating example, the vector 25 that encodes the binding (A,B,D,D,F,H,J)would be 26 [0|1|1|1|1|1|0|0]. The index of each provider is deter- 27 mined by order of appearance in table 1; e.g. for Banks 28 A≡0and B≡1. Note that the values in each position 29 of the vector would be either 0or 1, since we have only 30 two providers per task in our motivating example, the 31 encoding is not binary. 32 3.2. Constraints support 33 GRASP and PR do not directly support the optimiza- 34 tion of constrained optimization problems. In order to 35 overcome this drawback, a variant of Eq. 1 is used as 36 objective function. This variant takes into account the 37 penalization term defined in (Canfora et al., 2005b) us- 38 ing a weight wun f , and a function Dfthat measures the 39 distance of a binding χfrom a full constraint satisfac- 40 tion. Thus our final function to be maximized is: 41 Ob jFunc(χ)=GlobUtil(χ)−(wun f ∗Df(χ)) (3) having 0≤wun f ≤1.42 6 The distance to full constraint satisfaction Dfis defined as: Df(χ, C)=P c∈C Meet(c, χ) |C|(4) being Cthe set of global and interdependence constraints of the problem 2.Meet(c, χ)is a function that measures the distance to the fullfillment of a single constraint cby the binding χ Meet(c, χ)=                                0if cis met abs(Qq(χ)−Tq)if cis global (Dist. to threshold) and unmet #services missing #dependant services if cis an unmet dep. const. (5) In this function, we denote the threshold of each global1 constraint on QoS property qas Tq. For instance, given2 the global constraint “the total cost of the composition3 must be lower than five”≡Qcost(χ)<5, then Tcost =5.4 If the actual cost of execution the composition given a5 binding χis 5.6, the value of Meet(c, χ), would be 0.6.6 Conversely, if the actual cost of executing the composi-7 tion is 3.5, the value of Meet(c, χ)is 0, since the con-8 straint is met. In a very similar way, when a constraint9 defines a dependency between taks for instance t3and10 t4in our motivating example, if the provider chosen for11 each task is different, the value of Meet(c, χ)would be12 1/2=0.5, since we have 1missing service from the13 chosen provider, and the total number of dependent ser-14 vices in the constraint is 2.15 3.3. GRASP building phase16 In QoS-Gasp, GRASP elements represent a particu-17 lar choice of a candidate service for a given task. Con-18 sequently, the solution χis built by choosing a service19 for a task at each iteration of the loop until the solution20 is a complete binding. The partial solution at iteration k21 is denoted as χk. The specific task to bind at iteration k22 is randomly chosen.23 The set of valid elements for the task tiis determined24 by the service dependence constraints. For instance, in25 our motivating example there exists a dependence con-26 straint between t3(stock querying) and t4(reservation27 2Local constraints are not taken into account, since they can be met by preprocessing the set of candidate services (Ardagna and Pernici, 2007). for pickup). Thus, if a provider has been chosen for 1 task t3in our partial solution χk, then the same provider 2 should be chosen for t4. If conflicting dependency con- 3 straints are found the construction phase restarts, since 4 it is not possible to create a feasible solution from χk−1.5 QoS-Gasp uses a RCL selection scheme that has been 6 applied extensively in the literature of GRASP. Specif- 7 ically, this selection is driven by an evaluation func- 8 tion g-that must be defined for the specific optimiza- 9 tion problem to solve- and a greediness parameter α10 (between 0and 1). Function gprovides a value in R11 for each candidate service, where gmin is the minimum 12 and gmax is the maximum of those values. A service 13 si,jwill be in the RCL if g(si,j)is greater or equal than 14 gmin +α·(gmax −gmin);i.e. αdefines the proportion of 15 the range [gmin,gmax]in which candidates are discarded 16 from RCL. Thus, for α=0all the candidates are in 17 the RCL (none is discarded), and the construction phase 18 becomes random. If α=1only the candidates with a 19 value in gof gmax would be in the RCL.20 The function gand value of αare crucial for the performance of GRASP. We defined up to seven novel greedy functions for the QoSWSC problem. Since the optimal values of those parameters depends on the problem to be solved, we performed a preliminary experiment testing each of function gwith several values of α. All the details about the gfunctions and their evaluation are reported in (Parejo et al., 2013) due to space limitations. The best average results were obtained α=0.25, and the best performing greedy functions were G1,G2 and G6showed below: G1(si,j, χk)=X q∈Q wq·Uq(qi,j)(6) G1is “miopic” and unadaptive, meaning that it only 21 considers the QoS value of each service, ignoring the 22 current solution under construction χk, but its evalua- 23 tion is extremely fast. 24 G2(si,j, χk)=Df(χk)−Df(χk∪si,j)(7) G2uses the difference of distance to constraint satisfication of the current partial solution χkand the new partial solution, denoted as χk∪si,j, but it ignores the QoS weights G6(si,j, χk)=Ob jFunc(χk∪si,j)−GlobUtil(χk)(8) G6is based directly on the gradient of the global QoS, 25 but ignoring the distance to constraint satisfaction of the 26 current solution. This subtle variant penalizes the selec- 27 tion of elements that generate constraint violations. 28 7 In order to evaluate Df,GlobUtil, and Ob jFunc, a1 random solution is generated at the beginning of the2 construction phase, and their elements are used to com-3 plete the choices for unassigned tasks in χk.4 3.4. GRASP improvement phase5 The GRASP improvement phase in QoS-Gasp is a lo-6 cal search procedure based on a neighbourhood defini-7 tion. The neighbourhood of a binding χcomprises of all8 possible bindings that have exactly n−1assignments in9 common with χ; i.e. have the same candidate services10 selected for each task except for one. QoS-Gasp uses11 Hill Climbing, where only a percentage of the neigh-12 bourhood is explored.13 3.5. Path Relinking14 QoS-Gasp uses the adaptation of GRASP described15 above to initialize the elite set used by PR. The length16 of the path between initiating and guiding solutions in17 QoS-Gasp is determined by the number of different ser-18 vice candidates. Each step of any relinking path, incor-19 porates one service candidate from the guiding solution.20 It is worth noting that the order in which service candi-21 dates are incorporated defines different paths. Conse-22 quently, for each pair of initiating and guiding solutions23 a high number of different paths could be explored. In24 order to reduce the computational cost of such explo-25 ration, QoS-Gasp restricts the number of paths gener-26 ated between each pair of solutions to Npaths. It intro-27 duces the service candidates from the guiding solution28 in a random order, and it limits the number of neigh-29 bours explored in each path to Nsteps. These parameters30 control the balance between the diversification of the ar-31 eas of the search space explored and the exhaustiveness32 of the search in those areas, which is crucial in rebind-33 ing scenarios where execution time is scarce.34 4. Experimentation35 The aim of the experimentation is to compare the36 performance of QoS-Gasp with previous metaheuris-37 tic proposals described in the literature for solving the38 QoSWSC Problem.39 4.1. Previous Proposals40 4.1.1. Genetic Algorithms41 The proposal described in (Canfora et al., 2005a) has42 been implemented for comparison since it is the most43 cited GA-based approach for this problem. In particular,44 the initial population is randomly generated. A standard45 one-point crossover operator (Dreo et al., 2003) is used.46 The mutation operator modifies the candidate to a sin- 1 gle task, both randomly chosen. Parameter values are 2 chosen according to (Canfora et al., 2005a) (as shown 3 in table 3). 4 4.1.2. Hybrid TS with SA 5 A hybrid of TS with Simulated Annealing (SA) was 6 proposed in (Koa et al., 2008) for solving the QoSWSC 7 problem. This proposal was aimed at finding feasible 8 solutions of constrained instances; thus, the search was 9 driven by the constraint meeting distance and the execu- 10 tion terminates when a feasible solution is found. In or- 11 der to enable the comparison with our proposals, and to 12 continue optimizing according to user preferences (even 13 when all constraints are met), a modification has been 14 carried out. When all the constraints are met, the dif- 15 ference between the QoS value of current solution Qq16 and the average QoS for this property Avgqis used for 17 guiding the search. Specifically, the QoS property se- 18 lected to guide the improvement in the algorithm is the 19 one minimizing s∗(Qq(χ)−Avgq)∗wq, where sis 1 20 if qis positive and −1if it is negative; i.e. our modi- 21 fication tries to generate neighbors improving the solu- 22 tion in the QoS property with the bigger improvement 23 room and importance for users. The pseudo-code of 24 the resulting algorithm, and a detailed explanation of its 25 working scheme is available in the additional material 26 (Parejo et al., 2013). 27 4.2. Experimental Setting 28 In order to evaluate our proposal QoS-Gasp was im- 29 plemented using FOM (Parejo et al., 2003). FOM is 30 an object oriented framework written in JAVA that re- 31 duces the implementation burden of optimization algo- 32 rithms. It also provides some experimentation capabili- 33 ties (Parejo et al., 2012). Experiments were performed 34 on a computer equipped with an Intel Core I7 Q870 35 CPU with 8 cores working at 1.87 Ghz, running Win- 36 dows 7 Professional 64bits and Java 1.6.0.22 on 8 GB 37 of memory. 38 4.3. Experiment #1 39 The aim of this experiment is to compare the perfor- 40 mance of our proposal and previous ones in terms of the 41 QoS of solutions they provide. Previous proposals (as 42 described in sec. 4.1) are compared to ours by solving a 43 number of instances of the QoSWSC problem. Specif- 44 ically, we compare Genetic Algorithms (GAs) and Hy- 45 brid Tabu Search with Simulated Annealing (TS/SA), 46 with a GRASP using G1(GRASP(G1)), and two vari- 47 ants of GRASP with Path Relinking (GRASP+PR) that 48 8 use G2and G6. The parameters used for each tech-1 nique are described in table 3. These values were2 chosen based on the experiments reported in literature3 for previous proposals and on another preliminary ex-4 periment performed for GRASP and GRASP+PR (de-5 scribed in detail in (Parejo et al., 2013)). Positive scal-6 ing utility function were used for Availability, Relia-7 bility and Security (we denote this set of properties as8 Q+={A,R,S}), cf. section 2.2. Negative scaling util-9 ity functions were used for the remaining properties10 (Q−={C,T}). The weights used for each QoS prop-11 erty were: wun f =0.5,wC=0.3,wT=0.3,wA=0.1,12 wS=0.2,wR=0.1. Since FOM solves minimization13 problems, an objective function that subtracts the value14 of ObjFunc (as described in equation 3) to 1.0 was used.15 Table 3: Parameters of the techniques used in the experiment Technique Paramenter Value GRASP α0.25 (G1) Greedy Function G1 LocalSearch HC (20% neig. exploration) GRASP+PR α0.25 (G6/G2) Greedy Function G6 / G2 LocalSearch HC (20% neig. exploration) # Elite Solutions 5 NPaths 2 Nsteps 50 Intial GRASP Iter. 50 Canfora’s Population Size 100 GA (Canfora et al., 2005b) Crossover 0.70 Mutation Prob. 0.01 Survival Policy The two better individuals Selector Roulette Wheel Initial Population Randomly generated Hybrid Initial Solution Local optimization (Koa et al., 2008) TS+SA Services exchanged 2 (Koa et al., 2008) Tabu Memory Recency based memory Tabu Mem. size 100 movements Accept. Criterion Based on current iteration 4.3.1. Experiment design16 Since our aim is to compare the performance of tech-17 niques, the dependent variable of this experiment was18 the evaluation of 1−Ob jFunc for the best solutions 1 found in each runt. The independent variable of exp. #1 2 was the tehnique used for optimization. The termina- 3 tion criteria was maximum execution time. Specifically, 4 the experiments were replicated using 100ms, 200ms, 5 500ms, 1000ms, 10000ms and 50000ms as maximum 6 execution times. These values cover most of rebinding 7 and binding scenarios at invocation time. 8 Eleven problem instances were generated by the algo- 9 rithm described in appendix C of (Parejo et al., 2013), 10 using the parameters shown in table 4. Those parame- 11 ters are common in the literature on the QoSWSC prob- 12 lem (cf. table 9 of (Parejo et al., 2013)). The specific 13 characteristics of each problem instance generated are 14 shown in table 5 . 15 Table 4: Problem instances generation parameters Composition Activities Uniform distribution between 10 and 100 Structure % control flow Uniform distribution between 20% and 50% Parameters % Loops 45% % Branches 45% % Flows 10% Max nesting Uniform ∈[5,10] Runtime Iter. per Loop Gaussian(µ=18, σ=6) inf. params Prob. of Branches Random Candidate Candidates per Task Uniform ∈[1,10] Services Cost Uniform ∈[0.2,0.95] Parameters Exec. Time Gaussian(µ=0.5, σ=0.4) Reliability Uniform ∈[0.3,0.9] Availability Uniform ∈[0.9,0.99] Security Uniform ∈[0.6,0.99] Constraints Number of Const. Uniform ∈[0,|Q|] Parameters % of optimality Uniform ∈[25,75] Objective Function Parameters wun f =0.5,wCost =0.3,wExecTime =0.3, wAvail =0.1,wS ec =0.2,wRel =0.1 For each combination of technique, problem instance 16 and maximum execution time, thirty runs were per- 17 formed in order to ensure the significance of results 18 4.3.2. Results 19 Table 6 shows the mean results per problem instance 20 and execution time. Specifically, table 6 is divided into 21 four sub-tables by execution time. In each sub-table, 22 rows depict the results obtained for each problem in- 23 stance, and columns depict the results obtained by each 24 optimization technique. The best means per problem 25 9 Transactions on 6, 560–572. doi:10.1109/TSC.2012.26.1 Jaeger, M.C., M¨ uhl, G., Golze, S., 2005. Qos-aware composition of2 web services: An evaluation of selection algorithms, in: On the3 Move to Meaningful Internet Systems. Springer. LNCS, pp. 646–4 661.5 Klein, A., Fuyuki, I., Honiden, S., 2013. Sanga: A self-adaptive6 network-aware approach to service composition. Services Com-7 puting, IEEE Transactions on PP, 1–1. doi:10.1109/TSC.8 2013.2.9 Klein, A., Ishikawa, F., Honiden, S., 2012. Towards network-10 aware service composition in the cloud, in: Proceedings11 of the 21st International Conference on World Wide Web,12 ACM, New York, NY, USA. pp. 959–968. URL: http:13 //doi.acm.org/10.1145/2187836.2187965, doi:10.14 1145/2187836.2187965.15 Koa, J.M., Kima, C.O., Kwonb, I.H., 2008. Quality-of-service ori-16 ented web service composition algorithm and planning architec-17 ture. Journal of Systems and Software 81, 2079–2090.18 Laguna, M., Mart´ ı, R., 1999. Grasp and path relinking for 2-layer19 straight line crossing minimization. INFORMS Journal on Com-20 puting 11, 44–52.21 Leitner, P., Hummer, W., Dustdar, S., 2011. Cost-based opti-22 mization of service compositions. IEEE Tran. on Serv. Comp.23 99. doi:http://doi.ieeecomputersociety.org/10.24 1109/TSC.2011.53.25 Leitner, P., Hummer, W., Dustdar, S., 2013. Cost-based optimization26 of service compositions. Services Computing, IEEE Transactions27 on 6, 239–251. doi:10.1109/TSC.2011.53.28 Liu, M., Wang, M., Shen, W., Luo, N., Yan, J., 2012. A quality of29 service (qos)-aware execution plan selection approach for a service30 composition process. Future Gener. Comput. Syst. 28, 1080–1089.31 URL: http://dx.doi.org/10.1016/j.future.2011.32 08.017, doi:10.1016/j.future.2011.08.017.33 Ma, H., Bastani, F., Yen, I.L., Mei, H., 2013. Qos-driven service34 composition with reconfigurable services. Services Computing,35 IEEE Transactions on 6, 20–34. doi:10.1109/TSC.2011.21.36 Ma, S.P., Yeh, C.L., 2012. Service composition manage-37 ment using risk analysis and tracking, in: Liu, C., Ludwig,38 H., Toumani, F., Yu, Q. (Eds.), Service-Oriented Computing.39 Springer Berlin Heidelberg. volume 7636 of Lecture Notes in40 Computer Science, pp. 533–540. URL: http://dx.doi.41 org/10.1007/978-3-642-34321-6_37, doi:10.1007/42 978-3-642-34321-6_37.43 Oster, Z., Ali, S., Santhanam, G., Basu, S., Roop, P., 2012. A service44 composition framework based on goal-oriented requirements en-45 gineering, model checking, and qualitative preference analysis, in:46 Liu, C., Ludwig, H., Toumani, F., Yu, Q. (Eds.), Service-Oriented47 Computing. Springer Berlin Heidelberg. volume 7636 of Lecture48 Notes in Computer Science, pp. 283–297. URL: http://dx.49 doi.org/10.1007/978-3-642-34321-6_19, doi:10.50 1007/978-3-642-34321-6_19.51 Paik, I., Chen, W., Huhns, M., 2012. A scalable architecture for au-52 tomatic service composition. Services Computing, IEEE Transac-53 tions on PP, 1–1. doi:10.1109/TSC.2012.33.54 Papazoglou, M.P., Traverso, P., Dustdar, S., Leymann, F., 2007.55 Service-oriented computing state of the art and research chal-56 lenges. IEEE Computer 40, 38–45.57 Parejo, J.A., Fern´ andez, P., Ruiz-Cort´ es, A., 2013. On parameter se-58 lection and problem instances generation for QoS-aware binding59 using GRASP and Path-Relinking. Research Report 2011-4. ET-60 SII. Av. Reina Mercedes s/n. 41012. Sevilla. Spain.61 Parejo, J.A., Racero, J., Guerrero, F., Kwok, T., Smith, K., 2003.62 Fom: A framework for metaheuristic optimization, in: ICCS’03,63 pp. 886–895.64 Parejo, J.A., Ruiz-Cort´ es, A., Lozano, S., Fernandez, P., 2012. Meta-65 heuristic optimization frameworks: a survey and benchmarking. 1 Soft Computing 16, 527–561. 2 Penta, M.D., Troiano, L., 2005. Using fuzzy logic to relax constraints 3 in ga-based service composition, in: GECCO. 4 do Prado, P.F., Nakamura, L.H.V., Estrella, J.C., Santana, M.J., San- 5 tana, R.H.C., 2013. A performance evaluation study for qos-aware 6 web services composition using heuristic algorithms, in: ICDS 7 2013, The Seventh International Conference on Digital Society, 8 pp. 53–58. 9 Qi, L., Ni, J., Ma, C., Luo, Y., 2013. A decomposition-based method 10 for qos-aware web service composition with large-scale composi- 11 tion structure, in: SERVICE COMPUTATION 2013, Proceeding 12 of the Fifth International Conferences on Advanced Service Com- 13 puting, pp. 81–86. 14 Qu, Y., Lin, C., Wang, Y., Shan, Z., 2006. Qos-aware composite 15 service selection in grids. GCC 2006 , 458–465doi:10.1109/ 16 GCC.2006.77.17 Ramacher, R., M¨ onch, L., 2012. Dynamic service selection with 18 end-to-end constrained uncertain qos attributes, in: Liu, C., Lud- 19 wig, H., Toumani, F., Yu, Q. (Eds.), Service-Oriented Comput- 20 ing. Springer Berlin Heidelberg. volume 7636 of Lecture Notes 21 in Computer Science, pp. 237–251. URL: http://dx.doi. 22 org/10.1007/978-3-642-34321-6_16, doi:10.1007/ 23 978-3-642-34321-6_16.24 Resende, M.G.C., 2009. Greedy randomized adaptive search proce- 25 dures, in: Encyclopedia of Optimization, pp. 1460–1469. 26 Sandionigi, C., Ardagna, D., Cugola, G., Ghezzi, C., 2013. Optimiz- 27 ing service selection and allocation in situational computing appli- 28 cations. Services Computing, IEEE Transactions on 6, 414–428. 29 doi:10.1109/TSC.2012.18.30 Strunk, A., 2010. Qos-aware service composition: A survey, in: Web 31 Services (ECOWS), 2010 IEEE 8th European Conference on, pp. 32 67 –74. 33 Su, S., Zhang, C., Chen, J., 2007. An improved genetic algorithm for 34 web services selection, in: Distributed Applications and Interoper- 35 able Systems. Springer. volume 4531 of LNCS, pp. 284–295. 36 Wada, H., Suzuki, J., Yamano, Y., Oba, K., 2012. E3: A mul- 37 tiobjective optimization framework for sla-aware service compo- 38 sition. Services Computing, IEEE Transactions on 5, 358–372. 39 doi:10.1109/TSC.2011.6.40 Wagner, F., Kloepper, B., Ishikawa, F., Honiden, S., 2012. To- 41 wards robust service compositions in the context of functionally 42 diverse services, in: Proceedings of the 21st International Confer- 43 ence on World Wide Web, ACM, New York, NY, USA. pp. 969– 44 978. URL: http://doi.acm.org/10.1145/2187836. 45 2187966, doi:10.1145/2187836.2187966.46 Wang, H., Tong, P., Thompson, P., Li, Y., 2007. Qos-based web ser- 47 vices selection. icebe 0, 631–637. 48 Wang, P., 2009. Qos-aware web services selection with intuitionistic 49 fuzzy set under consumer’s vague perception. Expert Systems with 50 Applications 36, 4460 – 4466. 51 Yu, Y., Ma, H., Zhang, M., 2013. An adaptive genetic programming 52 approach to qos-aware web services composition, in: Evolution- 53 ary Computation (CEC), 2013 IEEE Congress on, pp. 1740–1747. 54 doi:10.1109/CEC.2013.6557771.55 Zeng, L., Benatallah, B., Ngu, A., Dumas, M., Kalagnam, J., Chang, 56 H., 2004. Qos-aware middleware for web services composition. 57 IEEE Tran. Sof. Eng 30, 311–327. 58 Zhang, C., Su, S., Chen, J., 2006. Efficient population diversity han- 59 dling genetic algorithm for qos-aware web services selection, in: 60 Computational Science. Springer. volume 3994 of LNCS, pp. 104– 61 111. 62 Zhang, C., Su, S., Chen, J., 2007. Diga: Population diversity handling 63 genetic algorithm for qos-aware web services selection. Comput. 64 Commun. 30, 1082–1090. 65 16 Zhao, X., Wen, Z., Li, X., 2013. Qos-aware web ser-1 vice selection with negative selection algorithm. Knowl-2 edge and Information Systems , 1–25URL: http:3 //dx.doi.org/10.1007/s10115-013-0642-x,4 doi:10.1007/s10115-013-0642-x.5 Zheng, H., Zhao, W., Yang, J., Bouguettaya, A., 2012. Qos analysis6 for web service compositions with complex structures. Services7 Computing, IEEE Transactions on PP, 1. doi:10.1109/TSC.8 2012.7.9 Zou, G., Lu, Q., Chen, Y., Huang, R., Xu, Y., Xiang, Y., 2012. Qos-10 aware dynamic composition of web services using numerical tem-11 poral planning. Services Computing, IEEE Transactions on PP,12 1–1. doi:10.1109/TSC.2012.27.13 17