当前位置:首页 >> 互联网 >>

Requirements for QoS-Based Web Service Description and Discovery


320

IEEE TRANSACTIONS ON SERVICES COMPUTING,

VOL. 2,

NO. 4,

OCTOBER-DECEMBER 2009

Requirements for QoS-Based Web Service Description and Discovery
Kyriakos Kritikos and Dimitris Plexousakis, Member, IEEE
Abstract—The goal of Service Oriented Architectures (SOAs) is to enable the creation of business applications through the automatic discovery and composition of independently developed and deployed (Web) services. Automatic discovery of Web Services (WSs) can be achieved by incorporating semantics into a richer WS description model (WSDM) and by the use of Semantic Web (SW) technologies in the WS matchmaking and selection (i.e., discovery) process. A sufficiently rich WSDM should encompass not only functional but also nonfunctional aspects like Quality of Service (QoS). QoS is a set of performance and domain-dependent attributes that has a substantial impact on WS requesters’ expectations. Thus, it can be used for distinguishing between many functionally equivalent WSs that are available nowadays. This paper starts by defining QoS in the context of WSs. Its main contribution is the analysis of the requirements for a semantically rich QoS-based WSDM and an accurate, effective QoS-based WS Discovery (WSDi) process. In addition, a road map of extending current WS standard technologies for realizing semantic, functional, and QoS-based WSDi, respecting the above requirements, is presented. Index Terms—Web-based services, web services, service discovery, service matchmaking, service selection, quality of service, QoS modeling, constraint programming, requirements engineering.

?
1 INTRODUCTION
EB

W

Services (WSs) are modular, self-describing, and loosely coupled software applications that can be advertised, located, and used across the Internet using a set of standards such as SOAP, WSDL, and UDDI. They can be dynamically discovered and integrated at runtime in order to develop and deploy business applications. However, the standard WS techniques (such as WSDL and UDDI) fail to realize dynamic WSDi, as they rely on syntactic and static descriptions of service interfaces and other nonfunctional service attributes for publishing and finding WSs. As a result, the corresponding WSDi mechanisms return results with low precision and recall. In addition, no means are provided in order to select among multiple functionally equivalent WSs. The key to automation of WSDi is the incorporation of semantics into a richer WSDM. Ontologies [1] should be used in order to provide formal meaning to every term of the WSDM and in order to utilize the reasoning mechanisms of the SW. Reasoning can provide discovery results with higher precision and recall, thus leading to automation. Concerning functional WSDi, prototypes either adopting a pure ontology-based solution [2] or combining Information Retrieval (IR) techniques with reasoning [3] have already been implemented with quite promising results. Unfortunately, functional discovery of WSs is

. The authors are with the Computer Science Department, University of Crete, PO Box 2208, GR-714 09, Heraklion, Crete, Greece, and the Foundation of Research and Technology—Hellas (FORTH), Institute of Computer Science (ICS), N. Plastira 100, Vassilika Vouton, GR-700 13, Heraklion, Crete, Greece. E-mail: {kritikos, dp}@csd.uoc.gr, {kritikos, dp}@ics.forth.gr. Manuscript received 18 Jan. 2009; revised 16 July 2009; accepted 10 Aug. 2009; published online 4 Sept. 2009. For information on obtaining reprints of this article, please send e-mail to: tsc@computer.org, and reference IEEECS Log Number TSCSI-2009-01-0014. Digital Object Identifier no. 10.1109/TSC.2009.26.
1939-1374/09/$25.00 ? 2009 IEEE

inadequate, as there may be numerous functionally equivalent WSs. Users must be further assisted in selecting the appropriate WS for their needs. The solution to the last problem is QoS-based WS Description and Discovery (WSDD). QoS for WSs is a set of nonfunctional properties that encompass performance characteristics among others. As users are very concerned about the performance of WSs they use, QoS can be used for discriminating between functionally equivalent WSs. Thus, the proposed solution comprises 1) description of the QoS aspect of WSs (i.e., QoS-based WS description), 2) filtering of WS functional results based on user constraints on their QoS descriptions (i.e., QoS-based WS matchmaking), 3) sorting the results based on user-provided weights on QoS attributes/metrics (i.e., WS selection). While a lot of research has dealt with the semantic, functional WS description, little has been done for the nonfunctional part. Most of the research is concentrated on syntactic nonfunctional WS descriptions [4], [5], [6], [7], [8], [9], [10], [11]. Additionally, the semantic research efforts lack a rich QoS-based WSDM [12], [13], [14] that describes QoS aspects in all detail. The purpose of this paper is to analyze all requirements for a rich, semantic, and extensible QoS-based WSDM. There are two main approaches for QoS-based WS matchmaking: 1) ontology-based [12], [13], [14], and 2) Constraint Programming (CP) [15], [16] based [11], [17]. The former suffer from performance problems due to the use of immature ontology reasoners. The latter are fast but the results reported in the relevant research works suffer from accuracy problems due to the use of syntactic descriptions, while they do not provide advanced categorization of results. In addition, neither approach provides useful matchmaking results for overconstrained QoS demands. In this paper, we explain and analyze all the requirements that are needed for an accurate, effective, and
Published by the IEEE Computer Society

KRITIKOS AND PLEXOUSAKIS: REQUIREMENTS FOR QOS-BASED WEB SERVICE DESCRIPTION AND DISCOVERY

321

user-assisting QoS-based WS matchmaking process. Moreover, the requirements for the (QoS-based) WS selection process are unveiled. Last but not least, a road map is supplied providing guidelines on how to extend the standard WS mechanisms in order to incorporate and use the semantic QoS-based WSDMs and discovery tools that have already been developed. The ultimate goal is to provide a complete semantic framework for automating the QoS-based WSDi that could be used individually or as a complementary component of a functional WS registry. The rest of this paper is organized as follows: Section 1 defines QoS for WSs and the role that it plays in WS management. Section 2 analyzes all necessary requirements for a rich and semantic QoS-based WS description model. Section 3 analyzes the requirements for the QoS-based WSDi. Section 4 provides a plan on how to extend the current WS registries with semantically enhanced QoSbased WSDD capabilities. Finally, Section 5 summarizes the paper and draws directions for further research.

2

QoS

As QoS is the dominant concept used throughout this paper, this chapter provides a comprehensive analysis of the conceptualization of QoS for WSs. It also reveals the main domain-independent QoS attributes that are appropriate for the description of WSs. In addition, some domaindependent QoS attributes are also shortly analyzed taken from the application domain of Vehicle Traffic Monitoring. Finally, the role that QoS can play in the management of WSs is elaborated.

2.1 QoS Definition The international quality standard ISO 8402 (part of ISO 9000 [18]) describes quality as “the totality of features and characteristics of a product or service that bear on its ability to satisfy stated or implied needs.” According to [19], what defines quality is vague, and different views exist in different studies and from different perspectives. The following views are common:
Quality as functionality. Quality is considered as the amount of functionality that a service can offer to its users. For example, if SP1 allows you to rent a car besides booking flights and hotel rooms, and if this functionality is not provided by SP2 or SP3, then SP1 is offering a better quality than SP2 and SP3. 2. Quality as conformance. Quality means meeting specifications. For example, if SP1 has specified that his WS will be available 0.9999 of the time and this was true, then SP1 is considered as offering good quality of service. 3. Quality as reputation. Quality depends on users’ experience and expectation from a WS and its value is built collectively over the time of the service’s existence from users’ feedback [4]. For example, if WSs have consistently provided specific functionality with specific performance levels at all time of their operation, then they provide good quality of service. These different views of quality require QoS to be monitored and measured differently. Quality as functionality characterizes the design of a service and can only be 1.

measured by comparing the service against other services offering similar functionalities. Quality as conformance, on the other hand, can be monitored for each service individually, and usually requires the user’s experience of the service in order to measure the “promise” against the “delivery.” Finally, reputation can be regarded as a reference to a service’s consistency over time in offering both functionality and conformance qualities, and can therefore be measured through the other two types of quality over time. While it is possible to establish all three types of quality for a service in an SOC environment, it is perhaps most interesting and relevant to understand how quality as conformance may be monitored and measured. The reasons for this are the following: First, the first type of quality is already established in the SOC environment with the use of the WSDL and UDDI standards, although nobody reassures that the functionality exposed by a service is the same as the one advertised by the service provider. Second, the reputation of a service is just an indicator of the overall QoS of the service over time that depends on user expectations and other imponderable factors (advertisement, financial and political interests, etc.). So, reputation can only be considered as a QoS property that can be measured and computed by monitoring and other authorities. Another aspect which is usually neglected is that QoS must be seen in a broader end-to-end sense as it affects the end-to-end quality received by the WS client when invoking a particular WS. Thus, QoS characterizes any entity used in the path from the user to the WS, including the WS’s host and intervening network. Therefore, the QoS characteristics of all these entities constitute the QoS of a WS. Thus, based on the above definition and aspects, we consider QoS of a WS as a set of nonfunctional attributes of the entities used in the path from the WS to the client that bear on the WS’s ability to satisfy stated or implied needs in an end-to-end fashion. The values of QoS attributes can vary without impacting the core function of the WS which remains constant most of the time during the WS lifetime. If a WS is advertised to have certain values (or range of values) in these QoS attributes, then we say that the WS conforms to a certain QoS level. In general, each particular application domain that a service belongs to will have its own set of QoS attributes that apply to all services of the domain [4], [7], [20]. However, certain attributes will be domain-independent attributes [7], [9], [21], [22], [23], [24]. For example, a Vehicle Traffic Monitoring WS will involve QoS attributes belonging to the vehicle traffic monitoring application domain [25] like “coverage,” while attributes such as “price” and “availability” are domain independent and can be used for characterizing WS of any application domain. QoS attributes can be distinguished into measurable and unmeasurable ones. A measurable QoS attribute can be measured with the use of one or more QoS metrics. A QoS metric [6], [26] is a concept that encompasses all measurement details for a QoS attribute. QoS metrics have specific value types, while their values are associated to a specific unit. Moreover, QoS metrics are distinguished between resource and composite ones. Resource metrics are computed directly from the instrumentation of the service’s management system (e.g., service uptime), while composite ones are derived from other metrics with the help of mathematical

322

IEEE TRANSACTIONS ON SERVICES COMPUTING,

VOL. 2,

NO. 4,

OCTOBER-DECEMBER 2009

formulas (e.g., service availability is computed by dividing uptime with the total measurement time). For example, the execution time QoS attribute of a WS can be measured by the average execution time metric. This metric has as value type the range of integers [1, 10], while its values are associated to the unit of “second.” It is a composite metric whose values are computed by taking the average of all execution times (i.e., average of all values of a resource metric) of the considered WS during a specific time period. Unmeasurable quality attributes cannot be measured at all. They represent static information which is qualitative in nature. These attributes have a specific value type and are unit-less. However, they can have an ordering function that provides a partial ordering between the values they take. For instance, the robustness/flexibility QoS attribute can have the following value type finflexible; flexible; very flexibleg which can be mapped to the set f0; 1; 2g with the use of a specific ordering function. Each value of this attribute denotes the degree to which a specific service functions correctly in the presence of invalid, incomplete, or conflicting inputs. For example, the very flexible value denotes that the service will function correctly whatever input it will get, by resolving the incompleteness and ambiguity of the input or discarding it if it is completely invalid. This value is mapped to the highest integer value. Once a set of attributes has been established for all domains a WS belongs to, it must be ensured that QoS information is collected in a fair manner by the values sent from providers, third parties, or requester’s feedback based on the characteristic of the quality attribute. For example, “price” can be provided by service providers, “response time” can be computed by third-party active monitoring of a WS, and “reputation” [4] is derived from service requesters’ feedback. Based on this value collection of QoS attributes, a WS violates a certain QoS level if it has promised a “better” (under a domain-specific definition of “better”) value from the one it actually delivers to the requester. As it can be seen from the above analysis of QoS, a QoS specification (i.e., a QoS offering or QoS demand) of a WS is a usually conjunctive set of linear and possibly nonlinear constraints on some variables representing QoS metrics or unmeasurable QoS attributes that restrict them to have either certain values (for unary constraints) or certain combinations of values (for n-ary constraints). For example, a QoS offer would contain the following linear constraints et 5 ^ flex ? very flexible, where et corresponds to the average execution time QoS metric and flex corresponds to the robustness/flexibility unmeasurable QoS attribute. It must be noted that the above definition is broad enough to cover specifications expressed in different (XML or ontology based) languages (e.g., WSOL [10] and OWL-Q [27]) and constraint-based QoS specifications expressed via constraint models (e.g., QRL [8]). Moreover, while usually only unary linear constraints constitute the QoS specifications, the existence of n-ary linear and nonlinear constraints is possible [28] in cases where dependencies between QoS attributes or nonlinear cost models [29], expressing the price of the WS with respect to its offered service levels, are defined.

