Automating the Procurement of Web Services

Automating the Procurement of Web Services ? Octavio Martín-Díaz, Antonio Ruiz-Cortés, Amador Durán, David Benavides, Miguel Toro Dpto. de Lenguajes y Sistemas Informáticos E.T.S. de Ingeniería Informática, Universidad de Sevilla 41012 Sevilla, España - Spain - Phone: +34 95 455 3871 Fax: +34 95 455 7139 - [email protected], [email protected], [email protected], [email protected], [email protected] Abstract. As government agencies and business become more dependent on web services, software solutions to automate their procurement gain importance. Current approaches for automating the procurement of web services suffer from an important drawback: neither uncertainty measures nor non-linear, and complex relations among parameters can be used by providers to specify quality-ofservice in offers. In this paper, we look deeply into the roots of this drawback and present a proposal which overcomes it. The key point to achieve this improvement has been using the constraint programming as a formal basis, since it endows the model with a very powerful expressiveness. A XML-based implementation is presented along with some experimental results and comparisons with other approaches. Keywords software procurement, web services, quality-of-service, traders. 1 Introduction As government agencies and business become more dependent on web services, software solutions to automate their procurement gain importance. It is generally assumed that decision criteria for choosing software packages stems from the user requirements they should fulfill. There are different types of requirements such as managerial, political, and, of course, quality requirements. There are a number of approaches which automate some activities of the procurement, most of them focus in quality requirements. However, these approaches suffer from several drawbacks that hamper their use when requirements that providers guarantee include uncertainty measures, non-linear and complex relations among parameters. In fact, if we want to achieve a competitive technology based on web services, their quality-of-service is an important issue to be taken into account, becoming one of challenges to be solved in the near future [31]. ? Supported by the Spanish Interministerial Commission on Science and the Spanish Ministry of Science and Technology under grants TIC2000-1106-C02-01, TIC2003-02737-C02-01 and FIT-150100-2001-78. In this context, software procurement [4,5] becomes web services procurement (WSP), an activity focussed on the acquisition of web services required by a webservice-based system, thus it is a critical activity for current web system developers. Some typical tasks involved in WSP are: –Specification of demands and offers, which should be checked for consistency in order to verify they do not contain any inner contradiction. –Search of offers, which should be checked for conformance in order to verify they fulfill the demand, so that the selection is limited to such offers. –Selection of the best choice according to the assessment criteria which is included in the demand. In this paper, we present a proposal to automate the procurement of web services. Our proposal improves on others in that it supports a symmetric specification model. Thus, providers can include in their offers requirements as complex as customers include in their demands. The key point to achieve this improvement has been using the constraint programming as a formal basis, since it endows the model with a very powerful expressiveness. A XML–based implementation is presented along with some experimental results and comparisons with other approaches. The rest of the paper is structured as follows. In Section 2, we introduce the notions of asymmetric and symmetric specification models, as well as an overview of related works. In Section 3, we propose the use of constraint programming as a means of achieving a symmetric specification model. In Section 4, we present briefly the main implementation aspects of our run-time framework, together with some experimental results. Finally, in Section 5 we summarise the presented work and the immediate future work. 2 Symmetric versus Asymmetric Models 2.1 Asymmetric models Let S be a multidimensional space whose dimensions are given by domains of qualityof-service parameters. Traditionally, a demand (  ) has been viewed as a subspace in S , whereas an offer ( ! ) has been viewed as a point in S . Thus, checking the conformance amounts to checking whether the point (the offer) belongs to the subspace (the demand) or not. See Figures 1.a and 1.b, respectively. This checking can be computed easily by evaluating ! in  . As an example, if a web service owns the offer ! = f MT T F =120 g , then it is conformantto the demand  1 = f MT T F  100 g because 120  100 , but not to the demand  2 = f MT T F > 120 g because 120 6 > 100 . This interpretation of conformance results in a model which is asymmetric with regard to the expressiveness of quality-of-service specifications. This semantics makes very difficult to specify offers when it is needed something else than a point, as an exampleto specify some uncertaintyor a space. As most of programminglanguages are able to check if a point is inside a space, whereas checking if a space includes another space is a hard question, most of platforms have adopted an asymmetric specification model. As well, these approaches with an asymmetric model usually own a limited expressiveness because conditions are restricted to simple expressions involving single parameters, so complex expressions are not allowed. (a) S S (b) Fig.1. Conformance in asymmetric models. 2.2 Symmetric models Alternatively, an offer can be also considered as a sub-space, just as demands, so that it represents the ranges of quality-of-service values that the corresponding web service guarantees to supply. In this way, an offer ( ! ) is conformant to a demand (  ) whenever the offer’s sub-space is inside the demand’s sub-space (see Figure 2.a), otherwise the offer is not conformant (see Figure 2.b). As an example, if a web service owns the offer ! = f MT T F > =120 g , then it is conformant to the following demand  1 = f MT T F > =100 g , but not to the demand  2 = f MTTF > 120 g because the offer’s instance value { MT T F = 120 } is out of the demand’s space. This interpretationofconformanceresults in asymmetricmodel becausequality-ofservice in demands and offers can be specified in the same way. This semantics makes the offer guarantee the complete range, not only a concrete value, i.e., we can not make any assumption on a concrete value, because it is equally possible any value in the subspace, and there is no control to get a concrete value. As well, symmetric approaches usuallyachieveagreaterdealofexpressivenesstospecifyquality-of-service,sincethere is usually no restriction on the number of involved parameters or type of operators, so that non-linear or more complex expressions are allowed. (b) (a) SS Fig.2. Conformance in symmetric models. 2.3 Related work Figure 3 shows a comparative study among the most prominent (as far as we know) quality-aware approaches to WSP. Briefly: –The UDDI Extension (UDDIe) [28] is based on the UDDI (Universal Description Discovery and Integration) services. UDDIe owns an asymmetric model when specifying demands and offers. IBM's WSME MME HP's MME Service UDDIe Our Proposal Customer's Provider's Name-Value Pair Properties Static/Dynamic Binding Scripts for Rule-based Reqs. Composition Single-Parameter Constraints on Parameters of Service (expandable) Name-Value Pair Properties Single-Par. Conditions on Properties (Qualifiers) Composition Multiple-Parameter Constraints on Parameters of Service Data Structuring Data Dictionary: pre-def. basic types sequences records DAML+OIL Ontology: datatypes and types subsumption Blue Pages Catalogues: pre-def. basic types catalogue extension basic and derived p. Dynamic View: The Process Model Advertisement/Submission Query/Submission Matchmaking Selecting Providers' Offers Advertising Querying Browsing Publishing Search and Discovery Creating Catalogues Offers Submission Demands Submission Matchmaking Catalogues, Parameters & Measures Stakeholders Providers Costumers Advertisers Requestors Providers Consumers Providers Costumers Quality-of-Service Documents Advertisements Queries Agreements Service Offers & Requests Publishing Inquiry Demands Offers Agreements Static View: The Lexicon The Reference Model Fig.3. A comparison of quality-aware approaches to WSP. –TheHP’sMatchmakingEngine(MME) [10] is basedontheDAML(DARPAAgent Markup Language) semantic web language [2]. It is the closest proposal to ours, because it owns a symmetric model to specify quality-of-service, and it uses constraints to do it, so it owns a great expressiveness. As well, it uses a Description Logic DL’s solver as a mean of carrying out the WSP-related tasks. Nevertheless, there is not currently any DL’s solver version able to process some of the most complex expressions which can be specified in MME. –The IBM’sWeb Services Matchmaking Engine (WSME) [12], which is related to Web Service Level Agreement (WSLA) [15,17], is based on the CORBA/ODP trader service. It owns an asymmetric model and there is no optimation of the selection because search results are only the lists of conformant offers. Nonetheless, there is a difference: relationships between demands and offers are bilateral. In the same way quality-of-service in offers is based on parameter/value pairs whereas demands impose conditions on them, it is also allowed that demands define their own quality-of-service parameters whereas the offers impose conditions on them. As an example, let an offer be given by the following quality-of-service specification ! = f me:M T T F =120 & your:national ity 2f BE;:::;UK gg and a demand  = f me:national ity = f IS g & y our:M T T F > 100 g , then the offer ! is not conformant to the demand  , because the condition it imposes on the demand (the Europe Union membership) is not fulfilled, despite of the offer fulfills conditions imposed by the demand. –Other languages for specifying quality-of-service and trader services the Qualityof-serviceModelingLanguage(QML)[8],theNoFunlanguage[6],andthe CORBA trader service [22]. These proposals are not directly related to WSP. 3 Supporting WSP with Constraint Programming We have chosen mathematical constraints as the way of specifying quality-of-service in demands and offers. In this way, checking conformance can be carried out just as a constraint satisfaction problem (CSP) or a constraint satisfaction optimisation problem (CSOP) [7,11,18,29]. In general, CSP-based modelling is quite simple and intuitive (in most cases) in the context of problems which we are dealing with. Constraint programming is an excellent support for symmetric specifications models, because it makes possible to check whether a space is included in another one, being these spaces treated as constraints. Our proposal owns a symmetric specification model with a great deal of expressiveness because of using constraints. 3.1 Constraint programming in a nutshell Constraint Programming (CP) has recently attracted high attention among experts from many areas because of its potential for solving hard real-life problems. Not only it is based on a strong theoretical foundation, but it is an attracting widespread commercial interest, as well. Constraints formalise those dependencies in physical worlds and their mathematical abstractions naturally and transparently. A constraint is simply a logical relation among several variables, each taking a value in a given domain. The constraint thus restricts the possible values that variables can take, and it represents a partial information about the variables of interest. An important feature of constraints is their declarative manner, i.e., they specify what relationships must hold without specifying a computational procedure to enforce them. CP is the study of computational systems based on constraints. The idea of CP is to solve problems by stating constraints (requirements) about the problem area and, consequently, finding solution satisfying all the constraints. The earliest ideas leading to CP may be found in the Artificial Intelligence dating back to sixties and seventies. The scene labelling problem [30] is probably the first constraint satisfaction problem that was formalised. The main step towards CP was achieved when Gallaire [9] and Jaffar & Lassez [14] noted that logic programmingwas just a particular kind of constraint programming.The basic idea behind Logic Programming (LP), and declarative programming in general, is that the user states what has to be solved instead of how to solve it, which is very close to the idea of constraints. Therefore the combination of constraints and logic programming is very natural, and Constraint Logic Programming (CLP) makes a nice declarative environment for solving problems by means of constraints. However, it does not mean that CP is restricted to CLP. Constraints were integrated to typical imperative languages like C++ and Java, as well. The nowadays real-life applications of CP in the area of planning, scheduling and optimisation rise the question if the traditional field of Operations Research (OR) is a competitoror an associate of CP. There is a significant overlapof CP and OR in the field of NP-Hard combinatorial problems. While the OR has a long research tradition and (very successful) method of solving problems using linear programming, the CP emphasis is on higher level modelling and solutions methods that are easier to understand by the final customer. Most recent advances promise that both methodologies can exploit each other, in particular,the CP can serve as a roof platform for integrating various constraint solving algorithms including those developed and checked to be successful in OR. As the above paragraphs show, the CP has an inner interdisciplinary nature. It combines and exploits ideas from a number of fields including Artificial Intelligence, Combinatorial Algorithms, Computational Logic, Discrete Mathematics, Neural Networks, Operations Research, Programming Languages, and Symbolic Computation. Currently, we see two branches of CP, namely constraint satisfaction and constraint solving. Both share the same terminology but the origins and solving technologies are different. The former deals with problems defined over finite domains and, currently, probably more than 95% of all industrial constraint applications use finite domains. Therefore,we deal with constraint satisfaction problems mostly in this paper. The latter shares the basis of CP, i.e., describing the problem as a set of constraints and solving these constraints. But now, the constraints are defined (mostly) over infinite or more complex domains. Instead of combinatorial methods for constraint satisfaction, the constraint solving algorithms are based on mathematical techniques such as automatic differentiation, Taylor series or Newton method. Constraint Satisfaction Problems [29] have been a subject of research in Artificial Intelligence for many years. A Constraint Satisfaction Problem (CSP) is defined as a set of variables each ranging on a finite domain, and a set of constraints restricting all the values that variables can simultaneously take. A solution to a CSP is an assignment of a value from its domain to every variable, in such a way that all constraints are satisfied at once. We may want to find: i) just one solution, with no preference as to which one, ii) all solutions, iii) an optimal, or at least a good solution, given some objective function defined in terms of some or all of variables. Solutions to a CSP can be found by searching (systematically) through all possible value assignments to variables. In many real-life applications, we do not want to find any solution but a good solution. The quality of solution is usually measured by an application dependent function called objective function. The goal is to find such solution that satisfies all the constraints and minimise or maximise the objective function, respectively. Such problems are referred to as Constraint Satisfaction Optimisation Problems (CSOP), which consists of a standard CSP and an optimisation function that maps every solution (complete labelling of variables) to a numerical value [29]. 3.2 Consistency and conformance Whenever a new demand or offer is submitted, its consistency needs to be checked, i.e., whether or not it contains any inner contradiction. This is interpreted as a CSP, so that if the correspondingCSP is satisfiable, then the demand or offer can be considered as consistent. The corresponding CSP for a demand or offer is composed of all the constraints it contains. On the other hand, the best choice selection regarding with a demand implies the previous checking for conformance, because the search is reduced to conformant offers. As we are using constraint programming, checking of conformance lies in determining whether each and every solution to the offer’s CSP is also a solution to the demand’s CSP. In this way, the corresponding CSP for checking the conformance is constructed according to the definition given in [18]: conf ormance ( !;  ) , sat ( c ! ^: c  )= false where ! is the offer and c ! its corresponding CSP,  is the demand and c  its corresponding CSP, and sat is a function that we identify with the CSP solver which is being used. It can be applied on a CSP c so that it returns one of the following results: tr ue if c is satisfiable, false if not, and ? if the solvercannot determinewhether c is satisfiable or not. 3.3 Optimality More often than not, it is possible to have several offers which are conformant to the same demand for a web service, then we should select that offer which is the best choice. This selection is carried out according to the assessment criteria the customer includes in his or her demand. These criteria may be given by utility functions [3,16, 21] which, in general, have the signature U :  ! [0 ; 1] where  is the measuring domain of a quality-of-serviceparameter. Utility functions assign an utility assessment (ranging from 0 to 1) to every quality-of-service value it can take, so the greater the assessment, the better the consideration of the customer. Therefore, utility functions allow the establishment of an objective criteria, given by customers, in order to select those offers which better fulfill the demands. Figure 4 shows several utility functions corresponding to examples in this section. Utility for Mean Time To Failure 0,5 1 0,25 1209060 MTTF 0,75 45 75 105 140 010 20 30 0,5 1 0,25 0,75 05152535 MTTR Utility for Mean Time To Repair Modem Modem ISDN ISDN Modem ADSL ISDN ADSL Modem ISDN ADSL ADSL Utility for Media Support MEDIA 0,5 1 0,25 0,75 0 { } Fig.4. Utility functions for MTTF , MT T R , and MEDIA . Althoughwe can make useof anykind of functionto specify utility functions,linear piecewise functionsare often the preferred.As an example,the utility functionfor a numeric quality-of-serviceparameter can be definedby means of polylines determined by a sequence of coordinatepoints such as ( x 1 ;u 1 ) ; ( x 2 ;u 2 ) ;:::; ( x n ;u n ) , where every x represents a value in the measuring domain of the quality-of-service, and u its assessment in the range [0,1]. The corresponding utility function is then given by: U ( x )= 8 > > < > > : u 1 + u 2 ; u 1 x 2 ; x 1 ( x ; x 1 ) if x 1  x<x 2  u n ; 1 + u n ; u n ; 1 x n ; x n ; 1 ( x ; x n ; 1 ) if x n ; 1  x  x n ? if x<x 1 o x>x n We are not usually interested in computing the utility assessment of an unique quality-of-service parameter, but on maximising the global assessment of offers in order to select the best one, being these offers conformant to the demand. Nevertheless, we can not compute the maximum offers’utility assessments when comparing them. As an example, let the following offers ! 1 = f 60  MT T F  120 g and ! 2 = f 90  MT T F  110 g . Intuitively, the first is better, because if MT T F =120 then U ( ! 1 ) = 1 . However, the offer is guaranteeing the complete range, not only a concrete value, so we can not make such assumption because it is equally possible that MTTF =60 , and there is no control to get a concrete value. Therefore, we compare the minimum utility assessments of offers. In this way, the latter offer is the better, because if MTTF =90 then U ( ! 2 ) = 0 : 5 , whereas the worst assessment of the first offer is 0.25, at most. Formally, the best offer ( ! S ) can be defined as: ! S = ! 2    8 ! i 2   ;f ! g U  ( ! ) U  ( ! i ) where ! and ! i stand for offers in the set   of conformantoffers to the demand  , and the U  ( ! ) utility function of an offer ! according to assessment criteria in demand  is defined as: U  ( ! )= min P  2 c ! w   U  (  ) st c ! where  represents a quality-of-service parameter which is involved in the offer’s CSP c ! , and U  (  ) its utility function, and w   its assigned weight, according to assessment criteria in demand  . On the other hand, weights are needed to express that a qualityof-service parameter is preferred to another. 3.4 An example of contraint-based quality-of-service specification Figure 5 shows several catalogues, demands, and offers written in QRL [23,26], the language which we have defined for specifying quality requirements. Figure 4 shows the graphical representation of utility functions appearing in Figure 5. These demands and offers will be used in the examples along these paragraphs. In this case, the involved quality-of-service parameters are the Mean Time To Failure (MTTF),theMean Time To Repair (MTTR),andtheMedia Support (MEDIA).Note the included demand and offers are all consistent, because their corresponding CSP are satisfiable, as well as offers are conformant to the demand, because the corresponding CSP for checking the conformance are not satisfiable, according to definitions in Section 3.2. Since both offers are conformant to the demand, we will have to compute the utility functions to compare them. According to definitions in Section 3.3, both offers own U ( MTTF = 110) = 0 : 83 and U ( MT T R =10) = 0 : 8 ,velazquez owns U ( MEDIA )=1 , and zipi owns U ( MEDIA )=0 : 5 . Therefore, utility assessment of velazquez is 0 : 9  0 : 83 + 0 : 05  0 : 04 + 0 : 05  1=0 : 84 , and utility assessment of zipi is 0 : 9  0 : 83 + 0 : 05  0 : 04+0 : 05  0 : 5= 0 : 815 , so the best offer is velazquez. // A catalogue of Reliability-related QoS parameters catalogue Reliability { MTTF { description: "Mean Time to Failure"; domain: real [0,+inf) minute; }; MTTR { description: "Mean Time To Repair"; domain: real [0,+inf) minute; }; } // A catalogue of Multimedia-related QoS parameters catalogue Multimedia { MEDIA { description: "Media Support"; domain: set { modem, ISDN, ADSL }; } } // Web service offer supplied by Velazquez using Reliability, Multimedia; offer for IVideoServer { O1: MTTF >= 110 and MTTF <= 120; O2: MTTR > 5 and MTTR <= 10; O3: MEDIA = {ADSL,ISDN,modem}; } c) Several offers. a) Catalogues of quality-of-service parameters. // Web service demand for IVideoServer using Reliability, Multimedia; demands for IVideoServer { D1: MTTF / (MTTF + MTTR) >= 0.9; D2: MEDIA includes {modem,ISDN}; } assessment { MTTF {90, { (0,0), (90,0.5), (120,1) } }; MTTR {05, { (0,1), (20,0.6), (30,0) } }; MODEM {05, case MEDIA = { } : 0.01; case MEDIA = {modem} : 0.1; case MEDIA = {ISDN} : 0.3; case MEDIA = {ISDN,modem} : 0.5; case MEDIA = {ADSL} : 0.9; case MEDIA = {modem, ADSL} : 1; case MEDIA = {ISDN, ADSL} : 1; case MEDIA = {modem, ISDN, ADSL} : 1; } } b) A demand. // Web service offer supplied by Zipi using Reliability, Multimedia; offer for IVideoServer { O1: MTTF >= 110 and MTTF <= 120; O2: MTTR > 5 and MTTR <= 10; O3: MEDIA = {ISDN,modem}; } Fig.5. Demands and offers written in QRL. 4 Implementation and Experimental Results 4.1 Overview of the prototype’s architecture We are developinga prototypeof a run-timeframeworkfor WSP [19,20,24,27], whose preliminary version is available at http://www.lsi.us.es/˜octavio. In this paper, we give a brief review, together with some experimental results we have recently obtained. A components view of the run-time framework is shown in Figure 6. Selecting a multi-level architecture along with the deployment of the components as web applications or web services have been critical design decisions. Components are split up among the upper user-interface level, the intermediate service and utility levels, and the bottom repository level. These components can be reusable and interchangeable.Service level includes those componentswhich implement the IImportService interface (functions related to submission of demands and searching for best conformant offer), and the IExportService interface (functions related to submission of offers). These components have need of invoking checkings for consistency, conformance, and optimum search. These functions are implemented by the Quality Trader Web Service [19] at the utility level. Each function has a similar operation: 1. It takes the involved demands and offers written in XML as parameters.