BDD Mapping Clause Samples

BDD Mapping. ‌ We now have a formal representation of SLAs (Equation 4) and SLA depen- dencies (Equation 5). The gain in using BDDs lies in reduction. Through this process, a BDD becomes a canonical representation of the boolean function it describes, as proven in [1]. Therefore, a SLA described as a boolean function in the form of a BDD takes a unique, well-specified and minimal form, eliminating redundancy and allowing to make the mapping which describes SLA dependen- cies far more efficient than what it would be if we operated on complete graphs. Additionally, the canonical form of the SLAs allows objective evaluation and comparison for maximizing utility. The exact method to construct a BDD from a SLA depends on the format in which this SLA is originally expressed, and therefore it cannot be algorithmi- cally defined in a universal way. In the case of WS-Agreement we would use the Context and Service Description Terms as facts; Qualifying Conditions as conditions; Guarantee Terms as clauses; and Term Compositor Terms could be classified as either conditions or clauses. In fact, WS-Agreement’s Term Com- positor Terms are essentially boolean operators: All (AND), OneOrMore (OR), ExactlyOne (XOR). Using this pre-defined knowledge for such a specific SLA language, it is straightforward to implement a parser that can read the docu- ments and construct a (Reduced Ordered) BDD on-the-fly as described in [12] with the revised “APPLY” operation. To illustrate the reduced form of BDDs representing SLAs, we will use the example scenario from Section 4.1. As mentioned, Equations 2 and 3 represent the two example SLAs as boolean functions of the variables from Table 1. Then, assuming an ordering corresponding to the numbering of the variables, the two resulting BDDs would be as in Figure 3. x1 x2 x3 x4 x5 x6 x7 1 0 y1 y2 y3 y4 y5 1 0 (a) (b)