different areas such as network research [30], [31], [32] and in real-time issues [33]. There is some effort in defining QoS in distributed systems. The focus is primarily on how to express the QoS for a system, and how these requirements are propagated to the resource manager to fulfill the QoS requirements [34]. Hamada et al. [35] present a layered model for representing QoS for telecommunication applications. They present service quality function, QoS schema mapping, and price-QoS trade-off. Fr?lund and Koistinen [21] present a QoS specification language for designing distributed object systems, in conjunction with the functional design. Sabata et al. [36] categorize the QoS from different viewpoints: application, system, and resource. They specify QoS in terms of metrics and policy. All the above research efforts categorize and define QoS from their perspective with some overlap between them. There is no consensus about a set of QoS important to distributed systems. There is even less research done on the QoS for SOA. However, some QoS attributes have been found that are common in most of the aforementioned areas and are directly applicable to WSs. These are general, crossdomain, QoS attributes and are analyzed in Section 2.2.1. Of course, there will be certain domain-dependent QoS attributes that will be characteristic of the application domain(s) of the WS. For example, QoS attributes regarding information quality will be important for a data warehouse WS [37]. Or, a service such as a car rental service will involve attributes belonging to multiple domains, such as the travel and retail domains. Attributes such as price belong to both domains, but an attribute such as “flexibility of reservation changes” has a specific meaning in the travel domain. However, determining the attributes that apply to a particular domain is nontrivial and needs to be decided by the community of users and providers as they settle upon ways to distinguish and evaluate different offerings. For this reason, we are not going to enumerate and explain the meaning of all possible QoS domain-dependent attributes that characterize all possible application domains. On the contrary, in Section 2.2.2, we are only going to enumerate the most important domain-dependent QoS attributes that are required to be specified for only one application domain.

2.2 QoS Attributes Categorization Quality of Service research has been an active research area for several IT domains. The term “quality of service” has been used for expressing nonfunctional requirements for

2.2.1 Domain-Independent QoS Attributes There are many QoS aspects important to WSs. We are going to organize them into QoS categories. For each category, we justify why we have included it, explain its purpose, and describe some of its representative attributes. Our categorization is based on the works of [7], [21], [22], [23], [24], [36], [38], [39], [40], [41]. Performance. This category contains quality attributes that characterize how well a service performs. Two quality attributes with a very well-defined meaning are common among all approaches: response time and throughput. Response time is the overall time required to complete a service request. It is regarded as a composite quality attribute computed from latency and network delay. Latency is the time between the request arrival and its servicing. Similarly, latency is composite and is computed from execution time and queue delay time. Execution time is the time taken by a WS to process its sequence of activities, while queue delay time is the wait time for a service request before it is actually executed. Another quality attribute that has similar meaning with execution time is transaction time but is used in the context of

KRITIKOS AND PLEXOUSAKIS: REQUIREMENTS FOR QOS-BASED WEB SERVICE DESCRIPTION AND DISCOVERY

323

transactional services. Throughput is the number of completed service requests over a time period. Dependability. Dependability of a computing system is the ability to deliver service that can justifiably be trusted [38]. In [38], the phrase “justifiably trusted” is translated into three different quality attributes and views: availability, reliability, and security. In our opinion, security is orthogonal to dependability and must be put into a separate category because it provides the mechanisms that can prevent a specific type of failures from happening but it has nothing to do with the way the service has been designed and built. Moreover, security mechanisms can be broken so even these faults cannot be prevented. Thus, based on the above argumentation, dependability contains availability, reliability, failure semantics [42], and robustness [7], [40], [41] with the latter two attributes describing: 1) the type of faults that can be exposed and how the service reacts to them (the former) and 2) the capability of the service to behave in an acceptable way when these faults happen (the latter). Another important remark is that besides availability, another quality attribute with similar meaning that should be added in this group is accessibility [39] as it can characterize the case where a service is available but not accessible to some users, e.g., due to network connection problems. Finally, three additional QoS attributes belong to this category, namely, scalability, capacity, and continuous availability. A concise description is given below: . Availability—It is the probability that the system is up. It is related to reliability. It can be measured as [43] A? hupT imei hupT imei ? ; htotalT imei ?hupT imei ? hdownT imei?

Fig. 1. Types of failure of a service.

.

.

.

