Efficient Web Service Composition via Knapsack-Variant Algorithm
Shiliang Fan Yubin Yang
cs.SE










^1State Key Laboratory for Novel Software Technology, 

Nanjing University, Nanjing 210023, China





Efficient Web Service Composition via Knapsack-Variant Algorithm
    Shiliang Fan^1
Yubin Yang^1,*
    
================================================================





Since the birth of web service composition, minimizing the number of web services of the resulting composition while satisfying the user request has been a significant perspective of research. With the increase of the number of services released across the Internet, seeking efficient algorithms for this research is an urgent need. In this paper we present an efficient mechanism to solve the problem of web service composition. For the given request, a service dependency graph is firstly generated with the relevant services picked from an external repository. Then, each search step on the graph is transformed into a dynamic knapsack problem by mapping services to items whose volume and cost is changeable, after which a knapsack-variant algorithm is applied to solve each problem after transformation. Once the last search step is completed, the minimal composition that satisfies the request can be obtained. Experiments on eight public datasets proposed for the Web Service Challenge 2008 shows that the proposed mechanism outperforms the state-of-the-art ones by generating solutions containing the same or smaller number of services with much higher efficiency.










§ INTRODUCTION


Web services are platform-independent applications which are released, discovered and invoked over the web using open standards such as UDDI <cit.>, SOAP <cit.>, and WSDL <cit.>. As software modules published on servers and consumed across the Internet, web services transmit their communication data over the network expediently, which leads to the loosely-coupled nature. The nature of loose coupling pave the way for easier and wider-ranging integration and interoperability among systems, making the technology of web services extensively used in enterprises. It is as plain as a pikestaff that web services have been the support technology for the swift development of IT-based services economy.

However, the complex business requirements cannot be fulfilled by a single service in most cases. But meanwhile, with the sharp increase of the number of web services, the composition of web services provides a way to solve the problem. Web service composition is the process of building a more complex, functional workflow via combining a collection of single services together, to satisfy the inputs and outputs given by users. There are mainly two kinds of approaches for the web service composition problem. Some researches transform the composition problem into a planning one by mapping services to actions <cit.>, <cit.>, <cit.>, which is known as AI-based technique. Others construct a graph to express the relationship of services and aim to extract a reachable path from the graph <cit.>, <cit.>, which is called graph-based technique.

There exists a phenomenon that a growing number of services own similar or identical functionality. Therefore, it is simple to known that, for a given request, the composition process of massive services may generate many possible solutions with different number of services. Minimizing the number of services of the resulting composition while satisfying the user request is significant for brokers, customers, and providers <cit.>. Standing in the shoes of brokers, a composition result with fewer services could make it easier for the work of maintenance and management. From the customers' point of view, a smaller composition ordinarily means the less payment for those services invoked; On the other side, decreasing the number of services involved in the composition may highly increase the success rate of acquiring the wanted responses to the requests made by customers. As for service providers, solutions with fewer services could save resources and cost for the same task.

Up to now, there are several studies on the web service composition taking the optimization of the number of services into consideration. Nevertheless, in face of the repositories that contains a substantial amount of services, existing researches take too long time to obtain the optimal solution on account of the huge search space. Thus these approaches aren't efficient enough to be applied to large-scale and real-time environments. In this paper, we aim at presenting a mechanism to efficiently solve the web service composition problem. The main contribution are:


  ∙ An equivalent transformation approach that transforms search steps on the service dependency graph into dynamic knapsack problems by mapping services to items with changeable volume and cost.

  ∙ A knapsack-variant algorithm that guarantees to efficiently generate the composition with minimal number of services by means of solving each dynamic knapsack problem.

  ∙ An optimization strategy to reduce the spatial complexity of the knapsack-variant algorithm.

Furthermore, a full validation on eight datasets of Web Service Challenge 2008 has been done. Experimental results show that our mechanism performs better than the state-of-the-arts both in term of quality and efficiency.

The rest of this paper is organized as follows. Section 2 reviews some related work, Section 3 describes the background and formalizes the web service composition problem, then illustrates the motivation of this research. Section 4 introduces the proposed mechanism, Section 5 shows the experimental results, and Section 6 provides some final remarks.









