Quality of Service (QoS) guarantees are usually regulated in a Service Level Agreement (SLA) between provider and consumer of services. Such guarantees are often violated, it may however be the case where the available services do not match exactly all required QoS, leading the system to grind to a halt. It would be better to look for an approximation for acceptable QoS and avoid the complete stopping of the running services. This paper aims at making dynamic QoS acceptability easy for service selection. The proposed model is based on an extension of existing probabilistic description logics reacting to QoS variations. The contributions made are twofold (1) a query description language to express the required QoS by means of a probabilistic description logic (2) a reasoning algorithm for decision making about the acceptability of QoS w.r.t the probabilistic description.
In a Service Oriented Architecture, service providers need to characterize their services de ning both the o ered functionalities and the o ered quality. Then, the quality of service (QoS) properties can be critical elements for achieving the business goals of service providers. Establishing QoS contracts, described in a SLA, that can be monitored at runtime, is therefore of paramount importance. The SLA must stipulate the values of QoS attributes that a service provider is expected to deliver to a client.
Moreover, a successful execution of a service composition implies continuous monitoring of QoS at runtime. However, at this step, variations could occur in the QoS and most likely induce violations of the agreement. For that, the service composition should support a dynamic QoS-driven adaptation. A static adaptation is not adequate due to variations of the QoS. Existing approaches deal with static QoS, they do not address the attribute variations issue. A formal and declarative approach to achieve a dynamic adaptation is then highly desired.
In this paper, we propose a probabilistic description logic based approach to describe the QoS attributes and handle their variations through the use of linguistic concepts. The proposed approach helps to select services in order to build approximate compositions which may not satisfy all the requirements, hence avoiding to completely stop running the processes. It provides the basis allowing the representation and reasoning about the introduced symbolic concepts, where the variation of QoS is modeled in a probabilistic way, hence managing the QoS acceptability. Our main contributions are summarized in the following: 1. We introduce a query description language to express the required QoS using both linguistic concepts and probabilistic representations. To this end, we extend existing probabilistic description logics to handle QoS variations. 2. We develop a suitable reasoning algorithm for computing the QoS acceptability of the selected service w.r.t the probabilistic description. The algorithm achieves an approximate reasoning using inference rules involving probabilistic statements.
The remainder of the paper is structured as follows. In section 2, we provide rst, a discussion about existing works dealing with QoS and, second a review of the approaches related to probabilistic description logics. Section 3 describes our proposal to manage the QoS acceptability. In section 4, we present the syntax and semantics of the proposed language. Section 5 details the reasoning algorithm and section 6 concludes the paper. 2
Most of existing approaches focused on the contract de nition and on
mechanisms for contract enactment. [
On the other hand, semantic technologies have been applied in recent works
for reasoning about QoS of di erent systems during service composition. [
It is worthy to note that the above approaches do not handle the variations of QoS at runtime. An e ective service composition management requires a support for the acceptance of QoS values, and should also allow for a exible acceptability for autonomous corrective actions. We provide here a probabilistic description logic based approach allowing self-healing in reaction to QoS variations by expressing their semantics.
In the literature, a number of works on probabilistic description logics exists
[
Dynamic QoS Acceptability Framework As depicted in Figure 1, our work can be integrated into a service composition system as a real-time QoS acceptability process. The inputs are the QoS required by the service selection process and the events captured by the monitoring process. The output is a set of acceptable services regarding their e ective QoS. Events dealing with real-time execution of services are captured by the mon
Service Composition Framework
SLA QoS Requirements
Required QoS
Acceptable services Service composition w.r.t. QoS
Services Service execution execution results
QoS selection process Probabilistic QoS Probabilsitic description Selection process Probabilistic reasoning
Probabilistic QoS
Probablistic calculus process
Interpreted events Symbolic encoding process
events Monitoring
process
Fig. 1. QoS variations framework for service selection itoring process. From these events, we extract real-time measures of the QoS provided by services. To e ciently handle such measures for the purpose of decision making, they are expressed thanks to symbolic concepts while taking into account their variations in a probabilistic way. We illustrate this idea through the following example.
Let us consider two services S1 and S2 involved in a web services composition. Assume that the monitoring process has captured the events given in Table 1. Each quantitative measure captured by the monitoring process is interpreted by symbolic value using business rules. Business rules may be provided by the application domain experts in a Service Level Agreement (SLA). In what follow are examples of business rules: { Rule 1 (for the interpretation of Time Response measures): A response time is said to be good (GoodTR) if it is less than 3ms, medium (MediumTR) if it is between 4ms and 6ms and bad (BadTR) otherwise. { Rule 2 (for the interpretation of RAM consuming measures): A RAM consuming is said to be good (GoodRC) if it is less than 5Mb, bad (BadRC) otherwise.
Given the above two rules, the measures of Time Response and RAM are shown in Table 1 can be expressed in the following qualitative/symbolic descriptions: { Event 1: S1 : BadTR, S1 : GoodRC. { Event 2: S1 : GoodTR, S1 : BadRC. { Event 3: S1 : GoodTR, S1 : GoodRC. { Event 4: S1 : MiddleTR, S1 : BadRC. { Event 5: S2 : GoodTR, S2 : BadRC.
{ Event 6: S2 : GoodTR, S2 : BadRC. 3.2
The real-time QoS of a given service is not static but varies over di erent executions of the service. The QoS of each service has to be represented by a unique description in terms of a probability distribution 1. Hence, the multiple values about a symbolic QoS are described using the Bayesian probability de ned as follows:
P (SymbQoSjSi) = P (SymbQoS\Si) = jSymbQoS\Sij
P (Si) jSij = number of appearences of SymbQoS in the events of Si
Number of executions of Si where SymbQoS 2 fBadT R; GoodT R; M iddleT R; BadRC; GoodRC; M iddleRC g. Back to the example introduced in section 3.1, the services S1 and S2 have been executed four times and twice, respectively. Hence, the probability values associated with their QoS can be computed as follows: { S1 received once BadTR. So, S1 is BadTR with a probability of 0:25. { S1 received three times GoodTR. So, S1 is GoodTR with a probability of 0:75. { S1 received twice GoodRC. So, S1 is GoodRC with a probability of 0:5. { S1 received twice BadRC. So, S1 is BadRC with a probability of 0:5. { S2 received twice GoodTR. So, S2 is GoodTR with a probability of 1. { S2 received twice BadRC. So, S2 is BadRC with a probability of 1. 3.3
Given a required QoS, a traditional selection process decides whether a known service is acceptable or not. In our case, the selection process operates in an uncertain (probabilistic) environment since each QoS is described thanks to a probability distribution.
To this end, we propose a formal model based on probabilistic DLs to process acceptability of QoS. In this model, the required and provided QoS are described using a formal description language. A reasoning algorithm to decide the acceptability, is proposed as well.
As example for a required QoS, let's consider the following query: Retrieve the services that should provide a Good Response Time with a probability greater than 0.7 and Bad RAM Consuming with a probability less than 0.55. Intuitively, Only service S1 is acceptable with respect to this required QoS, the Service S2 is not acceptable because it does not provide Bad RAM consuming with probability less than 0.55. 1 The interpretation of probability considered here is the so-called "the a-priori interpretation" which is the oldest and simplest one. The probability of an event is the number of favorable cases, where this event occurs, divided by the total numbers of possibles cases. So, w.r.t the same service and the same attribute, the required axiom that probabilities add up to 1 holds In what follows, we present the proposed formal model for QoS acceptability decision making. 4
Probabilistic DL for Handling QoS Acceptability The model relies on a probabilistic extension of DL de ned with the following components: { An expression language, including a set of symbols that are used to express knowledge about QoS. { A semantic of symbols of the expression language, based on an interpretation domain and an interpretation function. { A reasoning algorithm based on a set of inference rules to make a decision about the QoS acceptability.
The proposed syntax is summarized in Table 2 (with 2 f<; >; ; g). The introduced description language allows expressing two types of information related to QoS: 1. The knowledge about dynamic QoS, and 2. The information related to the required QoS.
Q p Refers to services that provide the QoS Q with a probability p (Q 1 is noted Q) Q1 p u Q2 q Refers to services that provide the QoS Q1 and Q2 with probability, respectively, p and Q1 p t Q2 q Refers to services that provide the QoS Q1 or Q2 with probability, p and q, respectively :Q p Refers to services that do not have the QoS Q with a probability p Q1 v Q2 Means: Any service that provides the QoS Q1, then it provides automatically the QoS Q2.
Table 2. Syntax of the proposed description language q
For instance, the dynamic QoS of the example provided in the previous section can be written as follows: BadT R0:25(S1), GoodT R0:75(S1), GoodRC0:5(S1), BadRC0:5(S1),
GoodT R1(S2), BadRC1(S2).
Similarly, the description of the required QoS can also be expressed using this language. For example, the following formulas are two di erent descriptions of possible required QoS: GoodT R 0:7 u GoodRC 0:4 :BadT R 0:1 u GoodRC 0:9
In the rst, we require a good time response with a minimum rate of 70% and good RAM Consuming with the minimum rate of 40%. While in the second one, we require services that provide good RAM Consuming with probability greater or equal than 90% and, at the same time, do not provide bad time response with probability greater than 10%.
The formal semantics of terms and constructors of the description language is de ned by the pair I ; :I where: { I is an interpretation domain. It is composed of individuals that represent the services managed in the BPM (Business Process Management) system. { :I is an interpretation function that assigns terms Q of the language to individuals of I as shown in Table 4 (where p stands for the complementary of p, for instance >p = p):
Q p QIp = s 2 I j QI (s) p Q1 p u Q2 q Q1Ip u Q2Iq = s 2 I j Q1I (s) p ^ Q2I (s) q Q1 p t Q2 q Q1Ip t Q2Iq = s 2 I j Q1I (s) p _ Q2I (s) q :Q p (:Q)Ip = QIp = s 2 I j QI (s) p Q1 v Q2 8s 2 I ; Q1I (s) ) Q2I (s)
Table 3. Formal semantics of the proposed probabilistic DL
For instance, the probabilistic concept Q 0:5 is interpreted as the set of individuals with a probability degree greater than 0:5. Interpretation of complex and composed descriptions is also allowed as stated in Table 3. 5
Reasoning Algorithm for the Dynamic QoS
Acceptability Decision Based on the syntax and semantics of the description language presented in the previous section, we develop a reasoning algorithm that decides whether a provided dynamic QoS is acceptable with respect to a required one.
The decision problem is formulated as follows: "Is the dynamic QoS provided by the service Si acceptable with respect to a given required QoS RQ ?"
This acceptability decision problem can be formalized by the following logical deduction: h(T Box; ABox)i j= RQ(Si) where (T Box; ABox) is the knowledge base with two components: { A TBox: containing knowledges about the considered domain application.
For example, it may contain the following axioms: fGoodT R1 v BadT R0, BadRC1 v GoodRC0g { An ABox: containing knowledges about dynamic QoS provided by services.
For example, the ABox may contain the previous QoS of services S1 and S2: fBadT R0:25(S1); GoodT R0:75(S1); GoodRC0:5(S1); BadRC0:5(S1); GoodT R1(S2); BadRC1(S2)g
The logical deduction is achieved by checking the inconsistency of the following knowledge base:
hT Box; ABox [ f:RQ(Si)gi
The inference machinery calls on the propagation rules introduced in the following sub-section. 5.1
A sample of the propagation rules that constitute the foundations of our probabilistic DL is depicted in Figure 2. Those rules are de ned with respect to the formal semantics given in section 4. For sake of clarity, the Rreduction rules are given for and , one can easily deduce the corresponding rules for < and >. The algorithm checks the consistency of the knowledge base:
hT Box; ABox [ :RQ(Si)i by applying the propagation rules until termination. Each application of a propagation rule generates a new inference system ISi. The algorithm terminates if: 1. There exists a clash in the current inference system. In this case, the knowledge base is not consistent which means that the checked QoS is acceptable. 2. No more rule can be applied to generate a new inference system. In this case, the knowledge base is consistent, which means that the checked QoS is not acceptable. Rule Rt : ISi = f(Q1 p t Q2 q)(s)g ! ISi0+1 = ISi [ fQ1 p(s)g ; ISi0+01 = ISi [ fQ2 q(s)g Rule Rv : ISi = f(Q1 p v Q2 q); Q1 p(s)g ! ISi+1 = ISi [ fQ2 q(s)g Rule Rv0 : ISi = f(Q1 p v Q2 q); Q1=r(s); p Rule Rreduction: ISi = fQ p(s); Q p(s)g ISi = fQ p(s); Q q(s); p ISi = fQ p(s); Q=q(s); q ISi = fQ p(s); Q q(s); p ISi = fQ p(s); Q=q(s); p
rg ! ISi+1 = ISi [ fQ2 q(s)g ! ISi+1 = ISi fQ p(s); Q p(s)g + fQ=p(s)g qg ! ISi+1 = ISi fQ q(s)g pg ! ISi+1 = ISi fQ p(s)g qg ! ISi+1 = ISi fQ q(s)g qg ! ISi+1 = ISi fQ p(s)g We illustrate the use of the proposed algorithm to decide whether the dymanic QoS of services S1 and S2 is acceptable with respect to the following required QoS:
RQ = (GoodRC 0:4 u :BadT R 0:8) t GoodRC 0:9.
Acceptance of the QoS of S2 The QoS of the service S2 is acceptable w.r.t RQ if:
hT Boxexple; ABoxexplei j= RQ(S2).
That is, hT Boxexple; ABoxexple [ f:RQ(S2)gi is inconsistent where, T Boxexple = fBadRC1 v GoodRC0g ABoxexple = fGoodT R1(S2); BadRC1(S2)g
The reasoning algorithm generates inference systems ISi by applying the propagation rules as follows:
IS0 = fT Boxexple; ABoxexple; :RQ(S2)g
= fBadRC1 v GoodRC0; GoodT R1(S2); BadRC1(S2); :[(GoodRC 0:4u :BadT R 0:8) t GoodRC 0:9](S2)g
IS1 = IS0[fGoodRC0(S2); [:(GoodRC 0:4 u :BadT R 0:8) u :GoodRC 0:9] (S2)g (generated by Rv and pushing the negation)
IS2 = IS1 [ f:(GoodRC 0:4 u :BadT R 0:8)(S2); :GoodRC 0:9(S2)g (generated by Ru)
IS3 = IS2 [ f(GoodRC<0:4 t BadT R 0:8)(S2); GoodRC<0:9(S2)g (generated by R:)
IS40 = IS2[f(GoodRC<0:4(S2); GoodRC<0:9(S2)g or IS400 = IS2[f(BadT R 0:8)(S2); GoodRC<0:9(S2)g ( IS40; IS400 generated by Rt) IS50 = IS40 [ f(GoodRC<0:4(S2)g (generated by Rreduction on IS40) IS60 = IS50 [ f(GoodRC0(S2)g (generated by Rreduction with GoodRC0(S2)) The algorithm stops at the inference system IS60 because no more rule can be applied.
As there is no clash in IS60, the system is not inconsistent (without performing the inference system IS400). That is, it exists an interpretation such that: hT Boxexple; ABoxexplei j= :RQ(S2) We can deduce that the service S2 is not acceptable w.r.t. the required QoS RQ. Acceptance of the QoS of S1 The QoS of the service S1 is acceptable w.r.t RQ if:
hT Boxexple; ABoxexplei j= RQ(S1).
That is,
hT Boxexple; ABoxexple [ f:RQ(S1)gi is inconsistant where, T Boxexple = f g ABoxexple = fBadT R0:25(S1); GoodT R0:75(S1); GoodRC0:5(S1); BadRC0:5(S1)g The reasoning algorithm generates inference systems ISi by applying the propagation rules as follows:
The algorithm stops because all the inference systems contain a clash. Therefore, the system is inconsistent.
This means that the service S1 is acceptable w.r.t. the required QoS RQ. 6
In this paper, we proposed a high level support for describing the semantic QoS variations in order to react to the service behavior changes. It provides an appropriate adaptation and avoid the process to grind to a halt. The key element of our model is the probabilistic extension of DL proposed. This extension allows to express the QoS requirements and performs an e cient reasoning mechanism to let the system self healing. Our variant of description logic has a minimal set of logical constructors. It contains only concept terms and two constructors which are conjunction and disjunction. As future work, we plan to extend the proposed approach by providing more constructors.