where hupT imei is the total time the system has been up during the measurement period, hdownT imei is the total time the system has been down during the measurement period, and htotalT imei is the total measurement time (sum of hupT imei and hdownT imei?. Continuous availability—It assesses the probability with which a client can access a service an infinite number of times during a particular time period. The service is expected not to fail and to retain all state information during this time period. Continuous availability is different from availability in that it requires subsequent use of a service to succeed but only for a limited time period. Reliability—The ability of a service to perform its required functions under stated conditions for a specified period of time. It is the overall measure of a WS to maintain its service quality. Reliability is also related to the assured and ordered delivery of messages transmitted and received by service requestors and providers. It is usually measured by MTBF which is the “mean time between failure” metric. Failure semantics—It describes the general capabilities of a service to handle failures. In particular, it describes the circumstances of service failures and how a service reacts to failures. We consider this as a composite QoS attribute that consists of the following atomic QoS attributes:

Failure masking—It is used to describe what kind of failures a service may expose to its clients. A client must be able to detect and handle any kind of exposed failure. The types of failure than can be exposed are the following: failure, omission, response, value, state, timing, late, and early (Fig. 1). The QoS specification for a particular WS will list the subset of failures exposed by that service. If a service exposes omission failures, clients must be prepared to handle a situation where the service simply omits to respond to requests. If a service exposes response failures, it might respond with a faulty return value or an incorrect state transition. Finally, if the service exposes timing failures, it may respond in an untimely manner. Timing failures have two subtypes: late and early timing errors. Operation semantics—This semantics describes how requests are handled in the case of failure. We can specify that issued requests are executed exactlyOnce, atLeastOnce, and atMostOnce. Exception handling—Since it is not possible for the service designer to specify all the possible outcomes and alternatives, exceptions can be expected. Exception handling is how the service handles these exceptions. It can be in a brutal or a graceful way. For example, if a database (DB) is down, a service might swap to another database. Compensation—Actions that are needed to undo the effects of a service invocation when using stateful services. For example, if a user orders by mistake a different good from a catalogue, then compensation includes to give the customer credit and cancel the order. . Robustness/flexibility—It is the degree to which a service can function correctly in the presence of invalid, incomplete, or conflicting inputs. . Scalability—The capability of increasing the computing capacity of service provider’s system and its ability to process more operations or transactions in a given period. . Capacity—Limit of concurrent requests which should be provided with guaranteed performance. Transaction support related QoS: integrity. Transactions can be grouped into a unit in order to guarantee the integrity of the data operated on by these transactions. The unit can be either successful, when all transactions in the unit “commit,” or unsuccessful, when all units “roll back” to their original state in case of a transaction failure. This is described by the ACID properties: Atomicity (executes entirely or not at all), consistency (maintains the integrity of the data), isolation (individual transactions run -

324

IEEE TRANSACTIONS ON SERVICES COMPUTING,

VOL. 2,

NO. 4,

OCTOBER-DECEMBER 2009

as if no other transactions are present), and durability (the results are persistent). A two-phase commit capability is the mechanism to guarantee the ACID properties for distributed transactions running over tightly coupled systems as if they were a single transaction. It is more difficult in the Web services environment [44], [45], as the transactions may involve more than one business partner with the possibility of transactions spanning over long time (hours or days)—Long Running Transactions (LRT). The transaction integrity is still described by ACID properties, although it is much harder to achieve in this case. It may require different mechanisms. Security. Services should be provided with the required security. With the increase in the use of services which are delivered over the public Internet, there is a growing concern about security. The service provider may apply different approaches and levels of providing security policy depending on the service requestor. Security for services [7], [24], [41] means providing authentication, authorization, confidentiality, traceability/auditability, accountability, data encryption, and nonrepudiation. Besides these classical quality attributes, we have additionally incorporated two, namely, safety and integrity [38]. A short description of these QoS attributes can be found below: . Authentication—The process of verifying that a potential partner in a conversation is capable of representing a person or organization. Authorization—The process of determining, by evaluating applicable access control information, whether a subject is allowed to have the specified types of access to a particular resource like a service. Usually, authorization is in the context of authentication. Once a subject is authenticated, it may be authorized to perform different types of access. Confidentiality—Absence of unauthorized disclosure of information. Integrity—Absence of improper system state alterations including accidental or malicious alternation or removal of information. Accountability—The state of being accountable; liability to be called on to render an account; the obligation to bear the consequences for failure to perform as expected. Traceability and auditability—Capability of the service to be monitored and to generate in a reliable and secure way events producing an audit trail from which a sequence of events can be reconstructed and examined. Security events could include authentication events, policy enforcement decisions, and others. The resulting audit trail may be used to detect attacks, confirm compliance with policy, deter abuse, etc. Data encryption—Refers to the algorithms adopted for protecting data from malicious accesses. As one algorithm may be better than another one, it also reflects the efficiency of the data encryption algorithms and mechanisms. Nonrepudation—Methods to prove to the data sender that data have been delivered, and to prove the sender’s identity to the recipient, so that neither the

sender nor the recipient can deny operations of sending and receiving data. . Safety—The absence of catastrophic consequences on the users and the environment. Configuration management. This group contains quality attributes that influence the way a service is configured to function (service level [36]) or characterize if the promised functional and quality level has been actually delivered during the service’s lifetime (completeness, stability, and reputation). The definitions of these QoS attributes are the following: . Service level—It is defined as the type of QoS commitment given to the application or user. Two types are usually utilized: guaranteed service or best effort service. Completeness—A measure of the difference between the specified set of features (e.g., functions) and the implemented set of features. Stability—A measure of the frequency of change related to the service in terms of its interface and/ or implementation. Reputation—The reputation qrep ?s? of a service S is a measure of its trustworthiness. It mainly depends on end user’s experiences from using the service S . Different end users may have different opinions on the same service. The value of the reputation is defined as the average ranking given to the service by end users, i.e., Pn Ri qrep ?s? ? i?1 ; n

.

.

.

.

. .

.

.

.

.

where Ri is the end user’s ranking on a service’s reputation and n is the number of times the service has been graded. Usually, end users are given a range to rank Web Services. For example, in Amazon.com, the range is [0, 5]. Alternatively, a ranking of an end user to a service can be a vector of values of some QoS attributes. From this vector, a QoS value can be obtained which is then averaged over all user rankings to get the overall reputation of the service. Network and infrastructure related. The network is usually used for sending requests and receiving (either instantaneously or continuously) the results back and connects the service with the requesting user. Initially, most of the research approaches [7], [22], [24], [36] were neglecting this quality aspect but after the work published in [9], this situation has changed [40], [41]. Network parameters influence the values of service quality parameters of other quality groups like response time and availability. We have identified four network quality parameters, that are common among all research approaches, namely, bandwidth, network delay, delay variation, and packet loss. Another entity that is different from the service or the user but it influences directly or indirectly service quality is the infrastructure. This entity characterizes the service execution environment and can be characterized by many quality attributes. For the time being, we have only identified three of them, namely, server failure, guaranteed messaging requirements, and security level. The definition of all of these QoS attributes follows:

KRITIKOS AND PLEXOUSAKIS: REQUIREMENTS FOR QOS-BASED WEB SERVICE DESCRIPTION AND DISCOVERY

325

Bandwidth—Average of all the bandwidth samples gathered by probing the network service during intervals of length T . . Network delay—The number of milliseconds spent in transit when a client and server exchange data. This includes the transit time for all packets required for a request-response transaction. . Delay variation—It is the variation in the interpacket arrival time (leading to gaps, known as jitter, between packets) as introduced by the variable transmission delay over the network. . Packet loss—Average of all packet loss samples gathered by probing the network service during intervals of length T . . Server failure—It describes the way in which a service can fail. That is, whether it will halt indefinitely, restart in a well-defined initialState, or restart rolledBack to a previous checkpoint. . Guaranteed messaging requirements—The ability of the service to ensure the order and persistence of the messages. . Security level—Specifies whether security is ensured at message or transport levels. Cost. Some approaches consider cost as a service attribute that is orthogonal to the service quality because it is related to both functional and nonfunctional service attributes. However, the majority of approaches [7], [39], [40], [41], [46] consider cost as a service quality attribute. In addition, all approaches, at least the ones we have studied, use cost at the service selection phase in order to select the best service according to its QoS and cost and user’s preferences and budget. Based on the above reasons, we regard cost as a (composite) quality attribute (and group) consisting of three (atomic) service attributes: cost model, fixed costs, and variable costs. Actually, cost can be computed either from all atomic cost attributes or only from the fixed costs attribute. The cost model defines a set of functions that transform resources (services) into costs, the fixed costs are costs that constitute a fixed amount of the overall costs for the provision of a service, while variable costs are costs that change during the provision of a service in addition to fixed costs. Other. This quality category has been created to contain various quality attributes of services that do not belong to any other category. So, the contained quality attributes may not be related to each other. For the time being, only one quality attribute has been considered called supported standards [7], [22], [24], [39], [40], [41] used to indicate if the service complies with standards or not. This attribute can affect the portability of the service and its interoperability with other services or applications. .

encryption and price are unmeasurable QoS attributes. Data encryption refers to the algorithms adopted for protecting data from malicious accesses, while price is the subscription or monetary cost for using the WS. On the other hand, reputation is a QoS attribute that is not advertised by WS providers but is computed by WS registries which take the average of WS executors feedback. However, it should be taken into account as WS requesters may provide constraints for it. Reliability is measured by the MTBF metric that measures for how long a WS can function in an errorfree manner. Availability is measured with the help of the upT ime and downT ime metrics based on the formula previously analyzed that gives a resource metric of availability. Of course, composite metrics computing the average, min, and max values of a resource metric can also be used. Execution time can be measured by a resource metric but—similarly to availability—it can also be measured by high-level statistical (i.e., composite) metrics. Domain-dependent QoS attributes strongly rely on the application domain of the WS advertised/queried. For the Vehicle Traffic Monitoring domain, eight QoS attributes are considered that characterize mainly the quality as well as other domain-dependent characteristics of the data processed and produced. These are covered area, routes set, detail level, accuracy, completeness, validity, timeliness, and coverage. The first three are static. The covered area attribute characterizes the extent of the area over which the WS is able to provide traffic information. Routes set is the set of route types that a WS supports. For instance, a WS may provide information only on national highways, while other WSs may also consider interstate or local routes. Similarly, the detail level of traffic information provided by a WS may also vary. A WS may provide information on accidents and traffic jams, while other WSs may also provide information about closed routes, detours, and predictions about conditions of local traffic. The next five QoS attributes are highly dynamic and many different metrics can be used for measuring them. Accuracy is the measure or degree of agreement between a data value or set of values and a source assumed to be correct. It is also defined as a qualitative assessment of freedom from error, with a high assessment corresponding to a small error. Accuracy can be measured using one of the following three error metrics: Mean Absolute Percent Error (MAPE), Signed Percent Error (SPE), and Root Mean Squared Error (RMSE). These three metrics are calculated based on the following three formulas: !   n  X Xi ? Xreference  1   ; ? MAP E ?%? ?  X  n reference i?1   1 SP E ?%? ? ? n
n X Xi ? Xreference i?1

2.2.2 Domain-Dependent QoS Attributes The application domain of Vehicle Traffic Monitoring [25] is examined in this paper. In this application domain, WSs provide up-to-date information about local and interstate traffic to business and retail customers across the US. The QoS of these WSs is characterized by two sets of attributes: domain dependent and domain independent. Domain-independent QoS attributes refer to technical aspects of service provisioning irrespective of the application domain used. For the sake of simplicity, we consider seven such QoS attributes: reliability, data encryption, refresh time, execution time, availability, reputation, and price. Data

! ;

Xreference

? v?????????????????????????????????????????????????????????????????? ! u  n ? X u 1 ? 2 ? RMSE ? t ; Xi ? Xreference n i?1 where Xi is the observed data value, Xreference is the reference (i.e., ground truth) value, and n is the total number of observed data values. RMSE can also be expressed as a percentage. These different error formulations are all valid

326

IEEE TRANSACTIONS ON SERVICES COMPUTING,

VOL. 2,

NO. 4,

OCTOBER-DECEMBER 2009

measures of accuracy but may reveal slightly different interpretations. MAPE and SPE are expressed as percentages; thus, these formulations may be used to compare the relative accuracy of different attributes (e.g., traffic volume count and speed measurement accuracy). Because the signed error does not use absolute error values (as MAPE does), the signed error formulation may reveal whether there is a consistent bias in measurements. RMSE is an error formulation that is commonly available in many statistical software applications. The correct source of data is typically referred to as ground truth, reference, or baseline measurements. Ground truth data can be collected in several different ways for each traffic data element. In many cases, ground truth data are collected from specialized equipment and reduced in a rigorous manner that minimizes error. The QoS attribute of completeness represents the degree to which data values are present in the attributes (e.g., volume and speed are attributes of traffic) that require them. Completeness is typically described in terms of percentages or number of data values. It can refer to both the temporal and spatial aspect of data quality, in the sense that it measures how much data are available compared to how much data should be available. It can be measured using a percentage metric computed from the following formula: P ercentComplete?%? ? navailableV alues ? 100; ntotalExpected

Compare multiple data elements (i.e., volume, occupancy, and speed) to check for consistency in traffic data values; . Compare traffic data to historical averages or trends from previous days, months, or years; . Compare traffic data to similar nearby locations (upstream or downstream) to check for continuity of traffic flow; . Compare traffic data in consecutive time periods to identify rapid fluctuations. Validity criteria are often based on “expert opinion” and are generally viewed as “rules of thumb,” although some validity criteria may be based on established theory (e.g., road capacity) or scientific facts (e.g., cannot record a zero volume and nonzero speed). The specific validity criteria will likely vary from place to place, as each traffic data collector or manager brings experience with certain roadway locations, traffic data collection equipment, or collection hardware and software. The QoS attribute of timeliness represents the degree to which data values or a set of values are provided at the time required or specified. Timeliness can be expressed in absolute or relative terms. It can be measured by two different metrics: Percentage of data received within acceptable time limits (PTD) and average delay for late data (ADLD). The PTD metric is expressed by the following formula: . P ercentT imelyData?%? ? non?time ? 100; ntotal

where navailableV alues is the number of records or rows with available values present and ntotalExpected is the total number of records or rows expected. The number of data records expected is a function of the application. The percent complete statistic is defined to include all “values present.” In this respect, completeness is defined as including both valid and invalid data values, as long as both types of data values are present in the version of data being evaluated. However, if a particular data process removes invalid data values from a database instead of flagging them as invalid and permanently storing them, then these purged invalid data values would not be included in the completeness statistic because they are not “present.” Validity is the degree to which data values satisfy acceptance requirements of the validation criteria or fall within the respective domain of acceptable values. Validity can be expressed in numerous ways. One common way is to indicate the percentage of data values that either pass or fail data validity checks. It can be measured by a metric computing the percentage of data passing validity criteria with the following formula: P ercentV alid?%? ? nvalid ? 100; ntotal

where non?time is the number of data messages or packets received within acceptable time limits and ntotal is the total number of data messages or packets received. The ADLD metric is expressed by the following formula:   X  1 ADLD ? ? ?tlate ? ? ?texprected ? ; nlate where nlate is the number of data messages or packets received outside acceptable time limits, tlate is the actual arrival time of a late data message or packet, and texprected is the expected arrival time of a late data message or packet. Besides the previous four QoS attributes, coverage is an attribute that represents the degree to which data values in a sample accurately represent the whole of what is to be measured. As with other measures, coverage can be expressed in absolute or relative units. Coverage can be expressed as the percent of roadways (or the transportation system) represented by traffic data. For instance, coverage can be computed from the following formula: cov ? coveredareareq \ coveredareaadv ; coveredareareq

where nvalid is the number of records or rows with values meeting validity criteria and ntotal is the total number of records or rows subjected to validity criteria. Validity criteria (also referred to as business rules or validation checks) are defined in many data management applications and can range from a single rule to several levels of complex rules. A simple rule might specify that traffic volume counts cannot exceed a maximum value associated with road capacity (e.g., 2,600 vehicles per hour per lane) or that traffic speeds cannot exceed a reasonable threshold (e.g., 100 mph). Other validity criteria for traffic data include the following:

where coveredareareq is the set of values determining the area the WS requester wants to cover, while coveredareaadv is the set of values determining the area the WS covers.

2.3 Benefits of QoS Usage for Web Services According to [46], several researchers have identified Web Processes (WPs) as the computing model that enables a standard method of building WSs applications and processes to connect and exchange information over the Web. For organizations, being able to characterize WPs based on

KRITIKOS AND PLEXOUSAKIS: REQUIREMENTS FOR QOS-BASED WEB SERVICE DESCRIPTION AND DISCOVERY

327

Fig. 2. The service life cycle.

QoS has four distinct advantages. First, it allows them to translate their vision into their business processes more efficiently, since a WP can be designed according to QoS metrics. Moreover, it is important for an organization to know the QoS an application will exhibit before making it available to its customers. Second, it allows for the selection and execution of WPs based on their QoS, to better fulfill customer expectations. As WP systems carry out more complex and mission-critical applications, QoS analysis serves to ensure that each application meets user requirements. Third, it makes possible the monitoring of WPs based on QoS. WPs must be rigorously and constantly monitored throughout their life cycles to assure compliance both with initial QoS requirements and targeted objectives. QoS monitoring allows adaptation strategies to be triggered when undesired metrics are identified or when threshold values are reached. Fourth, it allows for the evaluation of alternative strategies when adaptation becomes necessary. The unpredictable nature of the surrounding environment has an important impact on the strategies, methodologies, and structure of WPs. Thus, in order to complete a WP according to initial QoS requirements, it is necessary to expect to adapt, replan, and reschedule a WP in response to unexpected progress, delays, or technical conditions. When adaptation is necessary, a set of potential alternatives is generated, with the objective of changing a WP when its QoS does not meet initial requirements. An alternative is selected among the generated ones by estimating its impact on the WP’s QoS. It is essential that the services rendered follow customer specifications to meet their expectations and ensure satisfaction. Customer expectations and satisfaction can be translated into the QoS rendered and eventually in the increase of an organization’s profit. Organizations have realized that QoS management is an important factor in their operations. As WPs are composite or single WSs, all the above advantages of QoS management of WPs also apply to Web Services. Actually, QoS plays a significant role in almost all activities of the service (management) life cycle, as can be easily seen in Fig. 2, where time passes by from the left to the right, the arrows represent the temporal precedence of the activities, and the gray color in the activity representation denotes QoS absence in this activity. In the following, we are going to analyze the role that QoS plays in all the activities, focusing more on some of them. Service creation is a composite activity consisting of the activities of requirements engineering, design, and construction. QoS comes into play in the very beginning of this activity

where the QoS requirements of the service provider or of the actual users of the undercreation service are given as input. Apart from service design, QoS influences the construction of a service, especially that of a composite service. A composite service consists of a combination of WSs and internal operations and is defined by a process model that identifies the functionalities (tasks) required by the service to be composed and their interactions (e.g., control-flow, data-flow, and transactional dependencies). Then component services able to provide the required functionalities and being conformant to the QoS constraints are associated to the individual tasks. Concerning QoS, this service selection can follow a local [47], [48], a global [48], or a combination of these strategies [49]. According to the local strategy, for each task the best component service is selected based also on local QoS constraints given for this task. On the contrary, in the global strategy the selection is performed by solving an optimization problem [20], [49] that takes into account the (global) QoS constraints of the composite service, the process structure, and QoS metric aggregation rules [46]. However, as the number of services providing a given functionality may be constantly changing and some of these services will not always be available due to network problems, software evolution and repair, and hardware problems, the design-time composite service construction is not usually preferred. It must be noted that for having a successful and accurate service composition, the component services have to be properly described and discovered both functionally and with QoS. Our goal is to propose a complete set of requirements driving the QoSbased description and discovery of services. In the service testing activity, the constructed service is checked if it is functioning correctly and if it conforms to its QoS requirements. If this check fails, then the service has to be recreated. This activity takes place before and during the deployment of the service on its underlying infrastructure so as to reveal both design-time and initial runtime/ deployment problems. The goal of the service deployment activity is to assign services to the available computing and networking resources in an optimized way while satisfying three main objectives: 1) low administration effort, 2) low total cost of ownership, and 3) high degree of service performance. Static and dynamic resource management techniques [50] are needed in order to cluster instances of services with complementary load characteristics onto the same servers, thus achieving a balanced utilization of hardware resources, while ensuring that the service instances perform appropriately by starting

