An Initial Approach to Explaining SLA Inconsistencies

An Initial Approach to Explaining SLA Inconsistencies? Carlos Müller, Antonio Ruiz-Cortés, Manuel Resinas Dpto. Lenguajes y Sistemas Informáticos ETS. Ingeniería Informática - Universidad de Sevilla (Spain - España) 41012 Sevilla (Spain - España) {cmuller, aruiz, resinas}@us.es Abstract An SLA signed by all interested parties must be created carefully, avoiding contradictions between terms, because their terms could carry penalties in case of failure. However, this consistency checking may become a challenging task depending on the complexity of the agreement. As a consequence, an automated way of checking the consistency of an SLA document and returning the set of inconsistent terms of the agreement would be very appealing from a practical point of view. For instance, it enables the development of software tools that make the creation of correct SLAs and the consistency checking of imported SLAs easier for users. In this paper, we present the problem of explaining WS- Agreement inconsistencies as a constraint satisfaction problem (CSP), and then we use a CSP solver together with an explanation engine to check the consistency and return the inconsistent terms. Furthermore, a proof-of-concept using Choco solver in conjunction with the Palm explanation engine has been developed. Keywords: Service Level Agreement, WS-Agreement, Consistency Checking, Debugging, Quality of Service. 1 Introduction SLAs consist of a set of terms that include information about functional features, non-functional guarantees, compensation, termination terms and any other terms with relevant information to the agreement. An agreement signed by all interested parties should be redacted carefully because a failure to specify their terms could carry penalties to the initiating or responding party. Therefore, agreement terms should be specified in a consistent way, avoiding contradictions between them. However, depending on the complexity of the agreement, this may become a challenging task. For instance, in a scenario in which a provider offers computing services to other organizations, an SLA could be agreed that includes non-functional attributes such as: the availability -in percentage-, the mean time between two consecutive requests of the service (MTBR) -in seconds-, and the ?This work has been partially supported by the European Commission (FEDER), Spanish Government under CICYT project Web-Factories (TIN2006-00472), and project P07-TIC-2533 funded by the Andalusian local Government. efficiency. Assuming that: Availability ranges between [90..100] , MTBR ranges between ∈[5..60] and Efficiency =Availability/MTBR. If the SLA includes a term obligating to guarantee Efficiency >20, at first sight the SLA is consistent. However the highest valid value for efficiency is 100/5=20, so this term cannot be satisfied. Therefore, a consistency checker that automatically checks the SLA for inconsistencies between its terms would be very appealing from a practical point of view. Furthermore, it is of interest not only to obtain an automated way of checking the consistency of an SLA document, but also to return an explanation if the document is inconsistent. This explanation is the set of inconsistent terms of the agreement. So, in the previous scenario we would obtain as debugging information that the inconsistent terms are: [(Efficiency >20),(Availability ∈[90..100]), (MTBR ∈[5..60]),(Efficiency =Availability/MTBR)], because they are inconsistent terms. This automated consistency checking enables the implementation of a software tool which makes the creation of correct SLAs and the consistency checking of imported SLAs easier for users. Nevertheless, as far as we know, the consistency of SLAs has been taken for granted by most authors. In this paper, we describe a mechanism to check and explain SLAs specified with WS-Agreement [2], which is a proposed recommendation of the Open Grid Forum (OGF) which provides a schema for defining SLAs and a protocol for creating them. To this end, we map the terms of a subset of the WS-Agreement document into a constraint satisfaction problem (CSP). Then we use the CSP as an input for a CSP solver with an explanation engine, which will return the set of inconsistent constraints. Finally, we trace back the constraints to the original SLA terms in order to give useful debugging information to users. As a proof-of-concept, we have developed a prototype of our consistency analyser using Choco solver [1] in conjunction with the Palm explanation engine [3]. This prototype is available for testing at http://www.isa.us.es in the tools section. This paper is structured as follows. Section 2 presents some background on constraint satisfaction problems and WS-Agreement. Section 3 details the subset of WS-Agreement which is used to explain the SLA inconsistencies in 3.1 and its mapping to CSP in 3.2. Section 4 describes our process to explain the WS-Agreement* iconsistencies. Section 5 shows our proof-of-concept. Section 6 reports on the related proposals. Finally, Section 7 details our conclusions and future work. 2 Preliminaries 2.1 Constraint Satisfaction Problems Constraint Satisfaction Problems [8] have been the object of research in Artificial Intelligence over the last few decades. A Constraint Satisfaction Problem (CSP) is defined as a set of variables, each ranging on a finite domain, and a set of constraints restricting all the values that these variables can take simultaneously. A solution to a CSP is an assignment of a value from its domain to every variable, in such a way that all constraints are satisfied simultaneously. These are some basic definitions of what a CSP is. Definition 1 (CSP). A CSP is a three–tuple of the form (V, D, C)where V6=∅ is a finite set of variables, D6=∅is a finite set of domains (one for each variable) and Cis a constraint defined on V. Consider, for instance, the CSP: ({a, b},{[0..2],[0..2]},{a+b < 4}) Definition 2 (Solution). Let ψbe a CSP, a solution of ψis whatever valid assignment of all elements in Vthat satisfies C. In the previous example, a possible solution is (2,0) since it verifies that 2+0<4. Definition 3 (Solution space). Let ψbe a CSP of the form (V, D, C), its solution space denoted as sol(ψ)is made up of all its possible solutions. A CSP is satisfiable if its solution space is not empty. sol(ψ) = {S| ∀si·si∈S⇒C(si) = true} In the previous example there are eight solutions. The only assignment that does not satisfy a+b < 4is (2,2). Nevertheless, if we replace the constraint with a+b < −1, then the CSP is not satisfiable. In many real-life applications, if a CSP has no solution, we would like to know which set of constraints are responsible for this situation. This can be done by interpreting the CSP as an explanation problem. Definition 4 (Explanation problem). Let be a CSP of the form (V, D, C) with an empty solution space: sol() = ∅. It is considered to be an explanation problem if its objective is to find a set of constraints C0⊂Cthat cannot be satisfied. Definition 5 (Explanations). Let be an explanation problem, the resulting set of inconsistent constraints C0are known as the explanations for the problem. They are divided into two parts: a subset of the original set of constraints C0⊂C and a subset of decision constraints introduced so far in the search of solutions (dc1, ..., dck). As defined in [3], a contradiction explanation, also known as “nogood” [7], is a subset of the constraints of the problem that, left alone, leads to a contradiction (no feasible solution contains a nogood). The previous CSP example, with the constraint replaced with a+b < −1, is not satisfiable, and by interpreting it as an explanation problem the explanation engine should obtain as the set of inconsistent constraints: [(a+b < −1),(a >= 0),(b >= 0)] 2.2 WS-Agreement in a Nutshell WS-Agreement specifies an XML-based language and a protocol for advertising the capabilities and preferences of service providers, and creating agreements based on agreement offers. The structure of an agreement in WS-Agreement comprises: – Name: it identifies the agreement and can be used for reference. – Context: it includes information such as the name of the parties and their roles as initiator or responder in the agreement. Additionally, it can include other important information for the agreement. – Terms: they are grouped by the following term compositors: ExactlyOne, OneOrMore, or All. The two main types of terms are: •Service terms: they provide service information by means of: ∗Service description terms and service references, which includes information to instantiate or identify the services and operations involved in the agreement. ∗Service properties, which includes the measurable properties that are used in expressing guarantee terms. They consist of a set of variables whose values can be established inside the service description term, and whose domain can be established by the metric attribute pointing to an external XML document. •Guarantee terms: they describe the service level objectives (SLO) agreed by a specific obligated party, either using a free-form element or using a key performance indicator. It also includes the scope of the term (e.g. if it applies to a certain operation of a service or the whole service itself), and a qualifying condition that specifies the validity condition under which the term is applied. Figure 1 depicts an example of a WS-Agreement between a computing services provider and a consumer. It defines several service properties whose domain is specified in an external XML document (depicted in Figure 2). Note that other XML documents, such as an XML Schema definition, could have been used instead. The service properties defined in the WS-Agreement document of Figure 1 are the following ones: –the availability -integer form 1 to 100- –the mean time between two consecutive requests of the service (MTBR) - integer greater than 1- –the mean time to response (MTTR) -integer greater than 1- –the initial cost for the service (InitCost) -integer greater than 1- –the final cost for the service (Cost) -integer greater than 1- –the increase of the cost if the MTBR < 10 (ExtraMTBRCost) -integer greater than 1- –the increase of the cost if the MTTR < 05 (ExtraMTTRCost) -integer greater than 1- We have extracted the following information from the SLA: –MTBR ∈[5..60]. –MTTR ∈[1..10]. –If MTBR >= 10 Then Availability ∈[90..100]. –If MTBR < 10 Then Availability ∈[95..100]. –Cost = InitCost + ExtraMTBRCost + ExtraMTTRCost. –If MTBR < 10 Then ExtraMTBRCost = 15. –If MTTR < 05 Then ExtraMTTRCost = 15. –If MTBR >= 10 and MTTR >= 05 Then ExtraMTBRCost = 0 and ExtraMTTRCost = 0. 3 Mapping WS-Agreement onto CSP 3.1 WS-Agreement* as a subset of WS-Agreement Due to the flexibility and extensibility of WS-Agreement, we focus in this paper on a subset of WS-Agreement that is a bit less expressive than WS-Agreement, but still useful for our purpose. The subset of WS-Agreement is called WS- Agreement*. A WS-Agreement* document (α) is composed of the following elements: –Service properties must define all variables that are used in the guarantee terms. In addition, attribute metric of the variables is mandatory. This attribute must point to another XML document or schema that provides the data type and a general range of values (δ) for each service property. Figure 2 shows an example of an ad-hoc XML document that includes the mentioned information for service properties of the example of Figure 1, although other XML documents could be used. XML node Location (λυ) of each variable establishes the specific XML node inside the service description term where it is defined the value for such variable (value(λυ)). –Terms (T) can be composed using the three term compositors defined in WS-Agreement: All (), ExactlyOne (⊗), and OneOrMore (⊕). –Service description terms can be included but only to impose specific value definitions for each variable (υ) of service properties. Other service description terms could be added but they are ignored when checking the SLA consistency. –Guarantee terms (γ) can be included. Both qualifying condition (κ) and the SLOs (σ) must be defined as constraints on the variables defined in the service properties, and only to those variables (i.e. κ∈Cand σ∈C). The scope of a guarantee term cannot be established, but all guarantee terms apply to the whole service. Note that, although WS-Agreement* is not as expressive as WS-Agreement, it does allow for the expression of complex agreements. For instance, the agreement depicted in Figure 1 is compatible with WS-Agreement*. Thus, we can formally define an agreement specified with WS-Agreement* as follows: <Agreement ’’id=exampleScenario’’> <Context> ... </...> <All> <ServiceDescriptionTerm Name=’’ComputingService’’> <...> ... </...> <InitCost> 20 </...> ... </...> </...> </ServiceDescriptionTerm> <ServiceProperties> ...<Variable name=’’Availability’’ metric=’’metricXML:Availability’’> <Location> \\Availability </Location> </Variable> <Variable name=’’MTBR’’ metric=’’metricXML:MTBR’’> <Location> \\MTBR </Location> </Variable> <Variable name=’’MTTR’’ metric=’’metricXML:MTTR’’> <Location> \\MTTR </Location> </Variable> <Variable name=’’InitCost’’ metric=’’metricXML:InitCost’’> <Location> \\InitCost </Location> </Variable> <Variable name=’’Cost’’ metric=’’metricXML:Cost’’> <Location> \\Cost </Location> </Variable> <Variable name=’’ExtraMTBRCost’’ metric=’’metricXML:ExtraMTBRCost’’> <Location> \\ExtraMTBRCost </Location> </Variable> <Variable name=’’ExtraMTTRCost’’ metric=’’metricXML:ExtraMTTRCost’’> <Location> \\ExtraMTTRCost </Location> </Variable>... </ServiceProperties> <GuaranteeTerm Name=’’MTBRDomain’’> <SLO> MTBR >= 5 and MTBR <= 60 </...> </GuaranteeTerm> <GuaranteeTerm Name=’’MTTRDomain’’> <SLO> MTTR >= 1 and MTTR <= 10 </...> </GuaranteeTerm> <GuaranteeTerm Name=’’CostDefinition’’> <SLO> Cost = InitCost + ExtraMTBRCost + ExtraMTTRCost </...> </GuaranteeTerm> <ExactlyOne> <GuaranteeTerm Name=’’LowerAvailabilityDomain’’> <QualifyingCondition> MTBR >= 10 </...> <SLO> Availability >= 90 and Availability <= 100 </...> </GuaranteeTerm> <GuaranteeTerm Name=’’HigherAvailabilityDomain’’> <QualifyingCondition> MTBR < 10 </...> <SLO> Availability >= 95 and Availability <= 100 </...> </GuaranteeTerm> </ExactlyOne> <OneOrMore> <GuaranteeTerm Name=’’MTBRIncrement’’> <QualifyingCondition> MTBR < 10 </...> <SLO> ExtraMTBRCost = 15 </...> </GuaranteeTerm> <GuaranteeTerm Name=’’MTTRIncrement’’> <QualifyingCondition> MTTR < 05 </...> <SLO> ExtraMTTRCost = 15 </...> </GuaranteeTerm> <GuaranteeTerm Name=’’CheaperCost’’> <QualifyingCondition> MTBR >= 10 and MTTR >= 05 </...> <SLO> ExtraMTBRCost = 0 and ExtraMTTRCost = 0 </...> </GuaranteeTerm> </OneOrMore> </All> </Agreement> Figure 1. Example of a WS-Agreement document with all kinds of compositors. <metricXML> <Availability type=’’integer’’ min=’’1’’ max=’’100’’/> <MTBR type=’’integer’’ min=’’1’’ max=’’unbounded’’/> <MTTR type=’’integer’’ min=’’1’’ max=’’unbounded’’/> <InitCost type=’’integer’’ min=’’1’’ max=’’unbounded’’/> <Cost type=’’integer’’ min=’’1’’ max=’’unbounded’’/> <ExtraMTBRCost type=’’integer’’ min=’’1’’ max=’’unbounded’’/> <ExtraMTTRCost type=’’integer’’ min=’’1’ max=’’unbounded’’/> </metricXML> Figure 2. Ad-hoc XML document for the variable domains of Figure 1. Definition 6 (A WS-Agreement* document). A WS-Agreement* document αis a set of variables υi, variable domains δi, and a set of terms T, including service description terms, guarantee terms and terms compositors as follows: α= (υi, . . . , υn, δi, . . . , δn, T1, . . . , Tm),where Ti=            λυ γ Ti1. . . Tik Ti1⊗. . . ⊗Tik Ti1⊕. . . ⊕Tik            3.2 Mapping WS-Agreement* onto CSP Figure 3 depicts the mapping (µ) of a WS-Agreement* document (α) onto an equivalent CSP, (ψα). The variables (υ) defined inside the service properties are the CSP variables; the variable domains (δ) included in the document specified by the metric attribute are the CSP variable domains; and the constraints from the service description terms (λυ), guarantee terms (γ) and term compositors (as a logic “AND”, ⊗as logic “XOR”, and ⊕as logic “OR”) are the CSP constraints. Thus, in general, our WS-Agreement* to CSP mapping can be defined as follows: Definition 7 (Mapping an WS-Agreement* to CSP). The mapping (µ: α→ψ) of a WS-Agreement* document (α) to a CSP (ψ) can be defined as follows: µ(α) = µ(υ1, . . . , υn, δ1, . . . , δn, T1, . . . , Tm) = = ({υ1, . . . , υn},{δ1, . . . , δn},{µT(T1, . . . , Tm)}) = ψα where µT:T→Cis a mapping function of terms into constraints defined as follows: µT(T)≡            υ=λυif Tis a service description term (λυ) σif Tis a guarantee term without qualifying condition (γσ) κ⇒σif Tis a guarantee term with a qualifying condition (γσ,κ) Vk i=1 µT(Ti)if Tis a composite term (T1. . . Tk) Vk i=1 µT(Ti)⇔(Vk j=1\j6=i¬µT(Tj)) if Tis a composite term (T1⊗. . . ⊗Tk) Wk i=1 µT(Ti)if Tis a composite term (T1⊕. . . ⊕Tk)            <Agreement> <or or > <ServiceProperties> …<variable name=‘’ 1’’ metric=‘‘metricXML:δ1’’> <location> 1 </…> </variable> … …<variable name=‘‘ n’’ metric=‘‘metricXML:δn’’> <location> n </…> </variable> … </ServiceProperties> <ServiceDescriptionTerm ( 1)> …< 1> value( 1)</ 1> … <n> value( n)</ n> … </ServiceDescriptionTerm> <GuaranteeTerm name=‘‘ 1’’ ( 2)> <SLO> </SLO> </GuaranteeTerm> <GuaranteeTerm name=‘‘ m’’ ( k)> <QualifyingCondition> </QualifyingCondition> <SLO> </SLO> </GuaranteeTerm> </or or > </Agreement> <<WS-Agreement*>> <metricXML> <δ1type=‘‘…’’ min=‘‘…’’ max=‘‘…’’> … <δntype=‘‘…’’ min=‘‘…’’ max=‘‘…’’> </metricXML> <<metricXML>> CSP variables ={ (Equivalent CSP) CSP variable domains CSP constraints 1, …, n, δ1, …, δn, 1, …, m (i)≡ i = value( i) (1)≡ i≡ i (m)≡ (or or ) δi≡ δi { { { { { ( ( Figure 3. Summary of WS-Agreement* to CSP mapping. Using this mapping, the ψαfor the example of Figure 1 is mapped as follows: ψα= ( { Availability, MTBR, MTTR, InitCost, Cost, ExtraMTBRCost, ExtraMTTRCost }, {[1. . . 100 ], [ 1 . . . ∞), [ 1 . . . ∞), [ 1 . . . ∞), [ 1 . . . ∞), [ 1 . . . ∞), [ 1 . . . ∞), }, { InitCost = 20, MTBR ≥5 and MTBR ≤60, MTTR ≥1 and MTBR ≤10, Cost = InitCost + ExtraMTBRCost + ExtraMTTRCost, ((MTBR ≥10) ⇒(Availability ≥90 and Availability ≤100)) ⇔ ⇔ ¬ ((MTBR < 10) ⇒(Availability ≥95 and Availability ≤100)), (MTBR < 10 ⇒ExtraMTBRCost = 15) ∨ ∨(MTTR < 5 ⇒ExtraMTTRCost = 15) ∨ ∨((MTBR ≥10 and MTTR ≥5) ⇒ExtraMTBRCost = 0 and ExtraMTTRCost = 0) } ) The following table denotes constraints mapped from the example of Figure 1. Example term (Ti) name Equivalent mapped (µT(Ti)) InitCost InitCost = 20 MTBRDomain MTBR >= 5 and MTBR <= 60 MTTRDomain MTTR >= 1 and MTTR <= 10 CostDefinition Cost = InitCost + ExtraMTBRCost + ExtraMTTRCost LowerAvailabilityDomain (MTBR ≥10) ⇒(Availability ≥90 and Availability ≤100) HigherAvailabilityDomain (MTBR < 10) ⇒(Availability ≥95 and Availability ≤100) MTBRIncrement (MTBR < 10) ⇒(ExtraMTBRCost = 15) MTTRIncrement (MTTR < 5) ⇒(ExtraMTTRCost = 15) CheaperCost (MTBR ≥10 and MTTR ≥5) ⇒ (ExtraMTBRCost = ExtraMTTRCost = 0) ExactlyOne (LowerAvailabilityDomain ⇔ ¬ HigherAvailabilityDomain) ∧ (HigherAvailabilityDomain ⇔ ¬ LowerAvailabilityDomain) OneOrMore MTBRIncrement ∨MTTRIncrement ∨CheaperCost All InitCost ∧MTBRDomain ∧MTTRDomain ∧ ∧CostDefinition ∧ExactlyOne ∧OneOrMore Table 1. Mapping example terms to CSP constraints 4 Checking and Explaining WS-Agreement* Inconsistencies Checking the consistency of WS-Agreement documents involves both syntactic and semantic checking. The former involves checking the document against the WS-Agreement XML Schema. The latter, however, is harder to check on and is thus the focus of this paper. Figure 4 depicts our consistency checking process. In this scenario, it is imposed by a human error, an MTBR value definition inside the service description term with a value of 61. Thus, the ψαwould not be satisfiable by the MTBR domain definition. As depicted in Figure 4, we propose to use the agreement specified with WS-Agreement* in conjunction with the XML document which defines the variables metrics as the two inputs for a mapping component which implements the mapping defined in section 3.2. Once the agreement is mapped to a CSP, the explanation engine of the CSP explainer component will obtain whether the SLA document is consistent or not. In the latter case, the component sends to a tracing component the explanations for the problem. In this case, the explanations for the problem are MT BR: [MTBR = 61; MTBR ≥5 and MTBR ≤60]. The tracing component converts the explanations into the equivalent inconsistent original terms in order to give useful information to users. This is done by naming constraints mapped from an SLO as the name of the guarantee term which includes it; and if the constraint was mapped from a value definition inside a service description term, we name it “SDT”, concatenate with the name of the variable. Then, the previous explanation for MTBR would be traced by us to the inconsistent term “SDTMTBR” constraint, showing that it is the MTBR