WWW 2008 / Poster Paper April 21-25, 2008 · Beijing, China Speeding Up Web Service Composition with Volatile External Information John Harney LSDIS Lab, Dept. of Computer Science University of Georgia, GA 30602 Prashant Doshi LSDIS Lab, Dept. of Computer Science University of Georgia, GA 30602 jfh@cs.uga.edu ABSTRACT This paper introduces a novel method for composing Web services in the presence of external volatile information. Our approach, which we call the informed-presumptive, is compared to previous state-of-the-art approaches for Web service composition in volatile environments. We show empirically that the informed-presumptive strategy produces compositions in significantly less time than the other strategies with lesser backtracks. pdoshi@cs.uga.edu expected to change due to the revised parameters, then the informedpresumptive will backtrack to the point in the composition where the queried service occurs. Otherwise, it ignores the changed parameter value, as its impact on the composition is negligible. Thus, we seek to find a range of revised values that are expected to induce a change in the composition. Using the technique of gradient descent, we find the ranges of values with minimal computational overhead. In using the informed-presumptive, we form compositions in less time compared to previous state-of-the-art strategies, by eliminating backtracks that are not required. We empirically demonstrate the speed up using a simulated volatile environment. Categories and Subject Descriptors H.3.5 [Online Information Systems]: Web-based Services General Terms Algorithms, Theory 2. METHODOLOGY Keywords Web services, Adaptation, Volatile environments, Expiration times For a composition problem containing states, S , and component services, A, we find the service(s) to be invoked at each state s S . ^ Let A(s) A be the choice of services available at each state. The composition finds the optimal service(s) that maximizes the value function: (s) = arg max V a ^ aA(s) 1. INTRODUCTION Web service compositions (WSCs) are an important area of study in services oriented computing. They offer the potential for automatically formulating processes in an efficient and timely manner. WSCs are predominantly modeled as being static, where the participating services are assumed to exhibit fixed quality of service (QoS) parameters during the composition and execution. However, in practice, WSC environments are often volatile ­ QoS of participating services may change during the composition. Therefore, WSCs must compose in the presence of this volatility. Previous approaches [?, ?] associate expiration times with the service parameters. When the parameters of the component services expire, the WSC issues a query to gather the updated information. If the new parameter values are different from the previous ones, the WSC backtracks to the step in the composition where the service with the revised parameters is used. A significant limitation of these approaches is that some of the backtracks are redundant ­ changes in the parameter values do not necessitate changes in the composition. As excessive backtracking leads to time-consuming compositions, we may improve on these approaches by reducing the amount of backtracking. We introduce a new method for managing volatility during composition, which we call the informed-presumptive approach. The method predicts whether the newly queried parameter values will cause significant changes in the composition. If the composition is Copyright is held by the author/owner(s). W W W 2 0 0 8 , April 21­25, 2008, Beijing, China. ACM 978-1-60558-085-2/08/04. (1) In Eq. ??, is the optimal policy which maps each state to the optimal service(s) to invoke at that state, : S A; In defining the value function, V a , we borrow from [?], and use a weighted summation of the QoS parameters of the service, a, and sum over ¯ all services in the composition. We use the normalized cost, C a , ¯a and availability Av . Let pa denote the revised parameter value vector for the service, a: def ¯ ¯a pa = [C a , Av ] (2) ¯a ¯ where C a and Av are the revised cost and availability obtained by querying service a. (Of course, pa can be extended to account for other QoS parameters as well.) As a change in the value function indicates a change in the composition, we seek those revised parameter vectors for each service that bring a change in the value function. Let be the original policy and be the revised policy given the new parameter vector, then we find all pa for which: V (pa ) - V (pa ) = 0 a (3) V (p ) is the expected value of the original composition, , in the presence of the revised parameter vector, pa , of service a, while V (pa ) is the value of the composition following the optimal policy . The parameter vectors, pa , that satisfy Eq. ?? are those for which no backtracking is needed. We may view the difference in Eq. ?? as the error in using the original composition given the revised parameter vector, pa , and 1201 WWW 2008 / Poster Paper Average Composition Times 1400 Lazy Eager Presumptive Informed-Presumptive 1400 Lazy Eager Presumptive Informed-Presumptive 1400 April 21-25, 2008 · Beijing, China Lazy Eager Presumptive Informed-Presumptive 1200 Composition Time Steps Composition Time Steps 1200 Composition Time Steps 1200 1000 1000 1000 800 800 800 600 600 600 400 400 400 200 200 200 0 0 0.2 0.4 0.6 Change Likelihood 0.8 1 0 0 0.2 0.4 0.6 Change Likelihood 0.8 1 0 0 0.2 0.4 0.6 Change Likelihood 0.8 1 (a) (b) (c) Figure 1: The average composition time for the four strategies with a volatility ratio of (a)1, (b).5, (c).33. denote the difference as E (pa ). This allows us to model the problem of finding the vectors satisfying Eq. ?? as a gradient descent where we descend down the error surface, E (pa ), until we reach the minimal plateau (E (pa ) = 0). For performing the gradient descent, we update pa in the following way: pa pa + pa where pa = - E (pa ) (5) Here, is the step size, 0 1. The negative sign indicates that we take a step in the direction of the reducing gradient. For our application, the definition for E (pa ) is the vector: ~ E (pa ) E (pa ) (6) ¯ , Ava ] ¯ Ca Fortunately, Theorem ?? simplifies the task of finding E(pa ). E (pa ) = [ T H E O R E M 1. As V a is a linear function of the QoS parameters of a service, a, the gradient E (pa ) is constant. Theorem ?? allows us to perform gradient descent with minimal computational overhead, as we show later. (4) with varying cost and availability values. Let the time to compose a step in the composition (without any backtracks) be tsomp , the c expiration time for a service a be taxp , and the query lag time for e a service be ta lag . We use two measurements of volatility, (a) the Q volatility ratio, during the composition of a single step, and (b) the likelihood that the QoS parameter of a service will change upon expiration. tsomp c , taxp e which signifies how often a service expires 4. RESULTS 3. EXPERIMENT Our experimental evaluation focuses on comparing composition times when using the informed-presumptive approach and the previously existing strategies. These are: ·The eager strategy, which on service expiration, issues a query to the service for the revised information. It suspends the WSC until the revised information is received and backtracks if there is a difference in the QoS value. · The lazy strategy, which on service expiration, issues a query and continues the WSC until completion, at which point the revised information is processed. It backtracks if there is a difference in the QoS value. · The presumptive strategy, which on service expiration, issues a query and continues the WSC until the revised information is received, It backtracks if there is a difference in QoS value. Among these strategies, the presumptive approach was shown to perform the best. For our experiments, we utilized a travel planning scenario in a simulated volatile environment, and implemented the above strategies in addition to the informed-presumptive. Each component of a travel plan (ie. booking a plane ticket, reserving a hotel room, and renting a car) is a single step in the composition. At each step, we gave a choice of 10 vendor Web services, Figure ?? shows the results of our experiments for volatility ratios 1, 0.5, and 0.33. In Figure ??(a), we see that when services often expire during composition, the informed-presumptive approach shows lower composition times on average than the other strategies. However, at a low likelihood of change ( 20 percent), the informed-presumptive performs slightly worse as precision errors due to overstepping in the gradient descent become visible. In Fig. ??(b), the informed-presumptive has a significantly better average composition time than the others. For lower volatility levels, such as 0.33 (Figure ??c), the informed-presumptive continues to outperform the strategies, although the services expire less often. The improved composition times of the informed-presumptive are achieved by eliminating unnecessary backtracks employed by the other strategies. 5. CONCLUSIONS AND FUTURE WORK We have introduced a new approach for managing WSC in volatile environments that outperforms previous state-of-the-art composition strategies. We show that a significant time speed-up may be gained by predicting whether changed parameters induce changes in the composition, thus eliminating unnecessary backtracks. When complex value functions and dependencies are introduced to the composition, performing gradient descent is likely to become a time-consuming task. Thus, our future work will explore implementing our approach on more complex compositions. 6. REFERENCES [1] V. Agarwal, G. Chafle, K. Dasgupta, N. Karnik, A. Kumar, S. Mittal, and B. Srivastava. Synthy: A system for end to end composition of web services. JWSR, 3(4), 2005. [2] T.-C. Au, U. Kuter, and D. S. Nau. Web service composition with volatile information. In ISWC, 2005. [3] T.-C. Au and D. Nau. Reactive query policies: A formalism for planning with volatile external information. In CIDM, 2007. 1202