328

IEEE TRANSACTIONS ON SERVICES COMPUTING,

VOL. 2,

NO. 4,

OCTOBER-DECEMBER 2009

new service instances or by moving instances to more powerful servers when their performance degrades. After a service is deployed, its performance and cost model [51] can be accurately described, while its functionality is already known. For this reason, the functional and QoS capabilities of the service are described in appropriate languages and published in service repositories or registries to be found by potential customers (service advertisement). A service provider should offer different QoS levels to different customers according to the current performance characteristics of the service instances, the customer needs, the price the customer is willing to pay, and the previous use of the service. In this way, the service provider can actually control the profit for the usage of his service and he can eventually maximize it. The service discovery activity (WSDi) tries to find a WS providing specific capabilities, interfaces, and other characteristics, requested by a WS client. Its result is a set of WSs satisfying any or most of the client requirements. The WSDi activity provides better results if it is supported by a complete and accurate WSDM that is formal, complete, and accurate and provides any possible aspect that differentiates one WS from the other besides functionality. One aspect that currently is not supported by the WSs standards and not fully supported by other efforts is the QoS description of a WS. The WSDi process may return many functionally equivalent results. In this way, it will harden the task of selecting the most appropriate WS. If QoS description was incorporated into WS Description, then the returned result list would be filtered out to include only the results providing better QoS performance. Furthermore, the filtered results list can be ordered based on user functions specifying which QoS characteristics are more important to them. In this fashion, the discovery step would not only provide a more constrained result list but would also suggest the best result for the user, thus improving service selection. After service selection, even if an appropriate WS has been found, the client may not be confident that the described QoS levels of the selected WS will actually be delivered during WS execution. For this reason, the WS client and provider enter a multistep negotiation phase, where they try to agree on a trusted third-party entity monitoring QoS levels delivered, on the penalties that will be imposed when one of the two main parties does not keep up with its promises, in which situation a penalty applies, and on the validity period of the promises. The successful result of this service negotiation activity is a contract or a Service Level Agreement (SLA) [52] document that will give confidence and trust to the entities providing and consuming the service and will lead and guide the activity of service execution. If the WS client and provider do not come into agreement, the negotiation is stopped and the WS client must try to contact the second WS from the returned list of the WSDi activity. The runtime selection of component services of a composite WS (i.e., service composition activity) has been put forth as an approach to address the problems faced with the design-time construction of composite services [53], [54]. The main idea is that component services are selected by using the same techniques with respect to the ones used in the design-time composite service construction based on the agreed service (functional and QoS) level established in the SLA. If the composition is not possible, then the service

provider has to renegotiate with the client in order to lower the QoS level imposed on the initially agreed SLA. The SLA produced in the end of the service negotiation activity drives the actual service execution. The latter activity is the only activity where QoS does not play a role unless the service is designed to be adapted based on its current and previous QoS level. Adaptive services and the legally binding SLA create the need of running a service monitoring activity in parallel to service execution. This activity is responsible for monitoring the service functional and QoS levels and trigger adaptation actions when the SLA terms are violated, i.e., when undesired metrics are identified, threshold values are reached, and network or software or hardware errors happen. Adaptation actions of the service adaptation activity include repair of malfunctioning components, usage of backup machines, increase of CPU usage for a customer’s WS running operation, using alternative network paths, preference of undesired QoS levels for a WS operation instead of improving them, interrupting clients’ operations and starting an operation of a “better” client, etc. The selection and actual execution of each adaptation action depends on the current problem and the adaptation strategy that is designed and programmed to deal with it. After execution of the adaptation activity, the service may need to be recomposed (e.g., to select a new service component for a task if the previous has failed), renegotiated (to change the QoS level and price), readvertised (e.g., if a change on a specific QoS level is permanent), or dynamically redeployed and reexecuted (e.g., by running its instance on a more powerful server). In very critical circumstances, the service may have to be recreated, leading to service evolution.

3

REQUIREMENTS FOR QoS-BASED WS DESCRIPTION

Before starting this section, we must first explain that a QoS-based WSDM is a QoS metamodel and not a QoS model. The difference between a QoS metamodel and a QoS model is that the former is a generic conceptual model containing all appropriate concepts that are required for specifying quality attributes and other quality entities across all WS functional layers (BPM, Service, and Infrastructure) along with their relationships (e.g., a measurable quality attribute is measured by a quality metric), while the latter is a specific taxonomy or conceptual model that contains selected, concrete quality attributes, and other concrete quality entities, i.e., the instances or more specific concepts from the metamodel ones, respectively. A QoS metamodel is implemented by a QoS specification language that is used to create and specify a QoS model. In order to explicate the above argument, we provide a small example. Suppose that groups of quality attributes must be created and populated and we want to state that the Performance quality group consists of the response time and throughput quality attributes. The QoS metamodel would contain two concepts: 1) Quality Attribute and 2) Quality Group and one directed relationship between them which is named contains (with direction from quality groups to attributes). The corresponding QoS model would contain the subconcept or instance of Quality Group named Performance, the subconcepts or instances of Quality Attribute named response time and throughput, and two

KRITIKOS AND PLEXOUSAKIS: REQUIREMENTS FOR QOS-BASED WEB SERVICE DESCRIPTION AND DISCOVERY

329

concrete facts/relationships: 1) Performance contains response time and 2) Performance contains throughput. Finally, an XML language implementing the above QoS metamodel would express its concepts and relationships in the language’s XML Schema while the QoS model would have been expressed in a specific XML description obeying to the language’s XML Schema. After reviewing related work in QoS-based WS Description, we have come up with a set of requirements that must be satisfied by a QoS-based WSDM. In this section, this set of requirements is analyzed followed by an explanation of how our developed language fully respects them.

3.1 Requirements 3.1.1 Extensible and Formal Semantic QoS Model In the presence of multiple WSs with overlapping or identical functionality, WS requesters need objective QoS criteria to distinguish WSs. However, it is not practical to come up with a standard QoS model that can be used for all WSs in all domains. This is because QoS is a broad concept that encompasses a number of nonfunctional properties such as privacy, reputation, and usability. Moreover, when evaluating WS QoS, domain-specific criteria must be taken into consideration. For example, in the domain of phone service provisioning, the penalty rate for early termination of a contract and compensation for nonservice, offered in the service level agreement are important QoS criteria in that domain. Therefore, an extensible QoS model must be proposed that includes both the generic and domain-specific criteria. In addition, new domain-specific criteria should be added and used to evaluate QoS without changing the underlying computation (i.e., matchmaking and ranking) model. Last but not least, the semantics of QoS concepts must be described in order to have terms/concepts with specific meaning for both WS requesters and providers. In this way, QoS attributes like “application availability,” which may have different meanings if not formally defined, will have a specific meaning in QoS description. The solution to the above problems is the use of ontologies. Ontologies provide a formal, syntactic, and semantic description model of concepts, properties, and relationships between concepts. They give meaning to concepts so that they are human understandable and machine interpretable while they provide the means for interoperability. Moreover, they are extensible as new concepts, properties, or relationships can be added to them. In addition, SW techniques can be used for reasoning about concepts or for mapping between ontologies. These techniques can lead to syntactic and semantic matching of ontological concepts and enforcement of class and property constraints (e.g., type checking, cardinality constraints, etc.). Therefore, by providing semantic description of concepts and by supporting reasoning mechanisms, ontologies cater for better WSDi with high precision and recall. Last but not least, ontologies can help specialized brokers in performing complex reasoning tasks like WSDi or mediation. 3.1.2 Standards Compliance It is important for the QoS-based WSDM to comply with already widely accepted standards. In this way, it will be easily adopted by the research community. In addition, it will use all freely available tools related to these standards for its development.

3.1.3 Syntactical Separation of QoS-Based and Functional Parts of Service Specification QoS specifications should be syntactically separated from other parts of service specifications, such as interface definitions. This separation allows us to specify different QoS properties for different implementations of the same interface. Moreover, while functional constraints rarely change during runtime, QoS constraints can change during runtime. So, the separation of service offerings from WSDL descriptions permits service offerings to be deactivated, reactivated, created, or deleted dynamically without any modification of the underlying WSDL file. Last, an offer could be referenced from multiple WSDL files and thus be reused for different services. 3.1.4 Support Refinement of QoS Specifications and their Constructs As previously described, syntactical separation provides reusability. But except from reusability, another form of extensibility is equally important. QoS specifications should not only be reused but also refined. This means that a new WS QoS offering can be created by referencing an older one and by adding constraints like refinement of an older QoS restriction or creation of a new one. In addition, templates of QoS offerings can be created and appropriately extended for every domain. 3.1.5 Allow Both Provider and Requester QoS Specification It should be possible to specify both the QoS properties that clients require and the QoS properties that services provide. Moreover, these two aspects should be specified separately so that a client-server relationship has two QoS specifications: a specification that captures the client’s requirements and a specification that captures service provisioning. This separation allows us to specify the QoS characteristics of a component, the QoS properties that it provides and requires, without specifying the interconnection of components. Moreover, this separation is essential if we want to specify the QoS characteristics of components that are reused in many different contexts. 3.1.6 Allow Fine-Grained QoS Specification It should be possible to specify QoS properties/metrics at a fine-grained level. As an example, performance characteristics are commonly specified for individual operations. A QoS model must allow QoS specifications for interfaces, operations, attributes, operation parameters, and operation results. Generally speaking, any service object can have QoS attributes/metrics (e.g., elements defined in WSFL). 3.1.7 Symmetric Model of QoS Specification In [17], it is endorsed that a symmetric model of QoS specification must be adopted. The reason for this lies beneath. Asymmetric models. Let S be a multidimensional space whose dimensions are given by domains of QoS 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

330

IEEE TRANSACTIONS ON SERVICES COMPUTING,

VOL. 2,