§ RELATED WORK


Effectively combining minimal number of services distributed over the web to build enterprise-class services that satisfy given requirements is the goal of this paper. A survey of the problem of web service composition shows that several researches have been done in this perspective, and each has its own merits.

A heuristic A* search algorithm is proposed in <cit.> for the problem of automatic web service composition. For a given request, a digraph called service dependency graph is constructed firstly with a part of the original services chosen from an external repository. Meanwhile, some techniques are applied to reduce the useless nodes in the graph. Then the heuristic-based search algorithm named A* is executed over the optimized graph to seek the minimal composition which fulfills the user request. Though it can obtain compositions with minimal number of services on WSC-2008's datasets, it may show a poor performance in large-scale and  real-time environments. On one hand, different kinds of optimizations on the service dependency graph may spend large quantities of time. On the other hand, quite a few iterations of A* search algorithm aren't applicable to real-time scenarios.

A scalable and approximate mechanism is presented in <cit.> to get the near-minimal compositions against time. The authors proposed an on-the-fly strategy to construct only a path of the auxiliary graph instead of the complete graph. Additionally, a deterministic approach and a probabilistic approach are discussed to find the path with the minimal number of services, which is the final result of composition. Though the algorithm has a superior service composition time compared to other algorithms, the greedy strategy adopted always gets stuck in local optima. As a result, it always generates compositions with more services than the others. In a word, it performs well in efficiency but it remains to be improved in terms of the quality of solutions.

Pablo et al. <cit.> present a composition framework integrating fine-grained I/O service discovery strategy and an optimal composition search algorithm. To improve the efficiency of the generation of a layered service composition graph, the discovery and matchmaking phases are optimized using indexes and cache. Once the graph is generated, many optimizations are applied to reduce the graph size. Then a search which is modelled as a state-transition system is performed over the graph to find the minimal composition among all the possible compositions satisfying the request provided by user. Experimental results show the scalability and flexibility of the composition framework. However, similar with the mechanism in <cit.>, though lots of optimizations are used to improve the optimal composition search performance, much extra time is spent in the step. On the other side, the search algorithm isn't efficient enough to be applied to large-scale and real-time environments.

In summary, despite above algorithms to optimize number of services, there is a lack of approaches that have the ability to minimize the number of services of the composition effectively and efficiently. This paper proposes an effective and efficient mechanism in an effort to find compositions with minimal number of services in large-scale and real-time scenarios.









§ PRELIMINARIES AND MOTIVATION




 §.§ Preliminary Knowledge


Web service composition is a well studied problem, and semantic web services are the foundation of the problem. In this paper, a semantic web service is formally defined as follows <cit.>, <cit.>, <cit.>.


Given a set of concepts named Con, a Semantic Web Service ("service" for short) is defined as a tuple s = {In_s, Out_s}, where In_s = {in^1_s, …, in^n_s} is the set of inputs required to invoke the semantic web service s, and Out_s = {out^1_s, …, out^n_s} is the set of outputs generated by executing the service s. Each element of In_s and Out_s is actually a semantic concept belonging to the set Con, namely, In_s ⊆ Con and Out_s ⊆ Con.


Individual services can be combined by connecting their matched inputs and outputs to construct compositions <cit.>, <cit.>.


