2011 IEEE International Conference on Services Computing
Self-adaptive Fuzzy QoS-driven Web service discovery Romina Torres and Hern´an Astudillo Departamento de Inform´atica Universidad T´ecnica Federico Santa Mar´ıa, UTFSM Valpara´ıso, Chile Email:
[email protected];
[email protected]
Rodrigo Salas Departamento de Ingenier´ıa Biom´edica Universidad de Valpara´ıso, UV Valpara´ıso, Chile Email:
[email protected]
by quality. But quality is a fuzzy term, typically expressed in words. In the Software Engineering field, there are strategies to deal with the uncertainty of the environment by means of quantifying the non-functional requirements (NFRs) by assigning a measurement strategy to compare components based on quantified quality aspects [2]. So, typically, we are able to determine what are our acceptable ranges for a quantified quality aspects. So, the problem now is to identify these acceptable ranges, because they highly depend on what the market is offering at the moment. On the other hand, current Web service providers are moving from the Universal Description, Discovery and Integration (UDDI) repositories to the public Web-based registries [3]. Unfortunately, current UDDI registries do not provide builtin capabilities to test the quality of service (QoS), or even to publish in a standard way the QoS that the providers claims. Public Web-based registries – like ProgrammableWeb 1 – provide a basic quality registry to quantify the QoS of the services. There are several works that investigate how to quantify the QoS in order to be able to compare functionalequivalent services. Ran [4] introduced the idea that the service providers should supply the QoS measurements at registration time and moreover, a QoS certified framework could serve as a certification authority for these new augment Web service descriptors. However, Al-Masri & Mahmoud [3] indicate that it is a flaw that the QoS claims are provided by the service providers themselves and also because it involves major changes in current implementations of UDDI registries. Instead, the authors proposed a supporting tool that collects the Web services information from the Internet, and it measures the QoS with benchmarking. Zheng et al. [5] conducted a study on the QoS of over 20,000 real Web services, this dataset was publicly released. There are several works that are augmenting the Web service descriptions with precise service QoS values. So, QoS-aware service discovery can become real and in this work we will assume that the process exist. Because the QoS constraints are non-functional requirements (NFR), it is not easy to specify it in order to be able to determine whether or not it is satisfied. NFRs are usually vague and imprecise in nature [6]. NFRs are typically described
Abstract—Due to the high proliferation of web services, selecting the best services from functional equivalent service providers have become a real challenge, where the quality of the services plays a crucial role. But quality is uncertain, therefore, several researchers have applied Fuzzy logic to address the imprecision of the quality of service (QoS) constraints. Furthermore, the service market is highly dynamic and competitive, where web services are constantly entering and exiting this market, and they are continually improving themselves due to the competition. Current fuzzy-based techniques are expert and/or consensusbased, and therefore too fragile, expensive, non-scalable and nonself-adaptive. In this paper we introduce a new methodology to support requesters in selecting Web services by automatically connecting imprecisely defined QoS constraints with overly precise service QoS offerings over the time. We address the dynamism of the market by using each time a modified fuzzy c-means module that allows providers to automatically organize themselves around the QoS levels. The advantage of our approach is that consumers can specify their QoS constraints without really knowing what are the current best quality ranges. We illustrate our approach with a case of study. Keywords-Non-Functional Requirements, Quality of Services, Web service discovery, Dynamic environments, Fuzzy modeling.
I. I NTRODUCTION Discovering the potential Web services candidates from a large collection is the most critical activity to successfully build software. If the component candidates are wrongly chosen, their evaluation will not deliver adequate components to the selection and composition stages [1]. Due to the proliferation of services and the changing nature of this market, for architects can become almost impossible to manually determine which alternatives are the best based only on their experiences and knowledge. Even more, today service market offers are rapidly expanding. As Web services proliferate, a key issue of Web service discovery is to identify relevant services to implement customers’ requirements, while at the same time, the users need new criterias for distinguishing functional-equivalent services by assessing the performance of the Web services. The success of correctly assessing functional-equivalent services relies on the quality that they provide. These components can be totally different in terms of reliability, latency, response time and in general non-technical aspects like cost and licensing. Therefore, the discovery process should be driven by not only functional aspects, but also 978-0-7695-4462-5/11 $26.00 © 2011 IEEE DOI 10.1109/SCC.2011.87
1 http://www.programmableweb.com
64
II. F UZZY Q O S
using words in natural language, because the subjectivity of the QoS requirements. The fuzzy theory can be a basic tool for modeling the customers’ service quality evaluations and thus select the most suitable service provider. Current research works have proposed fuzzy-based techniques for representing vague QoS constraints and preferences, and with this base they support the latter activities as web services discovery and composition. Tran et al. [7] review the prominent works in QoS based ranking algorithms for web services that apply fuzzy theory for representing imprecise QoS constraints. Chen et al. [8] and Xiong et al. [9] model the Web service selection also as a fuzzy multiple criteria decision making (FMCDM). There are several other works as [10], [11], [12], [13], [14] that use fuzzy logic modeling to select, rank and compose Web services. Recently, Li et al. [15] have proposed a method to rank web services based on fuzzy QoS attributes, moreover the method seeks the weights of relevance of these attributes.
EVALUATION FOR
W EB S ERVICE RANKING
A. Fuzzy Modeling of Web Service QoS attributes Fuzzy sets were first introduced by Zadeh [16] as an extension of the classical set theory. Zadeh’s seminal paper was disseminated widely different fields of science and technology. Furthermore, fuzzy theory has becoming an important tool for decision making in an environment of imprecision, uncertainty and incompleteness of information as in the web services virtual market. A fuzzy set A in a collection of objects U is defined as a set of ordered pairs A ≡ {< x, μA (x) > |x ∈ U }, where μA (x) is the degree of membership, expressed as a numerical value in the closed interval [0, 1], of the element x in U to the fuzzy set A. Closer values to 1 indicate higher degrees of membership. Zadeh defined the basic operations on fuzzy logic: the disjunction (OR) μA∨B (x) := max{μA (x), μB (x)}, the conjunction (AND) μA∧B (x) := min{μA (x), μB (x)} and negation (NOT) μ¬A (x) := 1 − μA (x). On the other hand, Zadeh also defined a linguistic variable as a variable whose values are words or sentences in a natural or artificial language. A linguistic variable is described by a) the name or label; b) a term set that is the set of values that it can take; c) a definition domain of the term set is the Universe of discourse; d) and an interpretation accomplished by an expert. The linguistic terms are labelled fuzzy sets. There are many functions for representing linguistic terms, where the triangular, trapezoidal and gaussian shapes are the most popular kind. The fuzzy sets can be defined parametrically with a few number of parameters, where the values for these parameters are typically set up by a group of experts or by consensus of users. Consider as example the linguistic variable named response time as a quality attribute of Web services. Lin et al. [17] proposed to describe the different levels of QoS with five linguistics terms: {Poorly Acceptable, Almost Acceptable, Acceptable, Very Acceptable, Extremely Acceptable}. An important remark is that the linguistic terms are user-dependent. Then, when we ask to Web service consumer for the needed response time, he answers in terms of these five classes. According to this response value, we can return all the Web services that belong to the class that the consumer requires in some degree that the user could also specify.
However, the consumer does not know the state-of-art of the quality levels of the web services compared with the best possible one. The aforementioned techniques lack an automatic mechanism to support the evaluation of the quality aspects. Most works are based on the static knowledge of an experts committee or customer consensus. In other words, when the customers specify the QoS required for a specific functionality, they specify for each property (e.g. response time) the fuzzy set that best describes their needs. The problem here is that it is assumed that experts know the range values and distributions for each quality attributes without considering the Web services data. The web services are arranged as a virtual market, which is highly dynamic, where web services are constantly entering into and exiting from this market. For this reason, to define the desired limits for each quality concern and for each Web service functionality category becomes a hard problem. In this paper we introduce a new methodology to support requesters in selecting Web services by automatically connecting imprecisely defined QoS constraints with overly precise service QoS offerings. Our proposal uses an automated technique to determine the fuzzy terms of the quality aspects of the Web services based on a variant of the fuzzy c-means clustering algorithm, releasing the customer the responsibility to understand the complex, growing and changing service market. The advantage of our approach is that consumers can specify their QoS constraints without really knowing what are the current best quality values. We illustrate our approach with a case of study.
B. Modeling Web service selection as FMCDM The simplest fuzzy model consists of a set of rules of the type “if-then” with the structure as follows: if < condition 1 > and < condition 2 > and...
The reminder of this article is structured as follows. In the next section, we introduce a fuzzy approach to evaluate the QoS attributes of web services and with a FMCDM strategy the web services are ranked. In the third section, our proposal of a self adaptive fuzzy QoS-driven web services discovery process is stated. Section 4 explains implementation details and Section 5 illustrates our approach with a case study. Conclusions and further work are given in the last section.
...and < condition t > then < conclusion > where < condition i > is a premise of type “x is At ”. x represents the value of the t-th attribute. At is a predicate naming the linguistic term of the correspondig to the t-th attribute, and it is given by a fuzzy set. < conclusion > is a fuzzy set which characterizes the consequent of the “if-then” fuzzy rule when the conditions are satisfied.
65
For example, consider the following “if-then” fuzzy rule as a user requirement of a functional equivalent web-services.
C. Fuzzy c-means variant for the generation of fuzzy term sets Instead of defining the fuzzy sets with an expert committee or user opinions, we prefer to use clustering in order to identify the classes in the distribution of the data. This should be more robust and less expensive than the classical manner because the Web service market is currently expanding and changing and users and even experts may not know much about the subject he/she is clustering, may not be familiar with the clustering system, the reality that they knew have being changed, or also because experts are not always available. The objective of fuzzy clustering methods is to divide a given dataset into a set of clusters based on similarity. In classical cluster analysis each datum must be assigned to exactly one cluster. Fuzzy cluster analysis relaxes this requirement by allowing membership degrees, thus offering the opportunity to deal with data that belong to more than one cluster at the same time. Each cluster is represented by a center and an additional information about the shape of the cluster. The degrees of membership to which a given data point belongs to the different clusters are computed from the distances of the data point to the cluster centers. The Fuzzy C-Means (FCM) clustering algorithm (see [18] for details) is applied to each quality attribute. After applying the FCM algorithm, the set of cluster prototypes, V = {v1 , . . . , vc } and the partition matrix U are available. The value uij ∈ U of the fuzzy partition matrix determine the membership degree at which the attribute of th j-th web service sj fulfill the i-th linguistic term. The membership degrees of the dataset to the corresponding clusters are obtained by minimizing iteratively the objective function:
R1 : if availability is extremely acceptable then the web service is ranked high R2 : if response time is at least acceptable then the web service is ranked high Under this situation, the degree of membership of the quality attributes of the premises are used to scale the fuzzy sets of the corresponding conclusions. For m QoS attributes and n candidate web services, the judgment matrix Q = (qij )m×n , where qij = μAij (xij ) is the value of the membership degree of the i-th QoS attribute of the j-th web service candidate. For a particular requirement and its NFRs, there is a set of potential candidates functional-equivalent but with different QoS and price as well. Therefore, in order to support to consumers ask for services, first a committee of experts must agree what are the possible alternatives for each quality concern. For each one of these alternatives the experts must agree what are the fuzzy set that best represent it as well as what are the parameters for each one. Typically, this is an iterative process that convey to the final agreement, and these values should be validated against the data. Then, the crisp data of Web services (values of QoS of the offering), must be transformed to these fuzzy sets. Under dynamic environments, the process should be repeated time after time, which is unacceptable because for some organizations experts are expensive resources. After the system is already set up, consumers can make request in order to discover services that best match their requirements. The steps are describe as follow:
Jm (U, V ; W S) =
m
wi · qij
2 um ij d (sj , vi )
(2)
j=1 i=1
1) The consumer specifies the functional requirements and the NFRs. For each NFR, he must specifies what is the minimum level that he can accept for this particular quality concern. For instance, for response time he could say that at least an acceptable response time would be fine. Note that the statement at least acceptable means acceptable ∨ very acceptable ∨ extremely Acceptable and the basic fuzzy logic operations can be applied. 2) The judgment matrix Q is evaluated with the fuzzy terms defined in the previous step. 3) The consumer indicates the relative importance of all the quality criteria on this particular request. The consumer gives a value m between [0, 1] to the quality concern wi , such that i=1 wi = 1. 4) The overall quality score of each candidate Web service wsj is computed by using the weighted sum method: score(wsj ) =
m c
The minimization process with respect to uij and vi is done separately and necessary conditions for a minimum yields update equations for both: uij =
c k=1
1 d2 (sj ,vi ) d2 (sj ,vk )
n 1 m−1
j=1 vi = n
um ij sj
j=1
um ij
.
(3)
Due to probabilistic constraints imposed to minimize the objective function, the membership matrices are non-convex discrete fuzzy sets. In this paper we use a variant of the fuzzy c-means algorithm [19] that prevents the generation of nonconvex fuzzy terms and ensures that the all the classes are correctly mapped to its domain. III. S ELF - ADAPTIVE F UZZY Q O S- DRIVEN W EB S ERVICE D ISCOVERY PROCESS The Self-adaptive Fuzzy QoS-driven Web Service Discovery process proposed in this paper is based on the continuos analysis of what the Web service market is offering in term of quality. The innovation of this process centers on i) the use of an adaptive module (based on fuzzy c-means) that allows
(1)
i=1
5) Functionally equivalent web services are ranked according equation (1).
66
Fig. 3: Functional Clustering Process
then the fuzzy c-means find what are the members of these categories and in which degree. Of course, a QoS claim of a Web service could be belong to more than one class with some belonging degree to each one. Based on the duration of the epochs, each X time, the system perform this process again in order to reflect what the market is offering. In Figure 2 the Web service consumer perspective is shown. For each functional requirement (FR) that the consumer has, a set of non-functional requirements (NFR) must be specified. Based on the modified (or fuzzy) utility tree technique of the ATAM method (see [20] for more details), consumer can refine their NFR into QoS aspects. For each QoS aspect, the quality tree technique allows to obtain the relative importance between them as well as the required level for each QoS aspect. In both figures, Figure 1 and Figure 2, there is a subprocess that allows to match FR and NFR with Web services and QoS claims. In the side of the customer we have fuzzy quality requirements in terms of words and on the other side we have crispy QoS measurements of real Web services. In the following subsection we will explain each subprocess.
Fig. 1: Clustering process that allows providers self-organizing in functional clusters based on their functionality as well as in QoS level classes for each addressed QoS aspect
B. Clustering Web services based on their functionality using the SOM technique
Fig. 2: Refining Process of FR and NFRs into QoS requirements and their relative importance between them
In Figure 3 is showed the principal steps of the functional clustering subprocess: token extraction, filtering stop words, steaming words, and based on the TF/IDF vectors extraction clustering the Web services using growing hierarchical self organizing maps (GHSOM) (see [21]). We choose GHSOM instead of SOM because this is a recurrent process and we do not want to lose the current clustering of the data, we only want to add the new knowledge of the new data. With GHSOM we obtain a hierarchical classification of the description of the Web services. Each leaf map is considered as a functional cluster. Each functional cluster is a collection of terms that represent it and a set of descriptions (Web services) that are classified into that cluster.
to dynamically organize the providers around the pre-defined quality levels, and ii) a methodology that allows customers to refine their requirements in terms of quality constraints. A. An overview of the Self-adaptive Fuzzy QoS-driven Web Service Discovery process The overall process is described by joining Figure 2 with Figure 1. In Figure 1 (reading from left to right) there are four main steps in the process. The functional crawler step collects from different Web-based repositories the Web service descriptors. Then, the QoS crawler, based on an endpoint list sent by the previous step, runs benchmark tool over the Web services in order to gather the QoS measurements. Then, the functional clustering step, based on the Web service description language (WSDL) files clusters the Web services according to their functionality. Then, for each functional cluster, we perform the QoS-fuzzy clustering step that clusters for each QoS aspect the claims of each Web service in that functional category. The number of QoS categories are five,
C. QoS Clustering Web services In Figure 4 is showed the QoS-fuzzy clustering subprocess that organize the Web services that are currently in the market around of the five levels of quality. This subprocess must be performed for each functional cluster and for each QoS aspect. After the functional clustering finishes to functionally classify all the gathered Web services (or only the new ones if we are processing an epoch), it send for each cluster the list of
67
Fig. 4: Clustering Web service claims based on Fuzzy classes and Fuzzy c-means
Fig. 5: Fuzzy utility tree
endpoints of the Web services that must be tested using the benchmark tools. In this paper we assume that this process should exist and it should be like the proposed in [3]. After this step, we obtain for each quality aspect of each Web service a measurement. Our hypothesis is that the market is continually changing, and therefore, we need an automatic and almost real time mechanism capable to classify them based on their QoS the different Web services. To this end, we define five cluster of QoS or classes: “poorly acceptable” (PA), “almost acceptable” (AA), “acceptable” (A), “very acceptable” (VA), and “extremely acceptable” (EA). These classes are fuzzy number even when the measurements are crispy. Each fuzzy number has a membership function that is limited and continuous and in this case we have choose a triangular shape, represented by triangular fuzzy number A with membership function μA (x) is defined on R. ⎧ x−a1 if a1 ≤ x ≤ aM ⎪ ⎨ aM −a1 x−a2 if aM ≤ x ≤ a2 (4) μA (x) = aM −a2 ⎪ ⎩ 0 otherwise,
After this stage, the system is set up, ready to support customer to rank a set of Web services that satisfy the requirements of consumers. D. Specifying requirements In order to support customer to find an appropriated set of Web service candidates that satisfy their requirements, we propose a manual subprocess that must be performed in order to get a set of requirements in a common language. First, the customer specifies the functional requirement that need to satisfy. Then, for this particular FR, he/she specifies a set of NFRs that the solution must address. Using this initial subset of NFRs, he/she must refines them until he/she obtains a prioritized set of required QoS aspects. For each aspect that he/she need to address, he/she specifies the minimum acceptable class that the aspect must satisfy (e.g. response time should be at least “acceptable”, as well the relative importance with respect to other aspects. This subprocess is performed with the help of the stakeholders. Figure 5, we exemplifying a weather forecast FR, where customer was concern with the performance of the Web service because he/she needs to show the forecast of weather for the next three days almost at real time. Using the modified (or fuzzy) utility tree, he/she refines the performance NFR into latency QoS aspect and others (that we do not consider in this example for simplicity). This is a step toward refining NFRs to be concrete enough for prioritization. Then, classically, the customer with the stakeholders, specifies a concrete value range in order to make the aspect quantifiable and verifiable. But, as we mentioned before as part of the motivation of this work, set crispy number is an expensive task because the customer and stakeholders need to be aware of what is the market offering. In the example showed in the Figure 5, they what really need is to show the forecast almost at real time, probably because their competition, but they are forced to set a value, that could be far away of what they need. Maybe, a latency of at most 200 ms, is impossible in this market and actually there are not candidates based on this restriction, or maybe all the Web services have a latency at most 200 ms, indeed they actually have a latency lower than 10 ms. Therefore, we propose to modify the utility tree by a fuzzy utility tree, where the customer and stakeholders concretize
where [a1 , a2 ] is the supporting interval and the point (aM , 1) is the peak. We have two types of quality aspects, those that we want to minimize and those that we want to maximize. Therefore, for different aspects we will have individuals that have a great belonging grade to the EA with a lower value for the metric measurement against those that will be completely opposite, where the individual with greater values are classified into that class. For instance, this happens when we are comparing response time against the reliability quality aspect. As Figure 4 shows, for each Web service functional cluster and for each QoS aspect we apply the modified fuzzy cmeans clustering to organize the Web service around of the five QoS classes mentioned before, obtaining the center of each class as well their supporting interval based on the crispy measurements obtained by the QoS crawler. The advantage to use Fuzzy logic is that each QoS measurement is classified in at least one class with a belonging degree. For instance, a specific weather Web service could be classified into the EA class with a belonging degree of 1 as well it could be classified into the VA class with a belonging degree of 0.8.
68
Now, the customer is ready to ask to the system for a ranked Web service candidates for his/her query. He/she specifies the functional requirement in terms of what he/she thinks best describe what he/she really wants. Then, he/she specifies the set of QoS that constraint that FR in terms of classes and prioritization labels. Then, the system first treats this functional query as a virtual WSDL, meaning that we apply the steps of the functional clustering subprocess but modified. To this virtual WSDL, we extract it the tokens, we steaming the tokens, filter stop words and then we extract a TF/IDF vector that represent that virtual WSDL file. Then, using the cosine similarity distance we calculate the distance between this vector and the representing vector of each cluster. Then, all the Web services that belong to that cluster are potential candidates to be the Web service that the user is looking for. So, we first filter all those candidates that do not meet any QoS constraint. Then, we re-rank our new Web service dataset. Then, the potential Web services are evaluated according to the additive weighting, that basically calculates the score of an alternative as the weighted sum of its cardinal preference rating, that is composed of the satisfaction degree to the required class (or the sum of all the satisfaction degree to the particular requested classes and the superior ones that the particular Web service belongs) multiply it by the weight that is actually the importance that the decision-maker gives to this criteria, i.e. equation (1). The resulting score is the degree in which this particular candidate belongs to the “high” rating class. The decision-maker could filter candidates that not satisfy a specified threshold.
their restriction as fuzzy classes. For our example, they specify a required latency as EA without worry about the numbers behind. Regarding the prioritization of the aspects, we reuse the ideas of the original utility tree using relative rankings: High(H), Medium(M) and Low (L). The prioritization considers the importance of each QoS aspect to the success of the FR satisfaction, and the degree of perceived risk posed by the achievement of this QoS aspect. In our example, our customer assigned priorities of (H,M), meaning that it is highly important to the FR satisfaction and the achievement of this is perceived to be of medium risk. In our case, we do not consider the perceived risk, instead we only consider the importance. The importance of to use this fuzzy utility tree as a manual process is that allows to customer to refine the FR and its NFRs into QoS aspect in terms of words, and therefore, to exploit their options to get good quality candidates that best tradeoff their quality constraints. E. From uncertainty to Web service ranking In this subsection, we explain how the system works to achieve the requirements of the customers. It is important to carefully read this section, because, bring together all the parts already explained by separate. Based on the assumption that the system is already tuned (the cluster are already organized) a customer is searching a Web service for a specific FR with a set of quality constraints (NFRs). The customer and stakeholders, using the fuzzy utility tree, refines the NFRs into QoS aspects as a triplet < aspect, minimum class, prioritization > where the aspect could be one of the follows • response time: the round time of sending a request and receiving a response; • availability: the number of successful invocations over the total number of invocations; • throughput: the total number of invocations over a period of time; • successability: number of response messages over the total number of request messages; • reliability: the number of error messages over the total number of messages; • compliance: level of satisfaction of the WSDL specification; • best practices: level of satisfaction of the WS-I Basic Profile; • latency: time to process a given request; • documentation the minimum class could be one of the follows [P A, AA, A, V A, EA] and the prioritization could be [H, M, L]. Regarding the prioritization, these labels are transformed into a crisp numbers. Basically, we assign to H 3 points, to M 2 points and to L 1 point. Then, we sum all the punctuations and we divide the prioritization punctuation of each QoS aspect by this number. Therefore, the prioritization is a number between 0 and 1, and the sum of all the prioritization is equals to 1.
IV. I MPLEMENTATION AND DATASET As a proof of concept, we implemented a prototype of the proposed framework. We have used an Agent-oriented paradigm to model consumers and providers as software agents, where the consumers are agents which goals are to achieve the consumer requirements and the providers are agents which goals are to provide their services (be discovered if they match the requirements). We implement this prototype in Netlogo 4.1 2 . The prototype read each “X” time from a file the clustered Web services that are functionally arranged around functional clusters for each QoS aspect. The file is produced by an implemented module over Matlab. We implement in this module the variant of the fuzzy c-means algorithm. In order to emulate the Market changes, we have divided the dataset in four: an initial subset of 70% of the data and three subsets of 10% each one that are the read dataset of each epoch. We are currently using a recently published QWS Dataset 3 presented in [3], that it is composed of 2507 real Web service implementations, where for each one, the quality characteristics were measured using a benchmarking tool. Originally, they have not yet published their functional classification as well they do not provide price information. To functional cluster the Web services we have used the SOMLib 2 http://ccl.northwestern.edu/netlogo 3 http://www.uoguelph.ca/∼qmahmoud/qws
69
Digital Library Project 4 and to fully illustrate this framework we just generate a random price for each Web service between US$0 and US$5000.
Price 2 0
Response Time
V. C ASE OF S TUDY
0.5 0
1000 2000 3000 4000
1
1000 2000 3000 4000
1
2
µ(x)
µ(x)
3
The customer is searching a Web service in order to obtain the weather prediction for a specific location for the next three days. Because this service will be used for his/her own customers that will be the base for them to decide if traveling or not the weekend, the service must be extremely reliable and with fast response time rate. Besides, it must have an acceptable price. The customer with its stakeholders prioritizes these QoS aspects using the fuzzy utility tree and the results are • < response time, EA, H > • < reliability, EA, H > • < price, A, M > Then, the relative importance for each QoS criteria are 0.375 for response time, 0.375 for reliability and 0.25 for the price. Regarding the kind of QoS, the response time and price of Web services are properties that while smaller are their values more desirable are. Instead of the reliability that much is better. First, we compare the results obtained by set up the Fuzzy classes ranges using an experts consensus method against a Fuzzy c-means clustering technique. Experts based on a study of the current market determine what are the best and worst range values of each QoS aspect. Based on that information they use an equidistant approach dividing the values range in the five intervals (one for each class). In Figure 6 we can appreciate the histogram for the weather Web services in different quality dimensions, the linguistic classes for each one, using an equidistant approach (experts technique) and the variant of the fuzzy c-means. Observing the ranges for the response time aspect, we can appreciate that in the classes “almost acceptable” and “poorly acceptable” there is a big difference. For instance using the equidistant approach, we would classify a Web service with response time of 1000 ms we would classify it at least as a an “almost acceptable” class. Instead, using the fuzzy c-means we would determine that Web service with response time greater than 500 ms would be unacceptable (poorly acceptable). Even, when the experts could be supported by better mechanisms that allow them to avoid these problem, they would still have the problem that this is an expensive task that should be performed manually every “X” time. This first experiment was run using only the initial subset of 70% of the data finding the fuzzy number parameters of each class as is shown in table I. Figure 7 show the results obtained for the query of the customer. As we can appreciate from the 13 potential and functional-equivalent weather Web services only 8 of them are actually QoS-equivalent and they need to be reviewed. Notice that some Web services are yellow painted, that means that even when they also were acceptable for the user, their 4 http://www.ifs.tuwien.ac.at/
0.5 0
1000 2000 3000 4000
1
µ(x)
1
µ(x)
4
0.5
0.5
1 0
0
500 1000 1500 2000 2500
Availability
0
500 1000150020002500
1
500 1000150020002500
1
0
50
60
70
80
0.5 0
90
Throughput
µ(x)
µ(x)
5 0.5 0
50 60 70 80 90
1
50 60 70 80 90
1
1 0
5
10
15
µ(x)
µ(x)
2 0.5 0
5
10
15
0.5 0
5
10
15
Fig. 6: Fuzzy numbers for some of the QoS
Fig. 7: Result of experiment
membership degrees were too low, lower that 0.5, so they are not considered as part of the final solution. We could rank these alternatives according to the grade of membership, but we prefer to leave this decision to the customer. In table II some of the candidates are shown. The first column indicates the Web service provider, the second column indicates the membership degree (for instance in the case of cweather, has a 0.95 of membership degree to the class “high” defined by the rule that the customer specifies). The third, fourth, and fifth column indicates one the value for the quality concern and between the parenthesis is the TABLE I: Fuzzy numbers parameter for each linguistic class Concern Class EA VA A AA PA
a1 289 289 975 2085 3644
Price aM 289 975 2085 3644 4677
a2 975 2085 3644 4677 4677
Response Time a1 aM a2 49 49 262 49 262 558 262 558 793 558 793 2629 793 2629 2629
a1 73 73 70 67 67
Reliability aM a2 78 78 73 78 73 73 70 73 70 70
TABLE II: Example of some of the candidates provider DOTSFastWeather ndfdXML cweather
andi/somlib/
70
md 0.67 0.54 0.95
price 3691.03 (0) 881.33 (1) 2223.5 (0.91)
response time 103 (0.75) 396 (0) 49.43 (1)
reliability 73 (0.94) 67 (0.86) 73 (0.93)
R EFERENCES
membership degree to the specific class that the customer specifies for each quality concern (for instance “extremely acceptable” for the response time concern). Notice that some of the potential alternative could have the same name (but totally different endpoint, and therefore probably are totally different Web services).
[1] C. P. Ayala and X. Franch, “A goal-oriented strategy for supporting commercial off-the-shelf components selection,” in ICSR, ser. Lecture Notes in Computer Science, M. Morisio, Ed., vol. 4039. Springer, 2006, pp. 1–15. [2] N. Maiden and C. Ncube, “Acquiring COTS software selection requirements,” IEEE Software, 1998. [3] E. Al-Masri and Q. Mahmoud, “WSB: a broker-centric framework for quality-driven web service discovery,” Software: Practice and Experience, vol. 40, no. 10, pp. 917–941, 2010. [4] S. Ran, “A model for web services discovery with QoS,” SIGecom Exchanges, vol. 4, pp. 1–10, 2003. [5] Z. Zheng, Y. Zhang, and M. Lyu, “Distributed QoS evaluation for realworld web services,” in ICWS. IEEE Computer Society, 2010, pp. 83–90. [6] J. Yen and W. Tiao, “A systematic tradeoff analysis for conflicting imprecise requirements,” in RE. IEEE Computer Society, 1997, pp. 87–96. [7] V. X. Tran and H. Tsuji, “QoS based ranking for web services: Fuzzy approaches,” in Proceedings of the 2008 4th International Conference on Next Generation Web Services Practices. IEEE Computer Society, 2008, pp. 77–82. [8] M. Chen, G. Tzeng, and C. Ding, “Fuzzy MCDM approach to select service provider,” in Proceeding of the 12th IEEE International Conference on Fuzzy Systems (FUZZ ’03), vol. 1. IEEE Press., 2003, pp. 572–577. [9] P. Xiong and Y. Fan, “QoS-aware web service selection by a synthetic weight,” in FSKD (3), J. Lei, Ed. IEEE Computer Society, 2007, pp. 632–637. [10] P. Wang, K. Chao, C. Lo, C. Huang, and Y. Li, “A fuzzy model for selection of QoS-aware web services,” in ICEBE. IEEE Computer Society, 2006, pp. 585–593. [11] S. Agarwal and S. Lamparter, “User preference based automated selection of web service compositions,” in ICSOC Workshop on Dynamic Web Processes. IBM, 2005, pp. 1–12. [12] M. D. Cock, S. Chung, and O. Hafeez, “Selection of web services with imprecise QoS constraints,” in 2007 IEEE / WIC / ACM International Conference on Web Intelligence, WI 2007, 2-5 November 2007, Silicon Valley, CA, USA, Main Conference Proceedings, 2007, pp. 535–541. [13] H. Wang, C. Lee, and T. Ho, “Combining subjective and objective QoS factors for personalized web service selection,” Expert Systems with Applications, vol. 32, no. 2, pp. 571–584, 2007. [14] L. Zhuang, G. Heqing, L. Dong, Y. Han, and Z. Juan, “Solving multiobjective and fuzzy multi-attributive integrated technique for QoS-aware web service selection,” in Proceedings of the International Conference on Wireless Communications, Networking and Mobile Computing, 2007, pp. 735–739. [15] F. Li, Y. He, W. Hu, L. Wu, and P. Wen, “Web service selection based on fuzzy QoS attributes,” Journal of Computational Information Systems, vol. 7, no. 1, pp. 198–205, 2011. [16] L. Zadeh, “Fuzzy sets,” Information and Control, vol. 8, no. 3, pp. 338– 353, 1965. [17] M. Lin, J. Xie, H. Guo, and H. Wang, “Solving QoS-driven web service dynamic composition as fuzzy constraint satisfaction,” in 2005 IEEE International Conference on e-Technology, e-Commerce, and e-Services (EEE 2005), 29 March - 1 April 2005, Hong Kong, China, 2005, pp. 9–14. [18] N. Pal, K. Pal, J. Keller, and J. Bezdek, “A possibilistic fuzzy c-means clustering algorithm,” IEEE Transactions on Fuzzy Systems, vol. 13, no. 4, pp. 517–530, 2005. [19] T. Liao, A. Celmins, and R. H. II, “A fuzzy c-means variant for the generation of fuzzy term sets,” Fuzzy Sets and Systems, vol. 135, no. 2, pp. 241–257, 2003. [20] R. Kazman, M. Klein, and P. Clements, “ATAM: A method for architecture evaluation,” Software Engineering Institute, Carnegie Mellon University, Tech. Rep., 2000. [21] M. Dittenbach, A. Rauber, and D. Merkl, “Recent advances with the growing hierarchical self-organizing map,” in 3rd Workshop on SelfOrganizing Maps, ser. Advances in Self-Organizing Maps. Springer, N. Allison, H. Yin, L. Allison, and J. Slack, Eds., June 2001, pp. 140– 145.
A. Final Discussion Time after time, we need to train the model again with (in this case) the additional 10% of the data. Because the market changes over time, we expect to have new providers as well the lost of others. But, more importantly, regarding the QoS aspects, we would expect that the providers improve their quality levels because the new available technology and market competition. We propose a Market-aware framework, that satisfy the customer needs according to the current offering of the providers. But, a Web service that was classified in one aspect as“extremely acceptable” in the past, if it does not update itself with the market, then the service will start to age. Therefore, because the market changes, its Web service classification changes to other not so appreciated classes are “very acceptable” or lower. So, the question is, what happens with those clients that decide for one provider and now because the market is moving it is not the right option anymore. In this version of the framework, we do not have implemented the option of subscribe an application to the framework in order to indicate to it, if a current used Web service have dropped its QoS level and therefore it needs to be replaced by one of a suggested candidate Web service list but it is part of our ongoing work. VI. C ONCLUSIONS AND F URTHER W ORKS The major contribution of this paper is that by using this framework customers and providers connect imprecisely defined QoS requirements with overly precise service QoS offerings even over the time. Enables decision-makers to specify the required quality with words in a common language that providers also share. We provide an end to end solution that support customer to refine his/her requirements as well as to support providers to self organize themselves around functional and QoS classes. This approach give a more precise classification than the same providers would do from the opinions of the consumers. Besides, we propose a Market-aware framework that will allow in the future, register the agreements between consumers and providers and then monitoring changes on the QoS agreements in order to aware consumers if it is broken. ACKNOWLEDGMENT This work was partially funded by FONDEF (grant D08i1155), UTFSM DGIP (grant DGIP 241167 and PIIC), CCTVal ( FB/20SO/10 and Basal FB0821), and DIPUV 37/2008.
71