NO. 4,

OCTOBER-DECEMBER 2009

Fig. 3. Conformance in asymmetric models. (a) Conformant and (b) nonconformant offer.

Fig. 4. Conformance in symmetric models. (a) Conformant and (b) nonconformant offer.

subspace (the demand) or not. See Figs. 3a and 3b, respectively. This checking can be computed easily by evaluating ! in . As an example, if a web service owns the offer ! ? fMT T F ? 120g, then it is conforming to the demand 1 ? fMT T F ! 100g because 120 ! 100, but not to the demand 2 ? fMT T F > 120g because MT T F2 > MT T F! . This interpretation of conformance results in a model which is asymmetric with regard to the expressiveness of QoS specifications. This semantics makes it very difficult to specify offers when something else than a point is needed, as an example to specify some uncertainty or a space. While most programming languages 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. Approaches using an asymmetric model usually have limited expressiveness because conditions are restricted to simple expressions involving single parameters. Symmetric models. Alternatively, an offer can be also considered as a subspace, so that it represents the ranges of QoS values that the corresponding WS guarantees to supply. In this way, an offer ?!? is conforming to a demand ?? whenever the offer’s subspace is inside the demand’s subspace (see Fig. 4a), otherwise the offer is not conforming (see Fig. 4b). As an example, if a WS advertises the offer ! ? fMT T F ! 120g, then it is conforming to the demand 1 ? fMT T F ! 100g, but not to the demand 2 ? fMT T F > 120g because the offer’s instance value fMT T F ? 120g is out of the demand’s space. It must be noted that in this example the offer does not satisfy the constraint of the second demand. However, the offer may partially match the second demand if it respects some of the demand’s constraints. In this way, the violation of one constraint of the service quality demand does not condemn a service quality offer to be totally rejected from the results of the matchmaking process. Continuing the previous analysis, sometimes the bounds of service quality specifications have to be defined softly and not crisply (e.g., when the bounds are based on measurements which entail a measurement error). So, this case, where the offer is ! ? fMT T F ! 120g and the demand is 2 ? fMT T F > 120g, should not result in a rejection of the offer, as the bound of the demand can entail a small but important measurement error. One way to solve this problem is to introduce weights to the “doubtful” bounds signifying their confidence and techniques like semiring-based constraint satisfaction [55] can be used for matchmaking. The above interpretation of conformance results in a symmetric model because QoS 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. That is, we cannot assume a concrete value, because it is equally possible as any value in the subspace. Additionally, symmetric approaches usually achieve a greater deal of expressiveness, since there is usually no restriction on the number of involved parameters or type of operators, so that nonlinear or more complex expressions are allowed.

3.1.8 Extensible and Formal QoS Metrics Model Each QoS attribute or metric must have the following aspects:
. . The value set for the metric or unmeasurable attribute (and its allowed value range). The domains that this attribute belongs to. For instance, is it a cross-domain attribute or an attribute specific for a domain? The weight of the metric or unmeasurable attribute relative to its domain and user preferences. This weight can also help in calculating the rank of a QoS offering. The characteristic of the function from metric or unmeasurable attribute values to overall QoS values. For instance, some attributes such as price are monotonic, at least in typical business scenarios. The temporal characteristic of the metric value. Metrics may have decaying values where the decay function can vary from exponential to a step function. There must be a description (mathematical or otherwise formal) of how a QoS metric value of a complex WS can be derived from the corresponding QoS metrics values of the individual WSs that constitute the complex one. For example, the execution time TC of a complex WS C, which is defined as a sequence of two WSs A and B, can be computed as the sum TA ? TB of the execution times of the two individual WSs. This description is essential for the automated estimation of the values of QoS metrics for a complex WS that is composed of other WSs and individual operations and is thus a prerequisite for successful QoS-based WSDi. In addition, it helps automating the WS composition process and delaying individual WS selection as late as possible (i.e., at runtime). In [26], Tosic et al. argue for the need for several ontologies that would be used in the formal representation of QoS and other constraints. These ontologies include ontology of measurement units, ontology of currency units, ontology of measured properties, and ontology of measurement methods. They must be developed in a consistent way as they may reference common concepts and relationships.

.

.

.

.

.

KRITIKOS AND PLEXOUSAKIS: REQUIREMENTS FOR QOS-BASED WEB SERVICE DESCRIPTION AND DISCOVERY

331

3.1.9 Great Expressiveness and Correct Constraint Definition A QoS specification must be comprised of QoS constraints. Each QoS constraint consists of a name, an operator, and a value [21]. The name is typically the name of a QoS metric or unmeasurable attribute, although it can also be the name of a metric aspect. We will see in a while what an aspect is. The permissible operators and values depend on the QoS metric’s or unmeasurable attribute’s value type. A value type specifies a domain of values. These values can be used in constraints involving the metric or unmeasurable attribute. The domain may be ordered. For example, a numeric domain comes with a built-in ordering (“< ”) that corresponds to the usual ordering on numbers. Set and enumeration domains do not come with a built-in ordering; for those types of domains we have to describe a user-ordering of the domain elements. The domain ordering determines which operators can be used in constraints for that domain. For example, we cannot use inequality operators (“< ,” “> ,” “! ,” “ ”) in conjunction with an unordered domain. Aspects like percentile, mean, variance, and frequency are used for the characterization of measured QoS values over some time period. For example, the percentile aspect could be used to define an upper or lower value for a percentage of the measurements or occurrences that have been observed. Aspects can be proven to be very useful in cases where we want to guarantee that the measurements or occurrences of a QoS metric present some special characteristics and we do not want to produce a new complex QoS metric from the basic one for each of these characteristics. However, aspects must be used carefully especially in cases where many aspects are created for one metric. QoS constraints are usually connected by the “and” logical operator, although they can also be connected by other logical operators, into expressions. A QoS specification should contain one complete expression or just one constraint. QoS constraints should be joined into Constraint Groups (CG) or Constraint Group Templates (parameterized CGs) in order to be reused by many QoS specifications [56]. Other reusability constructs can also be created even for expressions. 3.1.10 Allow Classes of Service Specification Class of Service, which is also commonly known as service level (e.g., see [13]), means the discrete variation of the complete service and quality provided by one service [10]. It makes sense to discuss class of service at the level of WSs and not at the level of constraints or guarantees that are part of the overall service and QoS. Classes of service can differ in usage privileges, service priorities, response time guarantees, etc. The concept of class of service also represents different capabilities, rights, and needs of potential customers of the WS, including power and type of the devices they execute on. Furthermore, different classes of service may imply different utilization of the underlying hardware and software resources and, consequently, have different prices. Additionally, different classes of service can be used for different payment models. The issues of QoS and balancing of limited underlying resources are particularly motivating for having multiple classes of service for WSs. If the underlying resources were unlimited, all consumers would always get the highest possible QoS. Unfortunately, this is not the case, so it is suitable to provide different QoS to different classes of consumer. Providers of WSs want to

achieve maximal monetary gain with optimal utilization of resources. Providing different classes of service and their balancing helps in achieving this goal because of the flexibility to accommodate several classes of consumer. On the other hand, consumers of such Web Services can better select the service and QoS they need and are willing to pay for, while minimizing their price/performance ratio.

3.1.11 Other Useful Information A WS QoS offering must provide references to protocols needed for service management and QoS monitoring as well as entries of third parties that one side would be willing to trust. This information is important as it will be used in the contract negotiation phase, after the WS client has selected the particular service and its offering. Moreover, a QoS offering must be related to the price element in order to relate the specified QoS level to the cost of service usage per invocation. Finally, a QoS offering must have an expires attribute denoting the point in time until which the offer will be valid [9]. Of course, other nonfunctional properties and management statements can be added to a QoS offering/specification, upgrading the QoS offer to a service class but this is out of the scope of this paper. 3.2 Achievements Based on the above requirements, we have developed an upper ontology for QoS-based WS Description, which is called OWL-Q [27]. OWL-Q complements OWL-S [57], a W3C submission for semantic functional WS description, by subsuming OWL-S concepts or relating them to QoS concepts (syntactical separation). Based on our upper ontology, we have also developed a midlevel ontology that defines all domain-independent QoS metrics and attributes and a low-level ontology defining QoS metrics and unmeasurable attributes that are specific to the Vehicle Traffic Monitoring application domain. Let us now concentrate on how well the requirements set previously are satisfied by OWL-Q. OWL-Q offers a semantic, rich, and extensible QoS model. The QoS model is semantic as OWL is adopted (standards compliance). It is rich as there are many facets developed each capturing an aspect of QoS-based WS description in great detail. Last but not least, it is extensible as all of these facets can be refined and specialized according to the requirements of the users. The latter advantage is mainly based on the fact that ontologies can be structured and developed independently of the others and can be connected via the namespace construct. In this way, refinement of QoS specifications is easily allowed and realized with ontologies (refinement of QoS specifications). Moreover, OWL-Q allows the specification of both QoS offers and demands in a symmetric way. Another advantage of OWL-Q is that its QoS model contains a rich and semantic QoS attributes and metrics model. The richness of this model is undoubtful as there are many aspects supported for both of these entities and in great detail. Especially, the QoS Metric, Scale, Unit, MetricValueType, and Function facets are the most rich and detailed facets with respect to all other research approaches. Concerning specification of constraints, OWL-Q supports a quite rich, extensible, and expressive constraints model. Simple constraints are defined by the expression: ?arg1 binaryP redicate arg2 ? where arg1 and arg2 are QoS metrics, metric functions, or decimal values and

332

IEEE TRANSACTIONS ON SERVICES COMPUTING,

VOL. 2,

NO. 4,

OCTOBER-DECEMBER 2009

binaryP redicate is a binary comparison predicate between these two subexpressions like ; <; !; >; ! ?; ?? . It can be easily seen that our approach is equivalent to [21] with respect to constraint specification. Moreover, metric functions can play the role of aspects in the same way they are defined in [21] because we have defined most of the time series construction and statistical functions specified in [6]. Complex constraints can be constructed by simpler ones with the help of constraint predicates. We have defined many unary, binary, and n-ary constraint predicates. OWL-Q can connect many QoSProfiles to a single ServiceProfile satisfying the requirement of class of service specification. Moreover, as QoS metrics can be defined to measure QoS properties of different Service Elements, OWLQ also satisfies the requirement of fine-grained QoS specification. Thus, OWL-Q satisfies all previously analyzed requirements. The interested reader may find a comparison of OWL-Q with other competitive approaches in [41].

4

REQUIREMENTS FOR QoS-BASED WEB SERVICE DISCOVERY

The (QoS-based) WSDi process is decomposed into two subprocesses: matchmaking and selection. In the first subprocess, the (QoS-based) WS specifications are matched and the outcome is a list of QoS offers that completely satisfy the constraints of the demand. In the second subprocess, this output list is sorted based on weights provided by the WS requester to QoS metrics and unmeasurable attributes. Both of these subprocesses depend on the (QoS-based) WS descriptions. In the sequel, the requirements for both of these subprocesses will be analyzed in two separate sections. In the end of each section, there will be a small analysis of how our current work satisfies all of these requirements.

4.1

Requirements for QoS-Based Web Service Matchmaking The QoS-based WS matchmaking process starts when the functional WS matchmaking process ends. To put it in another way, the WS matchmaking process is a composite process consisting of two sequential processes: functional and QoS based. The functional process filters WS advertisements based on the functional restrictions of the requester. The QoS-based WS matchmaking process further filters the results of the functional process based on the QoS restrictions of the requester. So, the first requirement is that the output of the functional WS matchmaking process should be the input of the QoS-based WS matchmaking process. One important thing that must be discussed is what happens if both the goal/capability and the QoS filters are applied and if their order matters. First of all, we believe that the order does play a significant role here, although these filters are independent of each other. The above order is, first of all, preferable as it is better if we know first which advertisements satisfy the requested functionally and then to see if one of the QoS offers of each qualified advertisement suits the needs of the QoS demand of the request. Second, this order is also mathematically appropriate as WSs will provide many QoS offers so that the probability that one offer suits the needs of the requester is increased. Third, there is no guarantee that the service provider is frank about his QoS offers. Therefore, an application of the QoS filter