Given an output out_s ∈ Out_s of a service s, as well as an input in_s^' ∈ In_s^' of another service s^', if out_s and in_s^' are equivalent concepts or out_s is a sub-concept of in_s^', out_s matches in_s^' (i.e., in_s^' is matched by out_s).


There are mainly two kinds of structures of these compositions, namely sequential structure and parallel structure <cit.>. The services organized as a sequential structure are invoked in order, while the services organized as a parallel structure are invoked synchronously. A composition can be described as follows.


A Composition containing the set of services S = {s_1, …, s_n} is defined as Ω_S = s_1, …, s_n. If the services are chained in sequence, the composition is expressed as Ω_S^→ = s_1→…→s_n; if in parallel, then Ω_S^∥ = s_1∥…∥s_n. The set of services involved in Ω_S is defined as Servs(Ω_S) = S. Moreover, the length of a composition Ω_S is defined as Len(Ω_S) = | S |, namely the number of services in  Ω_S.


The aim of the service composition problem is to automatically select the minimal composition of available services to fulfil a user request that is defined as follows.


A Request from users is defined as a tuple R = {In_R, Out_R}, where In_R = {in^1_R, …, in^n_R} is the set of inputs provided by users (In_R ⊆ Con), and another element Out_R = {out^1_R, …, out^n_R} represents the set of expected outputs (Out_R ⊆ Con).


On the basis of the above concepts, the precise definition of the web service composition problem is given as follows.


A Web Service Composition Problem is defined as, for a given composition request R, to seek for a composition Ω_S fulfilling R with the optimization objective of min| S |, namely, the Ω_S contains the minimal number of services.





 §.§ A Motivating Example


Graph is a natural and intuitive way to express the complex interaction relations between entities. Service Dependency Graph is a digraph used to describe services and the matching relations among them <cit.>, <cit.>, <cit.>. For a given request R = {{in_1, in_2}, {out_1, out_2}}, an example of service dependency graph is shown in Fig.1. Each service is represented as a rectangle, while the inputs and outputs of a service are represented as circles. Furthermore, the matching relations among services are represented as edges connecting two circles.



As can be seen from Fig.1, the highlighted composition which can be represented as Ω = s_o→((A→D)∥(B→E))→G→J→s_k contains eight services in total (including the s_o and the s_k). There are also several other compositions satisfying the same user request R such as Ω^' = s_o→((A→C→I)∥(B→F→H→K))→s_k, whereas the number of services of them are unexceptionally more than eight. Therefore, the composition Ω highlighted in the graph is the optimal one with the minimal number of services.

In large-scale scenarios, the service dependency graph may be exceedingly complex, which leads to a huge search space <cit.>. As a consequence, it is formidable to extract the optimal composition from the graph. There is no doubt that the exhaustive combinatorial search can guarantee the optima, but it will take an unacceptable long time to generate the compositions and isn't applicable to real-time environments. To sum up, we should pay attention not only to the quality of the resulting composition but also to the efficiency of the composition algorithm.







§ DETAILED METHODOLOGY


In this section, an efficient mechanism is proposed for the problem of web service composition. Given a composition request R = {In_R, Out_R} and a service repository S_r, a service dependency graph is firstly constructed with the relevant services for the request. Then, search steps on the graph are transformed into dynamic knapsack problems, after which a knapsack-variant algorithm is proposed to solve each dynamic knapsack problem. Finally, an optimization strategy is adopted to reduce the spatial complexity of the knapsack-variant algorithm.



 §.§ Service Dependency Graph


As shown in Fig.1, a service dependency graph is a layered digraph. The first layer contains only one dummy service s_o = {∅, In_R}, similarly, there is only a dummy service s_k = {Out_R, ∅} in the last layer, while the concrete services in the other layers are selected from S_r. Moreover, each layer contains the services whose inputs are all matched by the outputs generated by previous layers.

The generation process of a service dependency graph is shown in Algorithm 1. Given the request R and the repository S_r, s_o is firstly added to the first layer L_0, after which each following layer L_i is constructed with the services whose inputs are all matched by the outputs generated by previous layers. s_k will be added to the last layer if the set of expected outputs Out_R is included in Out_all. Finally, unused services making no contribution to Out_R are removed from the graph by traversing from the last layer to the first layer.





 §.§ The Dynamic Knapsack Problem


Once the service dependency graph is completed, the composition problem is regarded as searching for a reachable path from s_o to s_k. Each search step on the graph is defined as determining the optimal precursors of each service.

The set of precursors of a service s ∈ L_i is defined as Pre(s) = {s^' |  s^'∈ L_j(∀ j<i)  In_s ∩ Out_s^'≠∅}. Specially, Pre(s_o) = ∅.


The search step of service G is shown in Fig.2. Note that, the minimal composition ending with a service s is expressed as Ω^s, and c_i in the figure represents an input or output concept of services. Assuming that the minimal compositions ending with the precursors of G, i.e., Ω^C, Ω^D, Ω^E, and Ω^F, have been determined in advance, the search step of G is defined as selecting the optimal subset of {Ω^C, Ω^D, Ω^E, Ω^F} to compose the Ω^G, which is actually a greedy strategy. On the basis of the greedy strategy, an equivalent transformation approach is proposed to transform each search step similar to the one shown in Fig.2 into a Dynamic Knapsack Problem.




As shown in Fig.3, assuming that the optimal precursors of a service s require to be determined, s is abstracted into a knapsack whose capacity is In_s (the set of inputs of the service s). Each precursors of s is spontaneously regarded as an item with dynamic volume and cost. The problem is to minimize the sum of the cost of the items in the knapsack so that the sum of the volume is equal to the knapsack's capacity. The volume of an item s^'∈ Pre(s) is relevant to Out_s^' (the set of outputs of the service s^'), and the cost of s^' is measured with Servs(Ω^s^') (the set of services involved in the composition Ω^s^'), which is too inconvenient to be applied to the following composition algorithm. Therefore, an approach is presented to quantify the volume and the cost of each item.






  §.§.§ The quantization of volume.


Firstly, all the subsets of In_s is obtained by Algorithm 2 in a certain order. Then, on the ground of the returned subsets Subs, a mapping table is constructed to quantify the volume of the knapsack and each item. Taking the problem in Fig.3 as an example, the mapping table used to support the volume quantization is shown as Table 1.



By means of Table 1, the volume of the knapsack and each item can be quantified as follows.


  ∘ The capacity of the knapsack s is quantified as the upper bound of index, namely | Subs | - 1.

  ∘ Assuming that the service s^' provides the set of outputs Out ⊆ Out_s^' for the service s, the volume of s^' is quantified as the value of the index which satisfies the condition that Subs[index] = Out.

Taking the problem in Fig.3 as an instance, the capacity of the knapsack G is V_cap = 15 after quantization. Two different feasible solutions of the dynamic knapsack problem are shown in Fig.4 respectively. As can be seen from the solution 1, the Service D provides the set of outputs {c_1, c_2} for the Service G, thus the volume of the item D is quantified as volume_D = 3 according to Table 1. In addition, volume_E = 4 owing to the fact that the Service E provides the set of outputs {c_3} for G. Similarly, volume_F = 8. It is not difficult to observe that volume_D + volume_E + volume_F = 3 + 4 + 8 = V_cap, hence the knapsack G can be filled with the set of items {D, E, F}, which indicates the effectiveness of the quantization.

The volume of an item is changeless in the 0-1 knapsack problem, while the volume of an item is changeable in the dynamic knapsack problem. For example, let's discuss the solution 2 shown in Fig.4(b). Despite the fact that the set of outputs of the Service D is {c_1, c_2}, D only provides {c_2} for G seeing that {c_1} is provided by the Service C, which leads to the change of volume_D from 3 to 2. Meanwhile, volume_C + volume_D + volume_E + volume_F = 1 + 2 + 4 + 8 = V_cap. The outputs provided by the service s^' for the service s are uncertain before decision-making, hence the volume of the item s^' can't be determined in advance.






  §.§.§ The quantization of cost.


Considering that the goal of this paper is minimizing the number of services involved in the resulting composition, the cost of an item s^' is designed as the minimal number of services that require to be invoked to generate the outputs of the service s^'. Therefore, the cost of each item is quantified as follows.


  ∘ Assuming that Ser represents the set of services which belong to Servs(Ω^s^') and haven't been invoked yet, the volume of the item s^' is quantified as the size of the Ser ∪{s^'}.

Taking the solution 1 shown in Fig.4(a) as an example, suppose that the set of items {D, E, F} are put into the knapsack G in order of the name (D→E→F). We have already assumed that the minimal compositions ending with the precursors of G have been determined in advance. Figure 2 reveals that Ω^D =s_o→A→D, Ω^E =s_o→B→E and Ω^F =s_o→B→F. On account of the fact that D is included in the knapsack G before E, the set of services {s_o} has been invoked in advance. As a result, only {B} requires to be invoked before E, which leads to cost_E = 2. Similarly, cost_D = 3, cost_F = 1 and the total cost of the solution 1 is calculated as cost_D + cost_E + cost_F = 3 + 2 + 1 = 6.

The cost of an item is changeable as well in the dynamic knapsack problem. As shown in the solution 2 (assume that the items are put into the knapsack G in order of C→D→E→F), the set of services {s_o, A} has been invoked when putting the item C into the knapsack. Consequently D can be invoked directly, which leads to the change of cost_D from 3 to 1.


In summary, only by ingeniously determining the dynamic volume and cost of an item can we solve the dynamic knapsack problem.





 §.§ The Knapsack-Variant Algorithm


The dynamic knapsack problem aiming at determining the optimal precursors of a service s can be described as follows. Given a knapsack s whose volume capacity is V_cap, and a set of items Pre(s) = {s_1, s_2, …, s_N} where N = | Pre(s)| represents the number of items, each with a dynamic volume volume_i and a dynamic cost cost_i, some items are selected from Pre(s) to fill the knapsack s with the objective of:


    minimize      ∑_i=1^Ncost_i · x_i
       subject to      ∑_i=1^Nvolume_i · x_i =  V_cap, 
              x_i ∈{0,1}.

where x_i represents the number of the item i to include in the knapsack. Unlike the 0-1 knapsack problem, all the volume_i and cost_i are uncertain here, which leads to the inapplicability of the 0-1 Knapsack Algorithm. In this section, a Knapsack-Variant Algorithm is proposed to solve the problem by determining the volume and cost of each service dynamically.

Let C[i][v] represent the minimal cost of selecting items from {s_1, s_2, …, s_i} (1≤ i≤ N) to fill a temporary knapsack whose capacity is v (1≤ v≤ V_cap), and I[i][v] the set of items selected to minimize C[i][v]. Then,

    C[i][v]     =
           min {C[i-1][v], C[i-1][v-volume_i]+cost_i}
       where      volume_i =  DV(s_i, In_s, Subs, v), 
             cost_i =  DC(s_i, I, i, v ,volume_i).

volume_i and cost_i are determined dynamically in the process of the dynamic programming, which is the quintessence of the knapsack-variant algorithm.

The function DV in Algorithm 3 is used to dynamically calculate the volume of an item. For the given temporary knapsack with the capacity of v, the outputs provided by service s_i for the knapsack are determined as Out_s_i∩ Subs[v]. Thus, the volume of the item s_i can be quantified by the quantization approach proposed in Sect.4.2. Inspired by the one-to-one match between the index(binary) and the Subs[index] in Table 1, a binary method is applied to determine the index which satisfies Subs[index] = Out_s_i∩ Subs[v], namely the volume_i.




For the given temporary knapsack with the capacity of v, the reason why the outputs provided by s_i for the knapsack are determined as Out_s_i∩ Subs[v] can be explained as follows. The knapsack with the capacity of v corresponds to a temporary service s_v with the inputs of Subs[v]. Therefore, the largest set of outputs provided by the service s_i for s_v is obviously Out_lar = Out_s_i∩ Subs[v]. However, if a smaller one Out_sma⊂ Out_lar is provided for s_v, Out_lar - Out_sma may require to be provided by extra services selected from {s_1, s_2, …, s_i-1}, which causes the loss of the local optimum, let alone the global optimum.

Moreover, the function DC shown in Algorithm 4 is applied to determine the cost of an item s_i. Since the items that have been included in the knapsack are cached in the data structure I, the set of services Ser ⊆ Servs(Ω^s_i) which haven't been invoked can be obtained drawing support from I, after which the cost of the item s_i is quantified as | Ser| + 1.



According to the optimization model in (2), by systematically increasing the values of i (from 1 to N) and v (from 1 to V_cap), the composition Ω^s with the minimal number of services will be finally obtained when i = N and v = V_cap.

    Len(Ω^s) = C[N][V_cap] + 1.

Therefore, the time complexity of the search step is O(NV_cap), so is the spatial complexity. However, the spatial complexity of (2) can be further optimized.

Considering that C[i][v] is only relevant to C[i-1][v^'] (1≤ v^'≤ v), C[i][v] can be replaced by an one-dimensional array C[v]. Then,

    C[v]     =
           min {C[v], C[v-volume_i]+cost_i}
       where      volume_i = DV(s_i, In_s, Subs, v), 
             cost_i = DC(s_i, I, i, v ,volume_i).

The problem can be solved by systematically increasing the values of i (from 1 to N) and decreasing v (from V_cap to 1), hence the spatial complexity is reduced from O(NV_cap) to O(V_cap).

The knapsack-variant algorithm is shown in Algorithm 5. Search steps on the graph are carried out layer by layer. Each search step depends on the optimization results of search steps in previous layers and is transformed into a knapsack problem that can be solved by (4). After completing the last search step of s_k, the expected composition with the length of Len(Ω^s_k) can be obtained.










§ EXPERIMENTAL RESULTS


In order to evaluate the performance of the proposed composition algorithm, we completed a group of experiments on eight public repositories from the 2008 Web Service Challenge. Services in each repository are defined using a WSDL file, and inputs and outputs are semantically described in a XML file called ontology.

Table 1 shows the detailed characteristics of each dataset. The number of services and concepts in the ontology of each dataset are shown in rows #Services and #Concepts respectively. Row #Sol.Services indicates the number of services for the optimal solution provided by the WSC'08.


To validate our composition algorithm, we compared our approach with three different approaches in the same experimental environment. For each dataset, we mainly focused on the number of services in the composition result (#C.Services) and the execution time to extract the solution from the service dependency graph (C.Time). The results are shown in Table 3.



As can be seen from Table 3, compared with other approaches, our approach can generate compositions with the same or smaller number of service. On the dataset D-06, our approach succeeds to find a better composition than the solution provided by the WSC'08 (35 versus 40). The execution time of <cit.> is no more than 3 ms on all datasets, which proves that the method is efficient enough to solve the service composition problem. However, it always generates the compositions with more services than the others. Considering that all the methods except <cit.> can find the minimal compositions, we compare our method with those methods in terms of the execution time.



Figure 10 shows that, our algorithm takes far less time to generate solutions than the other two. The dotted lines in blue and orange represents the average execution time of <cit.> and <cit.> respectively, while the green one shows the average time of our algorithm. Apparently our algorithm is over 10 times faster than <cit.> and nearly 17 times faster than <cit.> on average, which is a significant improvement.



We further compare our method with <cit.> and <cit.> taking the generation of the service dependency graph into account. As shown in Table 4, the size of the graph (G.Size) generated by <cit.> and <cit.> is smaller than ours because many optimizations are applied to reduce the graph size in these two methods, which leads to the fact that the time taken to generate the graph (G.Time) is longer than ours. Therefore, our knapsack-variant algorithm is executed over the the graph with lager size but is still over 10× faster than the other two, which sufficiently indicates the efficiency of our composition algorithm. Even though taking the G.Time into consideration, the total time (Tot.Time = G.Time + C.Time) of our mechanism is still much less than the others. As a result, our mechanism is more applicable to the large-scale or real-time scenarios.






§ CONCLUSIONS


In this paper we proposed an effective and efficient mechanism to automatically generate the minimal composition over a service dependency graph. Each search step on the graph is ingeniously transformed into a dynamic knapsack problem, after which the proposed knapsack-variant algorithm is executed to minimize the number of services by solving each dynamic knapsack problem. Moreover, a full validation performed on eight different datasets from Web Service Challenge 2008 shows that our algorithm outperforms the state-of-the-art methods, as it executes much faster than the state-of-the-arts while keeping the minimal composition results and is applicable to the large-scale or real-time scenarios.







§ ACKNOWLEDGMENT


This work is funded by the Natural Science Foundation of China (Nos. 61673204, 61321491), State Grid Corporation of Science and Technology Projects (Funded No. SGLNXT00DKJS1700166), the Program for Distinguished Talents of Jiangsu Province, China (No. 2013-XXRJ-018), and the Fundamental Research Funds for the Central Universities (No. 020214380026).

splncs  
 