before the goal filter will not prune as many results as those that will be pruned by the application of the goal filter. After the application of both filters, we may come into a situation where an advertisement that had a subsume [58] (i.e., not totally failing) match, regarding its capabilities, to have one of the best QoS offers. We believe that there must be some groundwork between and after the application of these filters in order to remove functional advertisements or QoS offers that do not suit the needs of the requester. That is why the participation of the requester is needed either by providing the appropriate input to the matchmaking engine (MME) or by interacting with the matchmaking engine. Therefore, the requester must determine which categories of the results of each filter are preferable or acceptable. In addition to the aforementioned groundwork, the presentation and total characterization (with respect to the degree of match) of the returned results is an inevitable choice for the matchmaking engine because the requester must know what are the best results and for each result in what category of match of each filter it was put. Notice that after matchmaking, we may come into a situation where there is one result in the best combined category. This will mean that further ranking is not needed and the selection step of the discovery process will be omitted. In practice, the selection step should not be omitted as the best discovered service could be recovering from failure or could be unavailable. Most of the requirements that are analyzed in [41] for QoS registries and WS matchmaking also stand for QoSbased WS matchmaking. In the sequel only the requirements that are specific to the QoS-based WS matchmaking process will be analyzed. QoS offers and demands that are matched during the QoS-based WS matchmaking process should be specified by the same language. The requirements on the metamodel of this language were expressed in the previous section. In addition, both providers and requesters should be encouraged to be honest with their descriptions. Otherwise, they will pay the price of either not being matched or being matched inappropriately. The matching should not be based on keyword search only. Instead, semantic and structural information about each element in the service request and advertisement must be taken into consideration. In particular, semantic matching of different QoS concept descriptions must be provided [27]. The basic part of QoSbased WS description is the one where WS providers advertise their capabilities and WS requesters provide their requirements as a set of constraints on specific QoS metrics or unmeasurable attributes. So, in order for the discovery process to be accurate, these sets of QoS concepts must be as similar as they can get. For this reason, semantic QoS metric/attribute matching algorithms must be developed and used before QoS-based WS matchmaking is performed in order to produce QoS-based WS specifications that contain the same set of QoS metrics/attributes (if possible). Moreover, knowledge about how QoS metrics are derived must also be taken into account as it can help the metric matching process by enriching the processed WS specifications. The main outcome of the metric matching process will be the alignment of QoS-based WS specifications. These aligned specifications will be then used in the matchmaking and selection algorithms increasing their precision and recall. In a perfect world, the matchmaking system would return to the requester those QoS offers that perfectly match

KRITIKOS AND PLEXOUSAKIS: REQUIREMENTS FOR QOS-BASED WEB SERVICE DESCRIPTION AND DISCOVERY

333

his request. In practice, this fact is highly unlikely to happen. One of the challenges of matchmaking is to locate those services that the requester would choose/select despite their differences from the request. Furthermore, the matchmaker should be able to characterize the distance between the request and the matches found, so that the requester can make an informed decision about which service to invoke. So, QoS offers should be grouped according to their rank (distance from request). Suppose that there is a measure or function that tells us if one solution (comprised by a specific value for every user metric or unmeasurable attribute) is better than another one (see next section). We argue that at least the following categories of results should be provided by the QoS-based matchmaking system with decreasing order of significance: Super matches: This category contains those offers that have at least one better solution and all other equivalent to the solutions of the demand. . Exact matches: This category contains those offers that have a subset of the solutions expressed by the demand. . Partial matches: This category contains those offers that have at least one worse solution than those of the demand. . Fail matches: This category contains those offers that have only worse solutions with respect to the solutions of the demand. Of course, an MME could provide more fine-grained categories than the proposed ones. However, the ranking of QoS offers must be based on the following properties: . QoS offers expressing the same set of solutions for the same QoS metrics/attributes should be given the same rank. . If a QoS offer O1 has at least one better and no worse solution than the solutions expressed by the QoS offer O2 , then O1 should have a better rank than O2 . Suppose that after the matchmaking process has been executed, there are only partial and fail matches. This is an indication of an overconstrained QoS request. Fail matches are of no use and should be discarded. However, partial matches are promising. The reason is that if one (not very important) QoS constraint of the QoS request is relaxed or deleted, then it is possible that some partial QoS offers are promoted to higher categories. This process is called constraint relaxation and must be incorporated in the QoSbased MME when the aforementioned case occurs in order to provide more value-added results to the WS requester. More details about constraint relaxation can be found in [55]. Finally, a specific requirement imposed to the QoS-based WS matchmaking system is to respond quickly to QoS demands. This depends on the technology used to perform the matchmaking. There are actually two different technologies/approaches used: reasoning and constraint-based techniques [17], [28] like CP [15] and Mixed Integer Programming (MIP) [59]. The latter techniques have been proved more effective but require the careful transformation [28] of the QoS-based WS specifications to Constraint Satisfaction Problems (CSPs) (or Mixed Integer Programming Problems—MIPPs) before matchmaking. The term careful means that the same QoS metrics and unmeasurable attributes (or .

whatever entities are used to represent them) of the processed QoS specifications must be mapped to the same variables in all the constructed (from the specifications) CSPs which are needed to be solved in order to conclude the matching of these specifications. Another dimension to consider in the second approach is the linearity of the constraints. In [28], [41], it is argued that if only linear constraints are contained in QoS-based WS specifications, then MIP must be used instead of CP, while CP is the most appropriate technique when also nonlinear constraints are contained in the QoS specifications.

4.1.1 Achievements For QoS-based WS matchmaking, we have proposed two algorithms [28] that satisfy all the requirements set above for QoS-based WS matchmaking. Their experimental evaluation [28] proves this claim. These algorithms were implemented [41] using MIP, CP, and explanation-based CP [60]. The actual system that will exploit these algorithms and their implementations will have to choose between them based on user-provided requirements (accuracy, speed, completeness, and relaxation) embodied in user profiles and the linearity of the constraints contained in QoS-based WS specifications. 4.2 Requirements for QoS-Based Web Service Selection In the selection process, the results (especially the best ones) obtained from the discovery process are further ranked in order to get the best result. The criteria for ranking are usually nonfunctional but in the context of this paper we will stick only to the QoS-based ones, which are the QoS metrics and unmeasurable attributes. The selection process is completely personalized (preference oriented) as the ranking is based on user preferences regarding the QoS criteria that are more important to him (along with the degree of importance) and different users may have different preferences. User preferences can be given separately to the selection algorithm or they can be obtained from the QoS request. Alternatively, they can be collected and derived from user context. User preferences should include weights given to criteria (either generally or with respect to their domain or group), preferred domains or QoS groups (along with their weight if the importance of domains or groups differs), information about if the increase of a criterion’s value benefits the requester, maximum normalized values of criteria, etc. Apart from user preferences, other information about the QoS criteria must be available like the type and range set of a criterion, the groups or domains the criterion belongs to, what is the ordering of the range set of the criterion, etc. This other type of information is collected/derived by the description of the QoS criteria in (user or provider defined or commonly agreed) QoS ontologies like OWL-Q. When the selection algorithm collects all the appropriate input, it starts processing available QoS offers in order to give to each of them a suitable rank/degree according to user preferences. The degree is usually computed from the P following formula: 8metric weight ? degreeOfPromisedVal , where the degree of promised value is determined by the criterion’s utility function [17]. For example, if the criterion is a positively monotonic metric, then it can be computed by the al?min next formula: degreeOfPromisedVal ? promisedV [20], max?min

334

IEEE TRANSACTIONS ON SERVICES COMPUTING,

VOL. 2,

NO. 4,

OCTOBER-DECEMBER 2009

where promisedV al is the promised value of the metric, min and max are the minimum and maximum value of the metric with respect to all the available QoS offers. If the offer promises a range of values for a criterion, then the promisedV al can be the worse or the best or the average or a combination of worse and best values [27]. Other sophisticated selection algorithms are based on normalizations and grouping of QoS criteria (in domains or functional groups), as the ones described in [61]. The purposes of normalization are 1) to allow for a uniform measurement of service qualities independent of units, 2) to provide a uniform index to represent service qualities for each provider, and 3) to allow setting a threshold regarding the qualities. The number of normalizations performed depends on how the quality criteria are grouped (i.e., the nesting degree of the groups). In case where there is a nesting of QoS groups, the WS selection algorithm must calculate the above formula for every group (at the same level of the QoS tree) taking into account the weight of each criterion/group in its group, and do this recursively starting at the bottom of the QoS tree and ending at its root (consider that there is an imaginative root group, where groups and criteria make up a QoS tree, and that the weights of all groups and criteria belonging in the same group have a sum of 1). It is important to note that according to the QoS ontology, a QoS tree (consisting of criteria and groups—all having weights) can be constructed. However, the user can give a different tree consisting of the criteria and groups he prefers, and he can give different weights from the defaults given by the QoS ontology modelers. We could say that this QoS tree can be described in a different ontological model than the QoS model or can be given with the help of XML graphs (i.e., it is described in XML format).

4.2.1 Achievements We have implemented MIP and CP versions of a novel QoSbased WS selection algorithm [41] that advances the current state of the art. Its novelty and advantages are outlined in the next paragraph. Although most QoS-based WS selection algorithms are interested in the worst score that can be given by a QoS offer; we believe that this is not enough; we have to pick among the same “worst score” offers the one that gives the best of the maximum-best scores. This feature is considered only in our algorithm. Another advantage of our selection algorithm is that it takes into account both of the limits of the WS requester and not only one value. This is very important, especially in highly dynamic application domains where just one value of a QoS metric cannot be guaranteed but only a range of values. Moreover, one of the biggest advantages of our algorithm is that it not only deals with unary QoS specifications but also with n-ary ones. This is something that is not offered by any other selection algorithm. Finally, our algorithm, depending on the linearity of constraints contained in QoS specifications, chooses between two different constraint solving techniques optimized in the two different possible cases of linearity, respectively.

5

ROADMAP

Current WS registries used for business or research purposes present limited QoS-based WSDD capabilities, if at all. The

previous sections presented some requirements that have to be respected concerning the QoS-based WSDM and the algorithms used for QoS-based WSDi. Although our work completely satisfies these requirements, it has to be enriched with various mechanisms in order to be used in WS registries. Current work proposed in the area of QoS for WSs, which focuses on a specific part of the problem, could be used for this purpose. The goal of this section is to provide a road map of enriching current WS registries with capabilities of QoSbased WSDD by exploiting already performed work and spotting areas for further research. We conclude by discussing what should be the obligations of the parties involved in the QoS-based WSDD activity (i.e., providers, requesters, and WS registry) based on this road map. We envision a QoS broker or stand-alone registry component that could be used to enhance the current functional WS registries. This broker would have the main functionality of publishing QoS offers and responding to QoS demands. Moreover, it could be used for updating the QoS offers by collecting information about them from various sources, freeing in this way WS providers from making this update themselves. Finally, this broker could use 1) leasing mechanisms for discarding QoS offers when they expire, 2) user profiling and caching mechanisms in order to respond to user queries in a fast and customized way or even perform the negotiation between the service provider and requester after the query response and produce the SLA in case of an agreement, and 3) notification mechanisms in case the Service Level Objectives (SLOs) of an SLA are violated which exploit the QoS collection mechanisms already mentioned above. Our work can play a central part in this broker. OWL-Q [27] can be exploited in two different ways. First, it can be used in semantically enriching text- or XML-based QoS specifications (please see WSDL-S [62] for the WSDL case) or QoS facts coming from QoS monitoring or feedback components. This enrichment can be performed semi- or fully automatically by exploiting IR techniques that could be used to either propose or enforce mappings (i.e., possible semantic annotations) of the structural terms to terms of the ontology (i.e., OWL-Q) KB. Of course, in case this term does not exist in the ontology KB, it would be created accordingly. Second, it can be used for the actual description of QoS-based WS specifications by WS providers and requesters or of QoS monitoring facts. Our semantic QoS metric matching algorithm [27] can be used for semantically aligning QoS-based WS specifications based on their QoS metrics. Finally, our QoS-based WS matchmaking and selection algorithms [28], [41] can be used for matchmaking and selecting between OWL-Q specifications, thus for performing QoS-based WSDi. The architecture of our envisioned QoS broker can be seen in Fig. 5. The broker consists of eight components and five DBs whose functionality is analyzed below. The QoS Information Collector is responsible for retrieving QoS facts from various sources, like WS provider and thirdparty monitoring systems and users feedback. It can also produce QoS facts itself by either monitoring WSs that have an agreement (for being monitored) with the broker system or crawling through the Internet and testing the discovered WSs [63], [64]. The QoS facts produced or retrieved are forwarded to the QoS Validator. The QoS Validator consults recommendation (trust and reputation) systems in order to assess if the source of each

KRITIKOS AND PLEXOUSAKIS: REQUIREMENTS FOR QOS-BASED WEB SERVICE DESCRIPTION AND DISCOVERY

335

Fig. 5. The QoS broker architecture.

QoS data or QoS specifications received is reliable and trustful. The QoS facts from reliable monitoring systems as well as QoS specifications from trustful users are accepted. Moreover trustful users feedback is stored in the Feedback DB. Frequently, the QoS Validator inspects the Feedback DB in order to find feedbacks of a WS from users that have similar expectations and uses techniques similar to [19] so as to produce a derived QoS fact for this WS. The similarity of users expectations can be calculated using the same techniques used for QoS-based WS matchmaking. The accepted or derived QoS facts as well as the accepted QoS specifications are forwarded to the QoS Concept Mapper. QoS facts will be of the form <QoSmetric=property URI; W S ID; value>. The role of the QoS Concept Mapper would be to fetch the QoS metric/property description and match it with the ontological terms stored in the OWL-Q KB. If the description is text or XML-based, then IR techniques will be exploited to do the matching. If the description is in OWL-Q, then the semantic QoS metric matching algorithm can be exploited. If no matching ontological term is found, then, in the first case a new one is created, and the new term is stored in the OWL-Q KB. If there is a match in the second case, then a fact of the form <URI1 sameAs URI2 > is entered in the OWL-Q KB. Once this matching takes place, the transformed (initial URI is replaced with URI of ontological term) QoS fact is stored in the WS QoS DB. Approximately, the same procedure in the QoS Concept Mapper is followed for the entered text- or XML-based QoS specifications by WS providers and requesters. The terms in these QoS specifications are matched with the ontological ones and then these specifications are transformed to OWL-Q and stored in the OWL-Q KB. In case that the WS specifiers send OWL-Q-based QoS specifications, then the QoS metric matching algorithm is exploited in order to align them based on the contents of the OWL-Q KB and then store them in this DB. If a WS provider is updating one of his QoS offers, then when storing the transformed OWL-Q QoS offer, the previous offer is replaced by the new one. The QoS Offer Updater frequently monitors the WS QoS DB for new facts and then it applies statistical methods in order to infer if a QoS offer of a WS has to be updated as the promise for a specific QoS metric has changed. If this is the case, then the corresponding OWL-Q offer in the OWL-Q

KB is changed by replacing the appropriate ontological fact with a new one. As the QoS broker is a stand-alone component, there are two ways the QoS-based WS matchmaking can be performed. In the first case, an OWL-Q request is fed into the system by a WS requester. The QoS Matchmaker consults the User Profile DB to find the corresponding user’s capabilities and preferences and then performs the matchmaking by fetching the OWL-Q offers stored in the OWL-Q KB one by one and matching them with the OWL-Q demand. Depending on the linearity of the constraints and the user’s preferences, the appropriate matchmaking algorithm is executed. In the second case, the OWL-Q demand and a list of WS IDs are fed into the system by a functional WS registry. The procedure followed is similar. However, only the QoS offers that correspond to the IDs of the WSs that match the user’s functional requirements are processed and matched. If there are many equivalent results returned by the QoS Matchmaker, then the QoS Selector is called that takes as input the matched OWL-Q offers and the corresponding OWL-Q request. Then depending on the linearity of the constraints and the user’s preferences it executes the appropriate WS selection algorithm and returns back the results to the issuer. If the issuer is a WS requester, then an ordered list containing the name of the WS, the URI of its functional specification, the corresponding OWL-Q offer, and its rank is returned. If the issuer is a functional WS registry, then it sends back to it an ordered list of WS IDs along with their rank. In both these cases, if the corresponding WS requester wants to negotiate with the WS provider on the “best” WS, then the IDs of the WS provider and requester and their corresponding OWL-Q specifications are sent to the Negotiator. The Negotiator component takes as input the previous information and fetches from the User Profile DB the appropriate user information (e.g., negotiation strategies). Then, it starts a simulated negotiation process. If this process ends successfully, then an SLA specification (e.g., WSLA [6]) is produced based on the agreement reached and by downloading the WS’s functional specification from its URI (or from the WS registry). This SLA specification is sent to the two users in order to inspect and finally agree with the content. If they agree, then the produced specification is stored in the SLA DB. Each SLO of each SLA stored in the SLA DB is checked for validity by the SLO Violation Notifier. This component has similar functionality with the QoS Offer Updater as it constantly monitors the WS QoS DB and uses statistical methods in order to discover if an SLO is violated. If this is the case, then the corresponding parties are informed about this violation and maybe appropriate management actions in their system are taken to remedy this problem. As it can be easily seen from the above analysis, most of the QoS broker’s components are easy to implement as their functionality can be fully provided or be assisted by already proposed research work and techniques. So, our vision is realistic and may finally become true. However, some additional research should be performed on some of the proposed QoS broker components. In particular, specialized IR techniques for transforming text- or XML-based specifications to ontological ones are needed. Moreover, advanced statistical methods are needed in order to detect changes in the QoS promises or SLOs of WS providers. Finally, advanced user profiling and constraint-based specifications

336

IEEE TRANSACTIONS ON SERVICES COMPUTING,

VOL. 2,

NO. 4,

OCTOBER-DECEMBER 2009

caching techniques are needed for effective QoS-based WS matchmaking and negotiation. Even if the envisioned QoS broker can be or is finally implemented, the WS providers, requesters, and registries face a new set of challenges that have to be met so as to exploit the full functionality of this broker. WS providers must use simulation and other performance analysis tools in order to discover the QoS constraints of each class of service. Then, they should use and feed their QoS constraints to a tool that will produce OWL-Q (or other language) offers associated to the WS functional offer. Next, they should publish these offers to the QoS broker. A prerequisite of the above is the providers’ frankness about their QoS offerings. Finally, they may feed the QoS broker with QoS monitoring facts about their services or make special agreements with the broker so that it takes care of monitoring their WSs and updating their WSs corresponding QoS offers. WS requesters must be able to understand the needs of their applications and, with the help of appropriate tools, translate them to functional and QoS-based requests. They should comprehend that if they specify many hard constraints, then they may not get any result and that if they are vague, then they will get too many results. Thus, they must be wise to express a specific number of constraints (hard or soft) and they should also provide weights and utility functions for every QoS criterion of interest. In the end, they should use appropriate tools to produce OWL-Q files and send them as queries to the QoS broker/registry. WS registries, if enhanced with our envisioned QoS broker, must provide an API for the semantic advertisement and enquiry of the functional and QoS-based parts of WSs. They should also implement APIs for the management of QoS and functional offers (activation, deactivation, creation, and deletion). They should carefully associate functional with corresponding QoS offers (of the same WS) so as to avoid cases where a deletion of a functional offer does not cause the deletion of the corresponding QoS offers.

[4] [5] [6] [7] [8] [9]

[10] [11] [12] [13] [14] [15] [16] [17]

[18] [19]

6

CONCLUSION

In this paper, after defining QoS and the role it plays in the management of WSs, an analysis of the requirements for semantic QoS-based WSDD were provided. Additionally, a proposal of how to produce a semantically enhanced and stand-alone QoS broker that could be used in a complementary way to current functional WS registries was given. Last but not least, the responsibilities of the participating entities in sight of the envisioned QoS broker were analyzed. We are currently working on the development and evaluation of the envisioned QoS broker. An extension to this work would focus on QoS-based WS composition and adaptation and on the representation, semiautomatic production, validity checking, analysis, and enforcement of composite SLAs.

[20] [21]

[22]

[23]

[24]

REFERENCES
[1] [2] Handbook on Ontologies, S. Staab and R. Studer, eds. Springer, 2004. M. Klusch, B. Fries, and K. Sycara, “Automated Semantic Web Service Discovery with OWLS-MX,” Proc. Fifth Int’l Joint Conf. Autonomous Agents and Multiagent Systems (AAMAS ’06), pp. 915922, 2006. P. Plebani and B. Pernici, “URBE: Web Service Retrieval Based on Similarity Evaluation,” IEEE Trans. Knowledge and Data Eng., vol. 21, no. 11, pp. 1629-1642, Jan. 2009. [25] [26]

[3]

E.M. Maximilien and M.P. Singh, “Conceptual Model of Web Service Reputation,” SIGMOD Record, vol. 31, no. 4, pp. 36-41, 2002. L. Jin, V. Machiraju, and A. Sahai, “Analysis on Service Level Agreement of Web Services,” Technical Report HPL-2002-180, Software Technology Laboratories, HP Laboratories, 2002. A. Keller and H. Ludwig, “The WSLA Framework: Specifying and Monitoring Service Level Agreements for Web Services,” Technical Report RC22456 (W0205-171), IBM, 2003. S. Ran, “A Model for Web Services Discovery with QoS,” ACM SIGecom Exchanges, vol. 4, no. 1, pp. 1-10, 2003. ?n-D? ?az, A.R. Corte ? s, D. Benavides, A. Dura ? n, and M. Toro, O. Mart? “A Quality-Aware Approach to Web Services Procurement,” Proc. Technologies for E-Services (TES ’03), pp. 42-53, 2003. M. Tian, A. Gramm, M. Nabulsi, H. Ritter, J. Schiller, and T. Voigt, “QoS Integration in Web Services,” Proc. Gesellschaft fur Informatik DWS 2003, Doktorandenworkshop Technologien und Anwendungen von XML (Proc. PhD Students Workshop Technologies and Applications of XML), Oct. 2003. V. Tosic, B. Pagurek, and K. Patel, “WSOL—A Language for the Formal Specification of Classes of Service for Web Services,” Proc. IEEE Int’l Conf. Web Services (ICWS ’03), pp. 375-381, 2003. S. Degwekar, S.Y.W. Su, and H. Lam, “Constraint Specification and Processing in Web Services Publication and Discovery,” Proc. IEEE Int’l Conf. Web Services (ICWS ’04), pp. 210-217, 2004. C. Zhou, L.-T. Chia, and B.-S. Lee, “DAML-QoS Ontology for Web Services,” Proc. IEEE Int’l Conf. Web Services (ICWS ’04), pp. 472479, 2004. N. Oldham, K. Verma, A. Sheth, and F. Hakimpour, “Semantic WS-Agreement Partner Selection,” Proc. 15th Int’l Conf. World Wide Web (WWW ’06), pp. 697-706, 2006. E. Giallonardo and E. Zimeo, “More Semantics in QoS Matching,” Proc. IEEE Int’l Conf. Service-Oriented Computing and Applications, pp. 163-171, 2007. P. Van Hentenryck and V. Saraswat, “Strategic Directions in Constraint Programming,” ACM Computing Surveys, vol. 28, no. 4, pp. 701-726, 1996. F. Rossi, P. van Beek, and T. Walsh, Handbook of Constraint Programming (Foundations of Artificial Intelligence). Elsevier Science, Inc., 2006. ? s, O. Mart? ?n-D? ?az, A.D. Toro, and M. Toro, “Improving A.R. Corte the Automatic Procurement of Web Services Using Constraint Programming,” Int’l J. Cooperative Information Systems, vol. 14, no. 4, pp. 439-468, 2005. S. Liebesman, ISO 9000—An Introduction, ch. 1, AT&T Corporate Quality Office, July 1994. V. Deora, J. Shao, W.A. Gray, and N.J. Fiddian, “A Quality of Service Management Framework Based on User Expectations,” Proc. Int’l Conf. Service Oriented Computing (ICSOC ’03), pp. 104114, 2003. L. Zeng, B. Benatallah, M. Dumas, J. Kalagnanam, and Q.Z. Sheng, “Quality Driven Web Services Composition,” Proc. 12th Int’l Conf. World Wide Web (WWW ’03), pp. 411-421, 2003. S. Fr?lund and J. Koistinen, “Quality of Services Specification in Distributed Object Systems Design,” Proc. Fourth Conf. USENIX Conf. Object-Oriented Technologies and Systems (COOTS ’98), vol. 4, 1998. M. Anbazhagan and A. Nagarajan, “Understanding Quality of Service for Web Services,” IBM Developerworks Website, http:// www-106.ibm.com/developerworks/library/ws-quality.html, Jan. 2002. R. Sumra and D. Arulazi, “Quality of Service for Web Services— Demystification, Limitations, and Best Practices,” Developer.com Website, http://www.developer.com/services/article.php/ 2027911, Mar. 2003. K. Lee, J. Jeon, W. Lee, S.-H. Jeong, and S.-W. Park, “QoS for Web Services: Requirements and Possible Approaches,” World Wide Web Consortium (W3C) Note, http://www.w3c.or.kr/kr-office/ TR/2003/ws-qos, Nov. 2003. C. Cappiello, M. Comuzzi, and P. Plebani, “On Automated Generation of Web Service Level Agreements,” Proc. Conf. Advanced Information Systems Eng. (CAiSE ’07), pp. 264-278, 2007. V. Tosic, B. Esfandiari, B. Pagurek, and K. Patel, “On Requirements for Ontologies in Management of Web Services,” Proc. Conf. Advanced Information Systems Eng. (CAiSE ’02)/Proc. Int’l Workshop Web Services, E-Business, and the Semantic Web (WES ’02): Revised Papers from WES ’02, pp. 237-247, 2002.

KRITIKOS AND PLEXOUSAKIS: REQUIREMENTS FOR QOS-BASED WEB SERVICE DESCRIPTION AND DISCOVERY

337

[27] K. Kritikos and D. Plexousakis, “Semantic QoS Metric Matching,” Proc. European Conf. Web Services (ECOWS ’06), pp. 265-274, 2006. [28] K. Kritikos and D. Plexousakis, “Mixed Integer Programming for QoS-Based Web Service Matchmaking,” IEEE Trans. Services Computing, vol. 2, no. 2, pp. 122-139, Apr.-June 2009. [29] M. Comuzzi and B. Pernici, “A Framework for QoS-Based Web Service Contracting,” ACM Trans. Web, vol. 3, no. 3, pp. 1-52, 2009. [30] R.L. Cruz, “Quality of Service Guarantees in Virtual Circuit Switched Networks,” IEEE J. Selected Areas in Comm., vol. 13, no. 6, pp. 1048-1056, Aug. 1995. ? rin, V. Peris, and K.N. Sivarajan, “Efficient [31] L. Georgiadis, R. Gue Network QoS Provisioning Based on Per Node Traffic Shaping,” IEEE/ACM Trans. Networking, vol. 4, no. 4, pp. 482-501, Aug. 1996. [32] K. Salamatian and S. Fdida, “Measurement Based Modeling of Quality of Service in the Internet: A Methodological Approach,” Proc. Thyrrhenian Int’l Workshop Digital Comm. (IWDC ’01), pp. 158174, 2001. [33] D.D. Clark, S. Shenker, and L. Zhang, “Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism,” SIGCOMM Computer Comm. Rev., vol. 22, no. 4, pp. 14-26, 1992. [34] D.L. Tien, O. Villin, and C. Bac, “CORBA Application Tailored Manager for Quality of Service Support,” Proc. Third IEEE Int’l Symp. Object-Oriented Real-Time Distributed Computing (ISORC ’00), pp. 52-59, 2000. [35] T. Hamada, S. Hogg, J. Rajahalme, C. Licciardi, L. Kristiansen, and P.F. Hansen, “Service Quality in TINA—Quality of Service Trading in Open Network Architecture,” Proc. First Int’l Conf. Enterprise Distributed Object Computing (EDOC ’97), pp. 322-333, 1997. [36] B. Sabata, S. Chatterjee, M. Davis, J.J. Sydir, and T.F. Lawrence, “Taxomomy of QoS Specifications,” Proc. Third Workshop ObjectOriented Real-Time Dependable Systems (WORDS ’97), pp. 100-107, 1997. [37] Y.W. Lee, D.M. Strong, B.K. Kahn, and R.Y. Wang, “AIMQ: A Methodology for Information Quality Assessment,” Information Management, vol. 40, no. 2, pp. 133-146, 2002. [38] A. Avizienis, J.-C. Laprie, and B. Randell, “Fundamental Concepts of Dependability,” Technical Report 0100, Computer Science Dept., Univ. of California, Los Angeles, 2001. [39] H.-L. Truong, R. Samborski, and T. Fahringer, “Towards a Framework for Monitoring and Analyzing QoS Metrics of Grid Services,” Proc. IEEE Int’l Conf. e-Science and Grid Computing, Dec. 2006. [40] C. Cappiello, “The Quality Registry,” Mobile Information Systems— Infrastructure and Design for Adaptivity and Flexibility, SpringerVerlag, pp. 307-317, 2006. [41] K. Kritikos, “QoS-Based Web Service Description and Discovery,” PhD thesis, Computer Science Dept., Univ. of Crete, Dec. 2008. [42] H. Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications. Kluwer Academic Publishers, 1997. [43] N.J. Gunther, The Practical Performance Analyst, foreword by R. Jain. Authors Choice Press, 2000. [44] M.P. Papazoglou, “Web Services and Business Transactions,” World Wide Web, vol. 6, no. 1, pp. 49-91, 2003. [45] C. Sun and M. Aiello, “Requirements and Evaluation of Protocols and Tools for Transaction Management in Service Centric Systems,” Proc. Ann. Int’l Computer Software and Applications Conf., vol. 2, pp. 461-466, 2007. [46] J. Cardoso, A.P. Sheth, J.A. Miller, J. Arnold, and K. Kochut, “Quality of Service for Workflows and Web Service Processes,” J. Web Semantics, vol. 1, no. 3, pp. 281-308, 2004. ? , “QoS Issues in Web Services,” IEEE Internet [47] D.A. Menasce Computing, vol. 6, no. 6, pp. 72-75, Nov./Dec. 2002. [48] L. Zeng, B. Benatallah, A.H. Ngu, M. Dumas, J. Kalagnanam, and H. Chang, “QoS-Aware Middleware for Web Services Composition,” IEEE Trans. Software Eng., vol. 30, no. 5, pp. 311-327, May 2004. [49] D. Ardagna and B. Pernici, “Adaptive Service Composition in Flexible Processes,” IEEE Trans. Software Eng., vol. 33, no. 6, pp. 369-384, June 2007. [50] D. Gmach, S. Krompass, A. Scholz, M. Wimmer, and A. Kemper, “Adaptive Quality of Service Management for Enterprise Services,” ACM Trans. Web, vol. 2, no. 1, pp. 1-46, 2008. [51] A.V. Moorsel, “Metrics for the Internet Age: Quality of Experience and Quality of Business,” Technical Report HPL-2001-179, HP Labs, Aug. 2001.

[52] H. Ludwig, A. Dan, and R. Kearney, “Cremona: An Architecture and Library for Creation and Monitoring of WS-Agreements,” Proc. Second Int’l Conf. Service Oriented Computing (ICSOC ’04), pp. 65-74, 2004. [53] F. Casati, S. Ilnicki, L.-J. Jin, V. Krishnamoorthy, and M. chien Shan, “eFlow: A Platform for Developing and Managing Composite e-Services,” Technical Report HPL-2000-36, HP Labs, 2000. [54] B. Benatallah, Q.Z. Sheng, A.H.H. Ngu, and M. Dumas, “Declarative Composition and Peer-to-Peer Provisioning of Dynamic Web Services,” Proc. Int’l Conf. Data Eng. (ICDE ’02), pp. 297-308, 2002. [55] S. Bistarelli, U. Montanari, and F. Rossi, “Semiring-Based Constraint Satisfaction and Optimization,” J. ACM, vol. 44, no. 2, pp. 201-236, 1997. [56] V. Tosic, W. Ma, B. Pagurek, and B. Esfandiari, “On the Dynamic Manipulation of Classes of Service for XML Web Services,” Research Report SCE-03-15, Dept. of Systems and Computer Eng., Carleton Univ., 2003. [57] K. Sycara et al., OWL-S 1.0 Release, OWL-S Coalition, http:// www.daml.org/services/owl-s/1.0/, 2003. [58] M. Paolucci, T. Kawamura, T.R. Payne, and K.P. Sycara, “Semantic Matching of Web Services Capabilities,” Proc. First Int’l Semantic Web Conf. Semantic Web (ISWC ’02), pp. 333-347, 2002. [59] A. Schrijver, Theory of Linear and Integer Programming. John Wiley, 1986. [60] G. Verfaillie and N. Jussien, “Constraint Solving in Uncertain and Dynamic Environments: A Survey,” Constraints, vol. 10, pp. 253281, July 2005. [61] Y. Liu, A.H.H. Ngu, and L. Zeng, “QoS Computation and Policing in Dynamic Web Service Selection,” Proc. Int’l Conf. World Wide Web (WWW) (Alternate Track Papers & Posters), pp. 66-73, 2004. [62] K. Sivashanmugam, K. Verma, A.P. Sheth, and J.A. Miller, “Adding Semantics to Web Services Standards,” Proc. Int’l Conf. Web Services (ICWS ’03), pp. 395-401, 2003. [63] E. Al Masri and Q.H. Mahmoud, “Investigating Web Services on the World Wide Web,” Proc. Int’l Conf. World Wide Web (WWW ’08), pp. 795-804, 2008. [64] E. Al Masri and Q.H. Mahmoud, “QoS-Based Discovery and Ranking of Web Services,” Proc. Int’l Conf. Computer Comm. and Networks (ICCCN ’07), pp. 529-534, 2007. Kyriakos Kritikos received the BSc, MSc, and PhD degrees in computer science from the University of Crete. From 2000 to 2008, he was a researcher in the Information Systems Laboratory at the Institute of Computer Science, FORTH, Greece. Currently, he is a postdoctoral researcher at the Politecnico di Milano in Italy. His research interests span the following areas: service-oriented computing with focus on quality-based service description, discovery, composition, and adaptation and on automated service negotiation, ontology modeling and reasoning, constraint and mathematical programming, and distributed (information) systems. Dimitris Plexousakis received the BSc degree in computer science from the University of Crete and the MSc and PhD degrees in computer science from the University of Toronto. He is a professor and chair of the Department of Computer Science, University of Crete, and a researcher in the Information Systems Laboratory at the Institute of Computer Science, FORTH, Greece. His research interests span the following areas: knowledge representation and knowledge base design, formal knowledge representation models and query languages for the semantic Web, formal reasoning systems with focus on dynamic action theories and belief revision, and business process and e-service modeling, discovery, and composition. He is a member of the ACM and the IEEE.


相关文章:
更多相关标签: