Repositorio Institucional de Documentos

2013 27 Diego Carmelo Pérez Palacín Extra Functional Properties Evaluation of Self-managed Software Systems with Formal Methods Departamento Director/es Informática e Ingeniería de Sistemas Merseguer Hernáiz, José Javier Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Diego Carmelo Pérez Palacín EXTRA FUNCTIONAL PROPERTIES EVALUATION OF SELF-MANAGED SOFTWARE SYSTEMS WITH FORMAL METHODS Director/es Informática e Ingeniería de Sistemas Merseguer Hernáiz, José Javier Tesis Doctoral Autor 2013 Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Extra Functional Properties Evaluation of Self-managed Software Systems with Formal Methods Diego P´ erez Palac´ ın TESIS DOCTORAL Departamento de Inform´ atica e Ingenier´ ıa de Sistemas Universidad de Zaragoza Supervisor: Jos´ e Javier Merseguer Hern´ aiz December 2012 Preface Today software applications are often intended to operate in dynamic contexts. These dynamic contexts can be expressed in terms of changes in the application execution environment, changes in the application requirements, changes in the workload, or changes in anything the software can perceive. These software applications are not restricted to a single domain but dynamic contexts can be found in many software domains such as: embedded systems, service-oriented architectures, clusters for high performance computing, mobile devices and networking software. The existence of dynamic contexts discourages engineers from the development of software that is not able to change, in some way, its execution to leverage the current context at any moment. Then, with the intention of satisfying requirements, the software must include mechanisms to change its configuration. Nevertheless, since context changes are frequent and go through many devices, human intervention to manually change the software configuration is not a feasible solution. To face this challenge, the Sofware Engineering community came up with new paradigms to enable the development of software that deals with dynamic contexts in an automatic manner; for example Autonomic Computing and self-* software approaches. In these approaches the software manages the mechanisms to change the configuration, without requiring human intervention. Among the most general manners to refer to self-* software are the terms self-adaptive and self-managed software. An essential aspect of self-adaptive software is to plan its adaptations. Adaptation plans determine how the system will adapt and the suitable moments to trigger these adaptations. There is a vast set of situations for which self-adaptivity is a solution. One of these situations is to keep the system satisfying its extra functional requirements, such as Quality of Service (QoS) and energy consumption. This thesis investigates these situations. One of the contributions of this thesis is to settle QoSand energy-aware self-adaptive systems into an architecture. For this purpose, a 3-layer architecture of reference for selfmanaged systems guides our research. The goodness of using a reference architecture is that it easily shows up new challenges for the design of this kind of systems. Of course, adaptation planning is one of the activities that the architecture considers. Another contribution of this thesis is to propose methods to create adaptation plans. Formal methods play an essential role in this activity since they help to study extra functional properties of the system under different configurations. Markovian Petri nets are used for this analysis. Once the adaptation plan has been created, we also investigate the evaluation of the QoS and energy consumption of self-adaptive systems with formal methods. Thence, we 3 contribute to the QoS analysis community -whose research cares about analysis of software systems quality propertiesby investigating a particularly new and complex type of software systems. To carry out this analysis it is required to model dynamic changes in the context, for which a variety of formal methods can be used: Markov modulated Poisson processes to estimate the dynamic workload parameters, and hidden Markov models to predict the environment state. These models were used together with Petri nets to evaluate and obtain results about QoS and energy consumption of self-adaptive systems. During the research work, we advertised that adaptability is a system property not as easily quantifiable as energy consumption or QoS properties -such as the response time. Research was done in this direction and, as a result, this thesis contributes to quantify the adaptability by proposing a set of adaptability metrics for service-based systems. Moreover, we studied whether there is a correlation between the adaptability of a system and other of its extra functional properties values. For achieving these contributions, this thesis makes an intensive use of models and model transformations; task for which best practices of the Model Driven Engineering (MDE) research field are followed. The research work of this thesis in the MDE field resulted in: enhancement of the modeling power of an already proposed software modeling language, and transformation methods from two software modeling languages to stochastic Petri nets. Contents 1 Introduction 1 1.1 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 I Evaluation of Self-managed Systems 7 2 Reference Architecture for Self-managed Systems 9 2.1 Enabling software to face the unknown . . . . . . . . . . . . . . . . . . . . . 11 2.2 Self-adaptive systems manage ignorance . . . . . . . . . . . . . . . . . . . . 12 3 Self-adaptation for Performance Engineering: Goal Management 15 3.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 3-Layer architecture for open-world software . . . . . . . . . . . . . . . . . 16 3.2.1 Component control . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2.2 Change management . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.3 Goal management . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Generation of strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4.1 Strategy generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.6 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4 Self-adaptation for Performance Engineering: Change Management 31 4.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 A formal model for SOA providers . . . . . . . . . . . . . . . . . . . . . . . 32 4.2.1 Hidden Markov models . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2.2 HMM representation of SOA providers . . . . . . . . . . . . . . . . 34 4.3 State prediction and configuration adaptation . . . . . . . . . . . . . . . . . 35 4.3.1 Prediction of the provider state . . . . . . . . . . . . . . . . . . . . . 35 4.3.2 Adaptations based on state predictions . . . . . . . . . . . . . . . . . 36 4.4 Integrating the adaptive configurations into an architectural solution . . . . . 40 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.6 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 i ii 5 Self-adaptation for Energy Conservation 43 5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.3 Workload modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.4 Energy modeling and analysis . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.5 Performance and energy trade-off . . . . . . . . . . . . . . . . . . . . . . . 54 5.5.1 Generation of basic-plan . . . . . . . . . . . . . . . . . . . . . . . . 54 5.5.2 Reconfiguration rate mitigation . . . . . . . . . . . . . . . . . . . . 55 5.5.3 Petri net model of a plan . . . . . . . . . . . . . . . . . . . . . . . . 58 5.5.4 The Petri net for trade-off evaluation . . . . . . . . . . . . . . . . . . 59 5.6 Deployment and evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.6.1 Evaluation framework . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.6.2 Example of evaluation: relay mail server . . . . . . . . . . . . . . . 62 5.7 Experimenting with variable workload . . . . . . . . . . . . . . . . . . . . . 65 5.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.9 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6 Workload Modeling for Self-adaptive Software 71 6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6.2 MAP’s and MMPP’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 6.2.1 MMPP fitting from a workload trace . . . . . . . . . . . . . . . . . . 74 6.2.2 GSPN workload model . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.3 Modeling transient time between states . . . . . . . . . . . . . . . . . . . . . 78 6.3.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.3.2 Setting parameters of workload model . . . . . . . . . . . . . . . . . 78 6.3.3 GSPN model for the transient time . . . . . . . . . . . . . . . . . . . 81 6.4 Comprehensive workload model . . . . . . . . . . . . . . . . . . . . . . . . 83 6.5 Experimental analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.5.1 Results discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.7 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 7 Measuring and Correlating System Adaptability 91 7.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 7.2 Architectural adaptability quantification . . . . . . . . . . . . . . . . . . . . 92 7.2.1 Architectural assumptions . . . . . . . . . . . . . . . . . . . . . . . 92 7.2.2 Adaptability metrics . . . . . . . . . . . . . . . . . . . . . . . . . . 94 7.3 Relating adaptability to a system quality . . . . . . . . . . . . . . . . . . . . 96 7.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 7.4.1 Computation of system qualities . . . . . . . . . . . . . . . . . . . . 102 7.4.2 Relation of adaptability to availability and cost . . . . . . . . . . . . 104 7.5 Relating quality requirements . . . . . . . . . . . . . . . . . . . . . . . . . . 106 7.5.1 Graphical representation . . . . . . . . . . . . . . . . . . . . . . . . 107 7.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.7 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 1.1. Outline 5 Stochastic Petri Nets (GSPN) [AMBC+95]. In turn, the latter investigates the middle layer, which is in charge of deciding whether to adapt the system, and it uses the theories of Hidden Markov Models (HMM). In Chapter 5 the 3-layer reference architecture is instantiated for energy savings. Again, GSPNs are utilized to create the adaptation plans. In Chapter 6, we identify a weakness in the modeling of bursty workloads and we investigate an accurate model for its representation based on GSPNs. Finally, in Chapter 7 we research the quantification of adaptability property; being the outcome of that research twofold: a set of metrics to measure the adaptability of software systems and a study about the correlation between adaptability values and QoS values. •The second part comprises an introduction and two chapters that accomplish investigation in model to model transformations. The introduction presents the motivation and benefits of MDE paradigm. It shows up a weak point of applying MDE from software design to formal models and also explains the proposal of the research community to solve the weakness. After, in Chapter 8 we follow the community proposal by creating a translation theory between the Core Scenario Model (CSM) and GSPN and a tool that implements that theory. In Chapter 9, we extend the modeling power of a Dynamic Kernel Language for PErformance and Reliability analysis (D-KLAPER) to represent reactive software (most self-adaptive systems are also reactive systems). In that chapter, we propose the theory to translate UML state machine diagrams into the extended D-KLAPER, and to translate the extended D-KLAPER into GSPN. Finally, it is shown an example regarding the use of D-KLAPER or performance performance evaluation of service-based software systems. •Chapter 10 presents the conclusions of this thesis. It summarizes the contributions and identifies future work and research directions. 6 1. Introduction Part I Evaluation of Self-managed Systems 7 Chapter 2 Reference Architecture for Self-managed Systems Understanding all the processes under self-adaptive systems execution is complex. Also its development has some intrinsic characteristics that make it a process harder than the development of non-adaptive systems. To relieve developers of the most general thinking about the software construction, there have been proposed some frameworks for self-adaptive software design. These frameworks include the general tasks that self-adaptive software has to execute. Four of the most important frameworks proposed are: MAPE-K structure of an autonomic element [KC03] (Monitor, Analyze, Plan, Execute, Knowledge), CADA autonomic control loop [DDF+06] (Collect, Analyze, Decide, Act), the adaptation methodology in [OGT+99] and a three-layered architectural approach for self-managed systems [KM07, KM09]. The work in this thesis uses the three-layered architectural approach in [KM07, KM09]. This architecture was not built from scratch but based on solid pillars. It was inspired by architectural approaches already in the robotic research area -field which holds a large experience in the construction of autonomous systems-, and concretely on the Gat’s architectural description in [GBMP97]. From that starting point, we tuned the concepts in the three layer architecture for selfmanaged systems. Our purpose is the construction of software whose adaptations are triggered to keep satisfied extra functional requirements -such as QoS and energy consumptionunder different execution contexts. The general view of the architecture is shown in Figure 2.1. A layer by layer description is in next paragraphs, while in next chapters we propose fine-grained instances of this general view for each one of the challenges dealt with in this thesis. Component control This layer is made of the components that accomplish the software application functionality. It also includes sensors and monitors that track the status of both the system and environment. Some examples of monitored elements can be: component performance, service providers performance, service providers availability, system load, hardware 9 10 2. Reference Architecture for Self-managed Systems <<input>> Component Adaptation Manager Actuators Software Application and Infrastructure Sensors and Monitors Plan Adaptation <<document>> management Change Goal management Plan Generator Models Adaptation <<input>> <<input>> <<input>> <<document>> Models Environment System <<document>> <<document>> Adaptation Plan Environment Updated Report Plan Request Environment status System status Change actions Extra functional goals <<output>> control Figure 2.1: General architecture following the 3-layer framework for self-managed systems status (e.g,. switched on, switched off, broken device). This sensed status information is sent to the upper layer. Besides, this layer includes actuators, which are the elements that effectively adapt the system execution. These actuators operate when they receive change actions from its upper layer. Some examples of elements onto which an actuator can operate are: software components with multiple execution configurations, replaceable software components, and hardware infrastructure. The software application and infrastructure comprises all the elements that allow the software to run its functionality, in which are included the monitored elements (i.e., those for which there is a sensor connected) as well as the managed elements (i.e., those for which there is an actuator connected). Change management The objective of this layer is to keep the system executing in the most appropriate configuration to satisfy application’s goals. To achieve this objective, the main task of this layer is to decide change actions to adapt the system based on the status reports received from the lowest layer. The software entity that executes the decision task is called adaptation manager. To perform this decision quickly, it has stored a pre-computed adaptation plan that contains information to guide the adaptations. In case that, in any point in time, the stored adaptation plan does not suffice to cope with the reported status, this layer can request for a new plan to the uppermost layer. To obtain a new adaptation plan that 2.1. Enabling software to face the unknown 11 considers the current execution environment, this layer informs the uppermost layer about what it was found in the environment. This notification is done through an environment updated report. Moreover, this layer can also receive a new adaptation plan that has been proactively created by the uppermost layer; i.e., the adaptation manager had not made any request for a new plan. Goal management The objective of this layer is to produce adaptation plans that allow the system to satisfy its extra-functional goals under changing environments. The software entity that produces these plans is called adaptation plan generator and its execution requires information regarding: extra-functional goals to achieve, application models (e.g., software behavioral models and hardware platform models) and environment models. All these models are subject to change, and a change in a model can make the created adaptation plan no longer suitable. Therefore, after a change in the models, it should be triggered the generation of a new adaptation plan and its subsequent delivery to the change management layer. For example, changes in environment models are done when an environment updated report is received from the lower layer. 2.1 Enabling software to face the unknown The type of self-adaptive systems investigated in this thesis have to face unknown situations and unpredictable environments. When software execution environment changes, the first challenge for the system is to realize that something in the environment has actually changed. This environmental change awareness is not always an easy task, and it becomes more difficult for slight environmental changes or when the change happens slowly. If the environment change is realized, next step for the software is to acquire knowledge about what the new execution environment is; i.e., not only sensors reports indicate that something has changed in the environment but sensors reports indicate that the execution environment has changed from context “a” to context “b”. After, software decides either to continue in the same configuration (in case that the current configuration still works well in the new environment) or change to another one (labour of the intermediate layer of the presented architecture). If it is decided to change, software has to find out the new configuration. For cases in which the occurrence of the new environment is predictable beforehand, the software can have stored a set of pre-computed reconfiguration actions to take when the environmental modification takes place. These actions are stored in an adaptation plan, which can guide the adaptations between a set of environment states. If the environment is new and non-predictable, then the adaptation plan followed by the software may not contain guides to adapt the configuration. To face the unknown situation in this case, a new adaptation plan can be requested. This new plan will contain the appropriate adaptation actions for changing from/to this new environment. Thus, in this case the labour of the uppermost layer of the architecture helps to face the unknown. However, not in every case the unknown situation can be solved; maybe because of lack of information about the environment, maybe because of lack of ideal decision methods. In this cases, software is executing in ignorance of its environment. In next subsection it is 12 2. Reference Architecture for Self-managed Systems described how the software can manage that unavoidable ignorance. 2.2 Self-adaptive systems manage ignorance Self-adaptive software that changes its configuration in response to unexpected changes in its execution environment should be conscious of the fact that its sensors and prediction algorithms are not perfect, and then it may not have the knowledge at every time about what the real environment and its best configuration are. To classify different types of lacks of knowledge of self-adaptive software, we describe in the next paragraphs a comparison between the human orders of ignorance and learning processes and the software one. We work upon the five orders of human ignorance proposed in [Arm00], and we reason in which level our self-adaptive system is. The five levels of ignorance in [Arm00] are briefly described as: - 0th order of ignorance. Lack of ignorance, i.e., knowledge. - 1st order of ignorance. Lack of knowledge. The subject lacks of knowledge about something but he/she/it is aware of such lack. - 2nd order of ignorance. Lack of knowledge and lack of awareness. The subject does not know that he/she/it does not know. - 3rd order of ignorance. Lack of process to find out the lack of awareness. The subject does not have any way to move from not knowing that he/she/it does not know to, at least, be aware of his/her/its ignorance. - 4th order of ignorance. Meta ignorance. Ignorance about orders of ignorance. Self-adaptive systems should have knowledge about its execution environment. Nevertheless, since that fact cannot be always ensured, they should at least be able to manage its ignorance. Then, the orders of ignorance can be applied to them. From the information coming from sensors, they create knowledge of their environment and they decide what the execution environment is. In case that the decision regarding the execution environment comes up with a different environment than the currently used, the next step involves either a selection of the adaptation actions -in case that the second layer is ready to cope with the new environment characteristicsor a deliberation about a long-term adaptation plan -in case that the uppermost layer is invoked. During software execution, the system is in the 0th order of ignorance when its last decision about the execution environment guessed correctly the real environment and the real environment has not changed since then. During the first moments after an environmental change -e.g., context changes from ato b-, system stands on the second order of ignorance; i.e., it does not know that it does not know the actual environment because it has not received information from sensors yet. As soon as new information from sensors arrives and the second layer realizes that such information does not fit with the expected values for environment a, system changes from 2nd to 1st order of ignorance; i.e., now it does know that it does not know what the current environment 2.2. Self-adaptive systems manage ignorance 13 is (b). It will remain in that state until it makes a decision about what the new execution environment is. If the decision is successful (it decides that the new environment is b), the order of ignorance comes back to 0th again. On the contrary, if it decides erroneously the order of ignorance goes to 2nd. At least two factors can make the system move to the third order of ignorance: when the change refers to an environmental characteristic that is not measured by any system sensor in the bottom layer, or when the deliberation algorithms in the uppermost layer are not correct. In the former case, sensors are not monitoring the appropriate environmental properties and then they will continue reporting the same data. Since sensors are the primary exposed mechanism to unveil that something has changed, the system will not know that it does not know the actual environment and it will not have any other mechanism to become aware of such ignorance. In the latter case, which happens when the uppermost layer has been invoked, the system does its best to unveil the current environment and what properties it can expect from it. To perform this task, it executes the deliberative algorithms that generate the expected execution environments and an adaptation plan between them. However, these algorithms are not adaptive (at least, in this thesis is not considered that such part of code can evolve). Therefore, a wrong algorithm will come up with unsuitable adaptations plans and the adaptation manager in the second layer will be clueless when it has to decide adaptations. Going into the latter case in depth, now the ignorance is not referring to “system does not know that the actual environment is not the same as its expected environment” as it happened in the previous cases, but to “system does not know that its set of expected environments and adaptations between them are not correct”. However, there can be devised a manner in which the system can belong to the 2nd order of ignorance for this case. This manner is: providing the software with self-evaluating techniques of its expected behavior and comparing the self-evaluation results with the actual ones. If the expected results do not match up with the real ones, the software can activate a warning stating that the last adaptation plan did not work as expected. In this case, another adaptation plan is proactively created by the third layer. Nevertheless, if subsequent self-evaluations show that results do not match for a sequence of plans, the system can infer that it does not know how to generate suitable adaptation plans, and it can raise an alarm notifying humans of that fact. So, having self-evaluating and reporting mechanisms, the system can keep 2nd order of ignorance instead of being on the 3rd one for this case, but it will require human intervention (i.e., to be installed a correct algorithm for the deliberation activity) to eventually move to 0th again. Probabilistic environment decision The decision about the current environment may not be straightforward. Indeed, the reported values from sensors may fit in more than one execution environment. In this case, starting from sensed information, the generation of knowledge can consist of mathematical treatments of that information. This mathematical treatment can, for example, obtain results as: statistical indicators about the expected values of the environment, their temporal variance, confidence level in the knowledge estimation and confidence level on the adaptation decisions. Software with probabilistic environment decisions manages its execution from the 1st order of ignorance; i.e., it always knows that it might be executing under an unknown en- 14 2. Reference Architecture for Self-managed Systems vironment. This software does not stand on ideal 0th order of ignorance but it is also less likely to move to the 2nd order. The reason for not being on the 0th order is that, even if a decision about configuration change is right, the system will always consider the probability of being wrong; i.e., the 1st order of ignorance in the sense it knows that it cannot be completely sure of its environment. Regarding the second statement, since it always manages a probability of having decide wrongly, it is obviously aware of its possible ignorance when facing adaptation decisions, which avoids it entering into the 2nd order of ignorance when environment changes. Yet the system can move to the 2nd order of ignorance if it runs incorrect deliberation algorithms and it is provided with self-evaluating mechanisms. 3.4. Example 21 GSPN for Nodesand Nodet(lines 6-9). A simple example of SetConfLevel will be given in Section 3.4. These algorithms have been implemented in the work in [Fra10]. Algorithm 3.1 Strategy generation Require: From Goal Management Layer: System Workflow (AD), Performance Goal (PerfGoal) From Change Management Layer: Components with their timing specification (CD,TT) Ensure: A New Strategy (and a possible warning meaning that the PerfGoal is not achieved) {Initialization} 1: set G=�N, E�:N=∅ {nodes},E=∅ {edges} {Create Initial Node} 2: N0←CreateNode(AD,CD,TT,null,null) 3: set Nodes =∅ 4: Nodes =Nodes ∪N0 5: while Nodes �=∅do 6: Nodes←ExtractOneNode(Nodes) 7: AlreadyCreated ←CheckNode(N, Nodes) 8: if not AlreadyCreated then 9: N←N∪Nodes {Create Nodesadjacent nodes} 10: for all k∈[1..K]do 11: Nodet←CreateNode(AD,CD,TT,k,Nodes) 12: AlreadyCreated ←CheckNode(N, Nodet) 13: if not AlreadyCreated then 14: Nodes ←Nodes ∪Nodet 15: end if {Create edge from Nodesto Nodet} 16: Edge ←CreateEdge(Nodes,Nodet,k,TT) 17: E←E∪Edge 18: end for 19: end if 20: end while 21: E=E∪CreateWayBackEdges(G,TT) 22: return ¡G, AnalyseStrategy(G,PerfGoal,CD,TT)¿ 3.4 Example We exemplify the algorithm of the strategy generation, described in Section 3.3, with an example of a system under development (SUD) that executes three operations, in a sequential manner. All such operations consist in service calls to providers in the open-world environment. The UML system specification is shown in Figures 5.12 and 3.3. The activity diagram 22 3. Self-adaptation for Performance Engineering: Goal Management Algorithm 3.2 CreateNode Require: AD,CD,TT,service (k), current node (node) Ensure: A node (confbest) 1: set PhaseList = ∅ {vector of vectors} 2: if (k==null ∧node==null) then 3: PhaseList ←ExtractInitialListOfPhases(CD,TT) 4: else 5: PhaseList ←ExtractListOfPhases(CD,TT,node,k) 6: end if 7: set CandidateConfigs = ∅ {set of configurations} 8: set RTs = ∅ {set of configuration response times} 9: CandidateConfigs ←AllPossibleConfigs(PhaseList) 10: for all conf ∈CandidateConfigs do 11: GSPNconf ←CreateGSPN(conf) 12: rtconf ←Evaluate(GSPNconf ) 13: RTs ←RTs ∪ �conf,rtconf � 14: end for 15: confbest ←FindBestConfig(RTs) {The node is a configuration with the min response time: �confbest,rt� ∈ RTs | ∀�conf,rtconf � ∈ RTs : rt ≤rtconf } 16: return confbest (Figure 5.12), annotated with the MARTE profile [Obj05], represents the system workflow (i.e., the system model). The type of workload (GaWorkloadEvent) is open and requests arrive to the SUD with an exponential inter-arrival time, with a mean of 500 time units (i.e., “tu”). The requests are processed, one at a time, by acquiring (GaAcqStep) and releasing (GaRelStep) the resource c0. Each activity step (PaStep) models an external service call sk to a provider in the open-world. In particular, the extOpDemands tagged-value is a parameter that is set to the current provider of service skand the extOpCount tagged-value indicates the number of requests made for each service call. The component diagram (Figure 3.3) represents the currently available providers of the services required by the system. In particular, component’s names are given according to the name of the service they provide. There exists only one provider c11 of service s1, while two providers are available for each service s2and s3. Table 3.1 (TT) shows the working phases, in time units, of the providers. In particular, for each provider ckl, the estimated mean service times Skl jand mean sojourn times SJkl jof the offered service, are given. Both the component diagram and TT make up the environment models. 3.4.1 Strategy generation The Time Table and the UML specification, properly annotated with MARTE, provide the input for the Algorithm 3.1 described in Section 3.3. A parametric GSPN model is then created from the activity diagram (Figure 5.12) that will be used to estimate the mean response 3.4. Example 23 Algorithm 3.3 CreateEdge Require: source (Nodes), target (Nodet), service (k), TT Ensure: The edge between NodesaNodet(edge) 1: if Nodet== null then 2: return null 3: end if 4: set cond = 0.0 {confidence level (float)} 5: set edge =�Nodes, Nodet, k, cond� {Computation of Nodesresponse time} 6: GSPNNodes←CreateGSPN(Nodes) 7: rtNodes←Evaluate(GSPNNodes) {Computation Nodetresponse time} 8: GSPNNodet←CreateGSPN(Nodet) 9: rtNodet←Evaluate(GSPNNodet) {Computation of the confidence level} 10: cond ←SetConfLevel(Nodes, rtNodes, Nodet, rtNodet,TT) 11: return edge time of the system under different configurations, using the multisolve facility of GreatSPN [Gre]. The GSPN model is shown in Figure 3.4 and it is characterized by three rate parameters representing the execution mean rates of the service calls s1, s2and s3. Observe that the call to service s2, in the activity diagram, includes 3requests (extOpCount tagged-value) this is modeled by the free-choice subnet, where the weights assigned to the conflicting transitions Start CallS2 and End CallS2 are equal, respectively, to 3/4and 1/4. The first main step of the algorithm (Algorithm 3.1 - line 2), consists of creating the initial node of the reconfiguration strategy graph (Algorithm 3.2). This is accomplished by assuming that each provider works under the best mode. We consider, then, the minimum estimated (mean) service times from each provider, i.e., S11 1= 5tu,S21 1= 10tu, S22 1= 35tu,S31 1= 20tu and S32 1= 30tu. There are four possible system configurations: for each one, we instantiate the parametric GSPN, in Figure 3.4, by setting the rate parameters λS1provider, λS2provider and λS3provider to the inverse of the considered service times Skl 1(k= 1,2,3) of each current provider of services s1,s2and s3, respectively. Once instantiated, the GSPNs are solved and the system (mean) response times are computed (see Table 3.2). In the strategy graph (Figure 3.5), the initial node Node0corresponds to the configuration that revealed the minimum system (mean) response time. Observe that, in this simple example, active providers in the initial configuration correspond to those ones having the minimum service times. However, this property does not always hold in a general case where several providers contend for shared resources. In the next main step of the Algorithm 3.1 (line 11), the nodes adjacent to the initial one are created, considering that the active providers in Node0can degrade their performance. Eventually, there will be three configuration nodes adjacent to the initial node, one for each 24 3. Self-adaptation for Performance Engineering: Goal Management Call S1 Call S2 Call S3 <<GaWorkloadEvent>> {pattern =(open =(interArrivalTime=(exp(500,tu))))} <<GaAcqStep>> {acqRes = C0, resUnits=1} <<PaStep>> {extOpDemands=$S1provider; extOpCount=1} <<PaStep>> {extOpDemands=$S2provider; extOpCount=3} <<GaRelStep>> {relRes = C0, resUnits=1} <<PaStep>> {extOpDemands=$S3provider; extOpCount=1} Figure 3.2: UML activity diagram external service requested by the SUD (Figure 3.5). Let us consider the creation of the first two nodes Node1and Node2adjacent to Node0: the algorithm will iterate over the created nodes to produce their adjacents, until all the possible system configurations are examined. Node1is added considering that the active provider of service s1in Node0(i.e., c11) changes its phase from ph1to ph2, i.e., c11 is answering to service requests with a mean service time of 20tu, instead of 5tu. Since c11 is the unique provider of s1, the Node1 is characterized by the same active providers as Node0as well as the same provider mean service times but the one of c11, which is equal to 20tu. The GSPN model in Figure 3.4 is used to compute the system mean response time of the configuration Node1. Node2is created assuming that the active provider of s2in Node0(i.e., c21) changes its phase by increasing the mean service time from 10tu to 70tu. Then, four candidate configurations were possible: two of them still include c21 as active provider of s2with degraded performance. They correspond to the first and the third configuration in Table 3.2 with the provider c21 in phase ph2. In the other two configurations, the active provider of s2is c22 (i.e, the second and the fourth configuration in Table 3.2). The GSPN model in Figure 3.4 is then used to select the best configuration among the candidates, that is the one with the minimum system (mean) response time. Then, the Node2actually corresponds to the configuration with the minimum system (mean) response time, i.e., 177.6tu. Once a new adjacent node is created, the algorithm generates the corresponding forward edge (Algorithm 3.1line 16). An edge from Nodesto Nodetincludes information about the service skand the goodness of the prediction (confidence-level) for the reconfiguration controller to decide whether it is worth to change the configuration from Nodesto Nodet. Observe that, since we are dealing with the open-world environment, every decision about the providers is based on predictions. We propose an ad-hoc heuristic that works under the open workload assumption and considers the performance goal (i.e., obtain the best system mean response time) as well as the available timing specifications (i.e., provider working phases). Let us consider an edge from Nodesto Nodetwhere the source and the target nodes have different active components, such as Node0and Node2in Figure 3.5. The computation of 3.4. Example 25 System under development C11 C31 S1 C21 C22 C32 S2 S3 Figure 3.3: UML component diagram the corresponding minimum confidence level is related to two quantities: •The performance improvement when the system reconfigures properly, that is the provider has changed its phase and the strategy realizes it (e.g., the provider c21 has changed from ph1to ph2and the system moves from Node0to Node2). This is estimated as: Perfimprove =rts|ckl←phj+1 −rtt, where rts|ckl←phj+1 is the system mean response time with the same active providers as in Nodes, but changing the working phase of provider ckl from phjto phj+1, and rttis the system mean response time in Nodet. •The performance loss when the system reconfigures due to a wrong prediction, that is the provider has occasionally had a slow execution, but it has not really changed its current phase, however the system moves to the target node. This is estimated as: Perfloss =rtt−rts, where rtsis the system mean response time in Nodes. Then, the minimum confidence level is given by the formula: conf level =Perfimprove Perfimprove +P erfloss .(3.1) When the source and target nodes of an edge have the same active components, such as Node0and Node1, the minimum confidence level is computed as conf level =rts rtt. Finally, the way-back edges are created (Algorithm 3.1 - line 21) to allow the system to move back to a previously considered configuration after a (mean) sojourn time period in the source node. So there will be an edge from Nodesto Nodet, labeled with a mean sojourn time period as a timeout, if there exists a provider ckl in Nodeswith its final phase phJkl and in Nodetwith its initial phase ph1. In Figure 3.5, way-back edges are dashed and, for readability, only five of them are shown. The choice of the ideal mean sojourn time period that allows the system to achieve the performance goal (i.e., minimum response time) is a 26 3. Self-adaptation for Performance Engineering: Goal Management Provider working phases (in time units, i.e., tu) ph1ph2ph3 C11 (5,3000) (20,6000) C21 (10,6000) (70, 2000) (250,2000) C22 (35,6000) (140,4000) C31 (20,2000) (70,2000) C32 (30,∞) In format phj= (Skl j, SJkl j) Table 3.1: Time Table of open-world providers (TT) future work issue. In the example, we set such period equal to the mean inter-arrival time of a service request to the SUD (i.e., 500tu). In order to validate our proposal, we carried out the analysis of the system, considering several assumptions: the system does not follow the strategy modeled by the reconfiguration graph in Figure 3.5 (case 1), and the system undergoes reconfigurations according to the strategy graph (case 2). We obtained the following results for the system mean response time: 494tu (case 1) and 436tu (case 2). This means that partially applying our performance aware reconfiguration (eight nodes in Figure 3.5) we have improved the system response time in 11%. 3.5 Conclusion Along this chapter, we have learnt that there exist a lot of challenges for the performance prediction of the open-world software to become a reality. However, we believe that this chapter has proposed a clear architecture for performance-aware open-world software, which means an attempt to comprehensively accomplish most of such challenges. From this architecture, we have explored the uppermost layer and how to generate reconfiguration strategies, that can reconfigure a system while its performance goal has to be achieved. Our generation technique tried to show up where the problems are and it demonstrates a possible solution using Petri nets. However, other generation approaches could be feasible and would be desirable. We validated our solution through an example. A direction to do research in the future work is to include more extra-functional requirements into the strategy generator functionality, such as dependability. As a technical detail, in this work we have not considered network transmission delays, which could be significant in some service-oriented applications that operate on the Internet; however, these delays can be easily incorporated through the UML deployment diagram. 28 3. Self-adaptation for Performance Engineering: Goal Management Mean response time estimation (in time units, i.e., tu) C11:ph1C21:ph1C31:ph160.5 C11:ph1C22:ph1C31:ph1177.6 C11:ph1C21:ph1C32:ph172.5 C11:ph1C22:ph1C32:ph1193.8 Table 3.2: System components candidates [PSL03] is addressed the problem of guaranteeing the QoS of untrusted third-party services. They propose a framework to choose services offering best QoS, in this work the workload is balanced among several providers to support some kind of fault tolerance. The work of Garlan in [GS02] also proposes an architecture for performance evaluation but restricted to self-healing systems, besides they do not use formal methods. Our work has also been inspired by the work in [OMT98], which proposes an architecture to manage the adaptation for evolvable systems, although that work does not deal with performance evaluation. Work in [CMI07] deals with adaptation management and proposes a Performance Management Framework. In this framework, alternative configurations are dynamically created by evaluating reconfiguration policies and monitored data, rather than store from the beginning a predefined set of possible configurations as we do. 3.6. Related work 29 <s3,0.81> Node 0 C11:phase1 C21:phase1 C31:phase1 Node 1 C21:phase1 C31:phase1 Node 2 C11:phase1 C22:phase1 C31:phase1 Node 3 C11:phase1 C21:phase1 C32:phase1 <s2,0.71> <s1,0.77> Node 5 C22:phase1 C31:phase1 Node 6 C21:phase1 C32:phase1 Node 7 C11:phase1 C31:phase1 Node 8 C11:phase1 C22:phase1 C32:phase1 <s1,0.88> <s1,0.80> <s2,0.72> <s2,0.93> <s2,0.72> <s3,0.82> <s3,0.81> <s1,after(500)> <s1,after(500)> <s3,after(500)> <s1,after(500)> <s2,after(500)> C11:phase2 C11:phase2 C11:phase2 C21:phase2 Figure 3.5: Partial reconfiguration strategy graph 30 3. Self-adaptation for Performance Engineering: Goal Management 4.3. State prediction and configuration adaptation 37 Adaptation Strategy Adaptation Decider <<uses>> CT-HMM Analyzer [xml data file] LoadCT-HMM(model,IDmodel) deleteCT-HMM(IDmodel) MonitoredData ChangeConfiguration NotifyModelState <xml ... NewStrategy Figure 4.4: Abstract view of Figure 4.3. We mean by “configuration change” the replacement of a service provider by another one, indeed offering best response time. Being the decisions of the Adaptation Decider based on predictions, there can happen fails or hits. Fails occur when: 1) the provider has actually changed its state but the prediction does not advise it, we call it “false negative”; 2) the provider has not changed its state but the prediction erroneously advises a change, we call it “false positive”. Likewise, a decision hit happens when: 1) no change is advised when it was not needed (called “no-adaptation hit”); 2) or a configuration change is advised when needed (called “adaptation hit”). From the point of view of a self-adaptive software system “false negatives” are lost opportunities to improve system performance, see that a non-adaptive system will always miss such opportunities. However, “false positives” can make the self-adaptive system work worse than a non-adaptive one. The Adaptation Decider calculates the system configuration that is expected to show the lowest mean response time for the system workflow execution. Algorithm 4.1 describes such calculation: for each possible configuration (line 4) calculates the weighted mean of the mean response time for each state combination of a provider (lines 6-10); the weight of each term is the probability for providers to be in the state expected in that state combination (line 8). Finally, it is selected the configuration that offers the lowest weighted mean response time. Algorithm 4.1 has some combinatorial executions (calculation of mrtiand Confi) that make it not practicable. The remainder of the subsection discusses three techniques that improve it, we discuss the improvement they achieve and the kind of prediction error they incur. Most probable state: This technique will change system configuration taking into account for each provider its current most probable state. It will pick the state with lowest response time and consequently selects the provider this state belongs to. This technique will incur in a large amount of false positives. See for example Figure 4.5: say the workflow consists of only one service call to S1. There are two providers (P11 and P12), so the system can execute in two configurations (Conf1and Conf2). Each provider can execute in 3 states, s1, s2and s3, with different mean response times as shown in Figure 4.5. Initially, the state probability distributions could be: πP11 (1) = 0.3, πP11 (2) = 0.37, πP11 (3) = 0.33 and πP12 (1) = 0.15, πP12 (2) = 0.25, πP12 (3) = 0.6. 38 4. Self-adaptation for Performance Engineering: Change Management Algorithm 4.1 Algorithm of the Adaptation Decider Require: AbstractServices(AS), ConcreteProviders(CP ), ProvidersStateDistributions (πk) Ensure: Conf, the configuration with the lowest expected MRT. 1: set Confi{Configuration, selection of a CP for each AS} 2: set StateCombij {Possible combination of providers states in a Configuration Confi} 3: set mrti= 0.0{weighted mean system response time in configuration Confibeing its providers state distribution π} 4: for all Confi∈(AS, CP)do 5: mrti= 0.0 6: for all StateCombij ∈Confido 7: mrtij ←CalculateMRT(StateCombij) 8: probStatej←CalculateP robability(StateCombij, πk) 9: mrti←mrti+mrtij ·probStatej 10: end for 11: end for 12: return Confi| ∀mrti�, mrti≤mrti� Let us assume the system in Conf1, since the most probable state for P11 is s2, the expected mean response time is 50 tu. Now, let us assume that the CT-HMM analyzer calculates a new state distribution for P11:πP11 (1) = 0.2, πP11 (2) = 0.39, πP11 (3) = 0.41. So, now the most probable state for P11 is s3and the system mean response time is 140 tu (see Figure 4.5). In addition, the most probable state for P12 is s3, whose expected mean response time is 110tu. Since 110 <140, the decision will be to change from Conf1to Conf2. This decision has a very high probability to be a false positive, because if all state probability distributions had been taken into account, the expected mean response time in Conf1would have been less than in Conf2, and no reconfiguration would have been proposed (then being a no-adaptation hit). Indeed, applying Algorithm 4.1, the result would have been: (0.2·10 + 0.39 ·50 + 0.41 ·140) <(0.15 ·20 + 0.25 ·80 + 0.6·110) which indicates that it is better to remain in Conf1. This technique is faster than Algorithm 4.1 since it only looks for one state for each provider (the most probable) and executes a comparison between pre-calculated mean response times. On the other hand, it needs to have pre-calculated and stored the expected mean response times for each provider configuration, which can be costly for large service based systems. Most probable state with “sureness”: This technique still considers the most probable state for each provider i(mpsi), but it also takes into account its probability and the expected improvement in the system response time. The technique calculates a “sureness” value (Sr), based on the response time of the system considering source and target configurations (Confsand Conft), as Sr =M RT (Conft(mpsi)) MRT (Confs(mpsj)) . Moreover, it calculates a probability PgoodP red =πi(mpsi)·πj(mpsj). The system will change configuration only if PgoodP red ≥Sr. Note that when PgoodPred is high -almost one-, the system will 4.3. State prediction and configuration adaptation 39 Conf1 S1:p11 .s :10 u.t. .s :50 u.t. .s :140 u.t. 1 2 3 11 p 11 p 11 p System MRT Conf2 .s :20 u.t. .s :80 u.t. .s :110 u.t. 1 2 3 12 p 12 p 12 p System MRT Used Provider Used Provider S1:p12 { { Figure 4.5: Example of two system configurations reconfigure even when the performance in Conftis not very much higher than in Confs. This technique executes as fast as the previous one since it also only needs to look for the most probable state probabilities. However, this technique avoids some adaptations that would most likely incur in a false positive. For example, in Figure 4.5, Sr =110 140 = 0.7857 and PgoodPred = 0.41 ·0.6 = 0.246, then P goodPred �Sr and the system would not incur in a false positive adaptation, as it happened in the previous one. The technique also avoids false positives that are due to “not as much sure of the most probable state probability as to reconfigure”. However, since it only takes into account the probability of the most probable state, it still incurs in false positives related to “in which states are the probabilities that are not in the most probable state of Confsproviders”. Fail compensation: This technique not only takes into account the most probable state, but the whole state distribution. It reduces the complexity of inner loop in Algorithm 4.1 because (see lines 6-9) it does not calculate mrtsfor each possible combination of states StateCombsj in a source configuration Confs, however it considers a pre-calculated mean. Concretely, this mean value is pre-calculated for each state of a provider pisjin a configuration, and it represents the mean response time of the system when piis in state sjand considers the steady state distribution for the rest of the providers in Confs. Therefore, this value represents the mean of the mean response times mmrt. Following this technique, the number of loops is Npi·Npkinstead of � pi∈providers Npiwhere Npiis the number of states of provider pi. The technique will cause false positives due to the use of steady state distributions to precalculate mmrt, whereas in the complete loop in Algorithm 4.1 the actual state probabilities distributions are considered. To mitigate them, it does not reconfigure just when the expected response time in Conftis lower than in Confs, it also considers the “expected profit” when the decision is a hit or the “performance loss” when the decision is a fail (false positive or negative). Then the adaptation is carried out when P rofitW henHit > LossWhenW rong. ProfitWhenHit is calculated as: � sj∈pi (πpi(sj)·� sl∈pk πpk(sl)·coeffprof (pisj, pksl)) where coeffprof (pisj, pksl)is the function coeffprof (pisj, pksl) = �mmrt(pisj) mmrt(pksl)if mmrt(pisj) mmrt(pksl)>1 0otherwise To calculate LossWhenW rong it is also used the previous formula but changing the coefficient for coeffloss(pisj, pksl)where 40 4. Self-adaptation for Performance Engineering: Change Management coeffloss(pisj, pksl) = �mmrt(pksl) mmrt(pisj)if mmrt(pksl) mmrt(pisj)>1 0otherwise 4.4 Integrating the adaptive configurations into an architectural solution In this section we integrate the theory previously described for software that operates in the open-world into the architecture for performance-aware self-adaptive software. Benefits of integrating our proposal into this architecture are clear: we are approaching to a complete reference architecture for open-world software, that can meet performance requirements while manages uncertainties in the environment through a formal model. Figure 4.4 appears now embedded within the shadow part of Figure 4.6, which clearly describes how the new proposal fits in the 3-layer architecture. The proposal in this chapter executes the task of the general Adaptation Manager of the architecture in Figure 2.1. Both the Adaptation Decider and CT-HMM Analyzer, are in the Adaptation Manager scope. Moreover, to ease the applicability of the architectural approach in a non-HMM based solution, just for generality, we refer to the CT-HMM Analyzer using its functionality name: Providers Performance Predictor. Regarding the Adaptation Manager, firstly, generates input values of the Providers Performance Predictor. In Figure 4.3, they are providerp,Ok, and tk, which now respectively match with information about Who, responseTime and When in Figure 4.6. The generation of this input might need a syntax translation depending on the language of the received status messages from the lower layer. Although this technicality about fitting interfaces has not been completely addressed in this work, we do not disregard it and we consider that a translation may exist through a conversion of input status messages to ResponseTimes, Who, and When. Configuration changes are decided using this information, then updating the internal model that stores which one is the main provider for each service and producing a ChangeConfiguration output. This output is forwarded in Change Actions message to the component control layer. Regarding the integration of the CT-HMMs management in the architecture some issues need to be clarified. The management of these models is divided into two entities: the entity that creates and parameterizes the models, called Provider Performance Behavior Analyzer; and the entity that uses them to predict their current state, the Providers Performance Predictor. The functionality of the former is not achieved by a simple operation but requires complex computations. Besides, its operation is not called frequently. Therefore, it is reasonable to place this entity in the uppermost layer. This functionality has not been addressed in this work. However, this is not a neglected part. Indeed, in the hidden Markov models theory, this is one of the typical studied problems, which means to find out the most probable parameters of an HMM from an observation sequence. The latter entity was presented in Section 4.3 without taking into consideration some challenges in open world. Then, it now should offer additional interfaces: loadCTHMM(model,IDmodel) and deleteCT-HMM(IDmodel).Adaptation Manager will use these 4.5. Conclusion 41 Workflow System Performance Goals Adaptation Strategy Generator AnalyzerBehavior Performance Provider Configuration Configuration Change Actions Change Goal management management Change control Component ...> Adaptation <xml.. Strategy Diagram Component System Workflow with SPE Specification Providers performance behavior performance report Providers ResponseTimes Status Strategy Strategy Request New Strategy loadCT−HMM eleteCT−HMM ManagerAdaptation Monitors Who When AdaptationDecider Performance Predictor (CT−HMM Analyzer) Providers Figure 4.6: Emphasized Change Management layer on the 3-layer architecture adapted to open-world interfaces when: •the upper layer provider performance behavior analyzer produces a provider performance behavior that was not included in the Providers Performance Predictor (loadCTHMM). •a service provider vanishes off the world (deleteCT-HMM). •knowledge about a service provider behavior is out of date and the provider performance behavior analyzer offers an updated model (deleteCT-HMM followed by loadCT-HMM). 4.5 Conclusion In this chapter, we have presented an approach, based on HMMs, to predict the performance of SOA providers in the open-world. We have used such prediction to decide the appropriate moments to change the system configuration. We have also fitted the approach in the 3-layer architecture, concretely in its second layer. 42 4. Self-adaptation for Performance Engineering: Change Management The parameterization of the CT-HMMs has not been addressed in this work. However, it is possible to integrate an already existing solution to find the most probable parameters. 4.6 Related work The motivation of our work in this chapter is shared with the work in [GMMT10], where authors evaluate providers selection strategies. In [GMMT10], comparison between strategies is based on the mean response time the clients achieve. Although our work shares motivation regarding to reach best workflow performance, we take different assumptions. Firstly, we do not rely on user agreements or collaborations to reach a global knowledge about providers performance behavior and their changes, but we assume independent adaptive clients that only concern about their best performance in a selfish way. Secondly, we assume that our requests do not affect the workload of the providers and hence neither their performance. Regarding the usage of HMM in self-adaptive software systems, work in [WY07] uses them in the provider side to predict requests based on the monitored history of the clients behavior. The layered architecture for model-driven adaptation explained in [TGEM10] has some aspects in common to ours -beyond the 3-layer architectural view-, such as the dynamic generation of adaptation plans. A key difference is that in our proposal, actions to follow the plans are based on probabilities, since they necessarily come from predictions about properties of third-party service providers that operate in the open-world, and these predicitions are necessarily subject to uncertainties. Chapter 5 Self-adaptation for Energy Conservation Energy use is becoming a key design consideration in computing infrastructures and services. In this chapter, we focus on service-based applications and we instantiate the 3-layer adaptation framework to architect a system that is able reduce its power consumption according to the observed workload. We concentrate on the work of the uppermost layer and we propose the generation of adaptation plans that guarantee a trade-off between energy consumption and system performance. The approach to reduce power usage is based on the principle of proportional energy consumption obtained by scaling down energy for unused resources, considering both the number of servers switched on and their operating frequencies. The formal method that helps us for the modeling of the framework concerns is the GSPNs. After presenting the approach, it is applied to a simple case study to show its usefulness and practical applicability. 5.1 Motivation The constant growth of energy usage in industrialized countries is creating problems to the sustainability of the Earth development. The problem of energy use concerns many fields in human activities: for this reason some new disciplines such as green computing are growing up to study how to consume less energy by providing the same quality of service [Ran10]. As shown in [DKL+08, Ran10], the interest towards efficient use of technology is motivated by some alarming trends showing, for example, that computing equipment in the U.S. alone is estimated to consume more than 20 million giga-joules of energy per year, the equivalent of fourmillion tons of carbon-dioxide emissions into the atmosphere [Ran10]. IT analysis firm IDC (http://www.idc.com/) estimates the total worldwide spending on power management for enterprises was likely a staggering 40 billion dollars in 2009. Large computing infrastructures, like data centers, web services hosting or email, in the U.S. consumed the 1.5% of all electrical power in 2006 and it grows at an annual rate of 43 44 5. Self-adaptation for Energy Conservation 12% [CJH+11]. Nevertheless, it is possible to observe that they are so complex that some parts become inactive even during active periods. In this chapter, we focus our research on the consumption of the computing infrastructure of the providers of service-based applications. Often when deciding the amount of resources -hardware and softwareto include in the platform, worst-case scenarios are considered, which leads to over-provisioning for other scenarios of the system. The result is a static system deployment that wastes part of the available processing infrastructure and consequently causes energy waste. Therefore, a first direction that can be followed for energy savings is the definition of adaptation plans that can be used to reduce power in time (turn off during idle times) and space (turn off inactive elements). Hence, infrastructures can be dynamically scaled to conserve power with no impact on performance while they match workload demands. The definition of this adaptation plan is not easy, because the workload is typically variable and unpredictable and because there are also other, possibly contrasting, goals that should be satisfied. Indeed, the ultimate goal of a service provider is to maximize profits from its offered services, while for a client the main objective is to obtain a service with required QoS at the minimum cost. Therefore a suitable adaptation plan should be able to define the best trade-off between energy consumption and QoS offered. The problem is quite complex and -as mentioned in the related work in Section 5.9there exist in the literature several attempts to propose methods for managing power and guaranteeing the agreed quality of service. Among the multiple QoS attributes of software to face with energy, in this chapter we choose the system performance in terms of mean response time. The problem of maximizing providers revenues, although important, is not directly tackled. The reason is that we follow the same vision as the one in [CDQ+05], which defends that quality requirements always must be met once contracted. However, other approaches consider that it is fair to violate QoS contracts deliberately in some cases; for example, in case that the penalty paid by the provider to the customer due to contract violation is lower than the investment necessary for meeting the agreed QoS. These methods allow providers to increase their profit at the expense of their reputations.- Nevertheless, the problem is indirectly addressed in this work, since having a strategy that scales the amount of servers, while satisfying the performance requirements, reduces the expenses in the equation profit =revenues −expenses. Proposed Solution In order to reduce energy waste, the processing infrastructure of a service provider can be dynamically accommodated to the actual processing requirements for each scenario. Since the received workload varies frequently and in some cases unpredictably, human intervention to modify the amount of dedicated processing resources is not feasible. So the goal is to have the system aware of its processing resource needs, and able to selfadapt its processing infrastructure to fulfill such needs. Therefore, the objective is to build systems that can autonomously manage their processing resources in order to consume only the power necessary to satisfy their -possibly evolvingperformance requirements. These new techniques actually complement the traditional and well-known off-line capacity planning [MA01]. To achieve the objective, in this chapter we instantiate the reference architecture in Chapter 2 to architect a system that is aware of its processing demands, performance requirements and available computing resources. After, we work on the uppermost layer, 5.1. Motivation 45 i.e., Goal Management, and it is proposed a method to generate adaptation plans. These plans tackle the adaptation decisions that decrease as much as possible the system’s energy consumption while maintaining the expected performance. The approach also allows the plan regeneration when its execution context changes, which would make the current plan not suitable. The adaptation plan indeed depends on the dynamic variable workload, on the available processing resources, on the application processing demands and on the agreed QoS in terms of performance requirements. To exemplify the deployment of the approach, it is discussed one deployment of interest for the case of software services. To study the relations among these properties, we follow model-driven techniques to transform design models into analyzable models. In this case, the analyzable models are the Stochastic Petri Nets (SPNs) subnets. Subnets allow modeling the variable workload, the workflow, the processing resources and the logic to adapt the system energy consumption. The considered variables are not new, several works (e.g., [EKR03, CDQ+05]) and a survey [BR04] exist on this topic. As recognized in [CJH+11], queuing models, category of which SPNs are an example, are ideal to predict runtime trade-offs between performance and energy use. Moreover, queuing models have been largely validated during the last decades and we can be absolutely confident in the results they produce, which may free the modeler from the need of validating the model as long as it accurately represents the target system. This is an advantage regarding ad-hoc models, heuristics or equations when used to model complex behaviors, since they really need extensive validation to prove that the predictions they obtain actually match the real measurement. In contrast, queuing models have been accused of being difficult to construct. In this regard, we try to keep our models as simple, repeatable and scalable as possible and we propose tools to automatically construct them. To generate a Petri net that represents the whole system behavior, we put together the previously mentioned subnets. Hence, this analyzable SPN includes fine-grained information regarding: mean execution times of internal activities; resource usage of activities; resource competition for passive resources (e.g., buffers) which generates “waits” and makes the system performance not scaling linearly with frequency; and resource competition for active (processors) which are the basis for power consumption. The SPN evaluation, carried out with the GreatSPN tool [Gre], gives results about the suitability of the adaptation plan (in terms of whether it deteriorates performance results) and how much energy it saves. Moreover, we define a parametric Petri net that can be evaluated to discover which are the best parameters to tune the adaptation plan, in order to save as much energy as possible. Motivating Example We describe a kind of system for which can be applied our approach. Consider a company that develops software services which are offered in the Internet, some of them for free while others can get subscription rates. Irrespective of the implementation, the services follow a Service Oriented Architecture (SOA). The company maintains a homogeneous computing infrastructure, around hundreds of servers, which deploys the services. These services are used all around the world and they can receive thousands of requests per minute at certain times of day, however it is also possible that the workload decreases at certain hours considerably. When the workload is in a peak the infrastructure has to be fully 46 5. Self-adaptation for Energy Conservation operative and each service will be replicated in as many servers as necessary to support the quality of service the company promises. On the contrary, when the workload is low, most of the servers can not be necessary at all. Therefore, the company needs an integral software solution, beyond the traditional load balancer, that switches on and off the servers to adapt the infrastructure to the workload dynamically. We argue that if the software solution follows the architecture described in this chapter, the infrastructure can achieve the advantages previously discussed, i.e., a good trade-off between QoS and energy conservation. The remainder of the chapter is organized as follows. In Section 5.2 we present the instance of the 3-layer architecture for self-managed systems for the management of energy and performance. The proposed SPN models for dynamic variable workload and energy consumption are presented in Sections 5.3 and 5.4, respectively. The trade-off between energy consumption and the fulfillment of the performance goal is presented in Section 5.5. Section 5.6 discusses a suitable deployment of the architecture and presents evaluation through an example, which is developed step by step to help practitioners to learn the proposal. The evaluation continues in Section 5.7 to experiment with variable workload. Section 5.8 draws some conclusions and provides pointers to on-going work. Related works presented in Section 5.9 complete the chapter. 5.2 Architecture In this section we instantiate the reference architecture for self-managed systems presented in Chapter 2 for software systems whose adaptation goal is to save energy. Figure 5.1 describes our proposal identifying responsibilities for each layer and the necessary software modules that can carry out them. The Component Control layer accomplishes the application function of the system, in our case the workflows of the software services the infrastructure deploys. The software services modules represent the executable files of these software services. They are the instance of software application and infrastructure in Figure 2.1. Note that they are replicated, really to represent several services but also several running instances of each service. Each running instance, which manages requests until its maximum capacity, will execute in a server of the infrastructure. Each server can host several running instances. The Component Control layer also features a HardwareController and a LoadMonitor software modules. They are the instances of sensors and actuators in the general architecture and they include facilities to report the current status of the processing infrastructure and to support modifications on it. The HardwareController implements: a sensor functionality for communicating with its upper layer to inform the current state of the servers (e.g., booting completion), and an actuator functionality to receive orders to reconfigure the server infrastructure (increase/decrease frequency or switch on/off of servers). We think of it as a software module that manages the servers through the Wake on LAN (WoL) facility. The LoadMonitor monitors current system workload and informs to its upper layer when the workload exceeds some thresholds, i.e., a problem to solve. Thresholds of interest were previously identified by the upper layer to this module. The Change Management layer executes actions to handle the new situations reported by the lowest layer. It is made by a software module, the EnergyManager, and its input 5.4. Energy modeling and analysis 53 servers is WAggreagedStandby =Wstandby ·(E[#OperativeServers]+ E[#WaitF orRequestsCompletion]) where E[#Px]is the mean number of tokens in place Px. 3. Maximum power consumption of a server, Wmax, considers when a server is busy and working at its maximum frequency. 4. Since voltage supply limits the maximum operative frequency of the circuit approximately to a linear factor, then following [EKR03, CDQ+05], we merge dynamic frequency scaling and dynamic voltage scaling, and we obtain that power consumption is proportional to the cube of the working frequency. Therefore, power consumption of a server in an operational frequency will be Wfreqi= (Wmax −Wstandby)·(opF reqi)3. Finally, the total amount of power consumed by a server working at frequency OpFreqiis Wserveri=Wstandby +Wfreqi. In the SPN, the mean power consumption of a single server is calculated as Wmean =� i Wserveri·P(#F requency =i+ 1), where P(#p=n)means that the probability of the number of tokens in place pis equal to n. Meaning of place Frequency is unveiled in the following. Regarding servers processing frequency, dynamic frequency and voltage scaling allow varying working processors performance and to reduce their power consumption. Although the working frequency could ideally range between 0 and 100% of processor capabilities, real working frequencies are usually discretized. Therefore, as in [CDQ+05], we assume that the actual server frequency is restricted to a value within a set of operational frequencies FreqSet. We consider FreqSet made of a base frequency BaseF req and increments BaseInc. Therefore FreqSet ={OpFreqi} | OpFreqi=BaseF req +i·F reqIncr ∧(i≥0) ∧(OpFreqi≤100%). For example: BaseFreq = 50%,BaseInc = 10% and FreqSet ={50%,60%, 70%,80%,90%,100%}. Advancing a description of the Petri net model in Section 5.5 (Fig. 5.9), tokens in place Frequency will represent servers processing frequency. It will contain from 1 to |FreqSet|tokens (from minimum to maximum frequency). A reconfiguration in the server frequency will obviously change the number of tokens in this place. To keep the model simple, we do not model other variables related to power-aware adaptation such as savings in the cooling system. 54 5. Self-adaptation for Energy Conservation 5.5 Performance and energy trade-off This section explains the process of creating an energy-aware plan that cares of performance requirements. To ease the explanation, we divide the process into two steps: the former to generate a basic plan, Subsection 5.5.1, while the latter to optimize it, Subsection 5.5.2. Subsection 5.5.3 proposes a Petri net model for the plan described in Subsection 5.5.2. Finally, Subsection 5.5.4 presents a Petri net that results from merging all the PNs obtained so far. That model will be useful to carry out a trade-off evaluation (performance and energy) of the system. 5.5.1 Generation of basic-plan An energy-aware adaptation plan will be a set of system configurations, that meet the performance goals using minimum energy, and actions to change among configurations. A configuration defines the number of active servers as well as the frequency they are working at. Hence, actions to change a configuration will just mean to switch on/off servers and/or change their working frequency. Using the number of servers and their working frequency, the power in each configuration can be calculated. A configuration also identifies a threshold that corresponds to the maximum system load the configuration can manage. Energy manager uses information in the plan to accommodate the system configuration to the most suitable regarding the current number of requests (system load). System load is an information the plan receives from the lower layer, which indeed monitors the system. In the following the process to generate the energy-saver adaptation plan is explained (Table 5.1 will help the process understanding). 1. Generate a SPN model of the system workflow which includes the required processing demands. Set the capacity of servers to a minimum (e.g., in Table 5.1, one server, k=1, at its minimum frequency, OpF req0= 50%). 2. Evaluate the SPN to discover the mentioned threshold, i.e., the maximum load (Nrequest) it can manage while the performance goals are satisfied. Compute power consumption (Wserveri) for this configuration. (In Table 5.1, 27 and 16.3 respectively for the first case.) 3. Increase the server frequency (which means to modify the SPN) and go to step 2. Repeat this step for all the frequencies the system has to manage, i.e., |FreqSet|. At this point we have completed one row of the table. It is natural to assume that, if a server working at frequency OpF reqican manage Nrequestsiand spends Wserveripower, kindependent and concurrent servers working at the same OpFreqiare able to manage k·Nrequestsiand they spend k·Wserveripower. Applying this, we compute the rest of rows in the table multiplying the first row values by the number of servers that represent each row. We will consider as many servers as available in the infrastructure. As a result, we have generated a table that contains all possible system configurations and, for each configuration, its power consumption and the load it is able to manage (the complete table is not displayed). 5.5. Performance and energy trade-off 55 Percentage of frequency, OpF reqi 50% 60% 70% 80% 90% 100% k=1 Nrequests 27 32 37 43 48 54 Wserver 16.3 18.4 21.3 25.1 30 36.2 k=2 Nrequests 54 64 74 86 96 108 Wserver 32.6 36.8 42.6 50.2 60 72.4 k means number of active servers Table 5.1: Information required to create an adaptation plan Using data in the generated table, Algorithm 5.1 can be applied to generate the basic adaptation plan. This plan contains an ordered list of a subset of possible configurations (called suitable configurations) as well as threshold values indicating the moment to change from one configuration to another. As a result we can distinguish two kinds of adaptations: those that only require to change the frequency and those that require to change the number of working servers -most probably, together with their frequency. An example of configuration in Table 5.1 is the system working with only one server (k= 1), with frequency 60% and then with thresholds 27 and 32 requests, in this case the power consumption is 18.4. System load ranging between 0 and 48 can be managed by only one server and changing only the frequency. However, when the number of requests exceeds 48 it will be better to change to a configuration with 2 servers and frequency at 50% since power consumption is 32.6 instead of 36.2 offered by the configuration that only changes frequency. So, the configuration that uses one server at 100% will never be used. Figure 5.7 shows a basic adaptation plan in a chart. It depicts reconfiguration points in function of the workload, considering a six-server infrastructure. 5.5.2 Reconfiguration rate mitigation The basic-plan suffers periods with high rates of switching on and off of the servers, which is a real drawback for two reasons. First, the time spent in booting and halting can be too high w.r.t. the real working time, then the energy spent in switching tasks is not spent in serving requests. Second, the more the switching rate, the more the wear and tear of servers. To reduce the number of switch on and off of the servers we propose to use reconfiguration limits with hysteresis. In other words, the Nrequests threshold value indicating when the system changes between two neighboring configurations will not be unique but composed of a couple of numbers, Nrequestsdec and Nrequestsinc, according to whether the system tendency is reducing its power (moving from the high energy consuming configuration to the lower) or increasing it (moving from the lower consuming configuration to the higher). Therefore, the association between the supported load and the system configuration will not be unique. 56 5. Self-adaptation for Energy Conservation Algorithm 5.1 Basic-plan generation Require: Table with Nrequests and Wserver (dimension KxF) Ensure: Basic adaptation plan. 1: set k= 1 {considered number of servers, row index} 2: set f= 1 {considered frequency, col index} 3: set Plan ←EmptyPlan() {create empty plan} 4: set currentConf ←Table[k][f] 5: Plan ←AddT oPlan(Plan, CurrentConf) 6: set cadidateFreq {Search rest of suitable configurations until finish the table} 7: while k < K do 8: cadidateFreq ←GetBestInRow(k+ 1, currentConf) 9: if IsBetterToContinueWithSame Servers(k, f, candidateF req)then 10: f←f+ 1 {Next configuration increases frequency} 11: currentConf ←Table[k][f] 12: else 13: k←k+ 1 {Next configuration increases servers} 14: f←candidateFreq 15: currentConf ←Table[k][f] 16: end if 17: plan ←AddToP lan(Plan, currentConf) 18: end while {Add last row of table to plan} 19: while f < F do 20: f←f+ 1 21: plan ←AddToP lan(Plan, T able[K][f]) 22: end while 23: return Plan The meaning of these new limits are: Nrequestsinc scorresponds to the threshold amount of requests to change from configuration sto s+ 1.Nrequestsdec scorresponds to the threshold amount of requests to change from configuration s+ 1 to s. In Figure 5.8, bold continuous line shows the Nrequestsinc values, which are very similar to the previous Nrequests while bold dashed line depicts Nrequestsdec. In that graph, the hysteresis length is equal to 2 steps, i.e, the dashed line is moved two configurations above the continuous line. Therefore, ∀s∈ {2..S}Nrequestsdec s=Nrequestss−2. For example, supposing that configuration s is the one that uses three servers working at 60% of its frequency, and looking at the change from configuration sto s+ 1 (i.e., use three servers working at 70%), Nrequestsinc s= 94. However, looking at the change from configuration s+ 1 to s,Nrequestsdec s= 74; value which corresponds with the previous Nrequestss−2. Therefore, the higher the hysteresis length, the lower the reconfiguration rate and the less the wear and tear, but higher the mean power consumption, since the system spends more 5.5. Performance and energy trade-off 57 1 1 1 1 50 70 80 90 502 2 2 3 3 3 4 5 nservers %freq 60 1 70 60 50 70 60 60 50 70 605 5 6 60 25 35 45 55 65 75 85 95 105 115 125 135 145 155 165 175 185 2nd server 3rd server 4th server 5th server 6th server nclients 1 server 2 servers3 servers 5 servers 4 servers Figure 5.7: Graph for system reconfigurations time in a configuration that consumes more energy than necessary to deal with the received workload. There is an example of the trade-off between these characteristics in Section 5.6. It is possible to observe small differences between bold continuous line in Figure 5.8 and black line in Figure 5.7: these are due to corrections made when the reconfiguration involves to turn on a new server. These corrections are intended to mitigate the non quality satisfaction during the booting time of the newly switched on server. We start to switch on a server few moments before it will compulsorily need to maintain the required quality. This helps to have it already booted and completely operative when it has to be used. Among the multiple manners to decide how much the booting moment should be brought forward, we choose to calculate it as a proportion of the step length called Bring Forward Proportion (BFP). Thus, when the system is in a configuration Confjsuch that the immediately consecutive Confj+1 uses one server more, the adaptation order will take place when system load reaches Nrequestsinc Confj=Nrequestsinc Confj−1+�(NrequestsConfj− Nrequestsinc Confj−1)·BFP�. As an example, let us consider the difference between the bold continuous line in Figure 5.8 (in Nrequests = 111) and black line in Figure 5.7 (Nrequestsinc = 96 + �(111 − 96) ·0.75�= 107) with a BFP value equal to 0.75 and focusing on the moment to order the switching on of the 4th server. Thus, without hysteresis and BFP, three servers were used when the load of the system ranged from 74 to 111. With the new improvement, three servers can be used to manage from 52 to 107 requests, but what happens concretely, is that two or three servers are used to manage from 52 to 74 requests, exactly 3 servers for the range 74-76, three or four servers to deal with requests from 78 to 96 and three, four or five servers manage requests from 96 to 107. 58 5. Self-adaptation for Energy Conservation 1 1 1 1 50 70 80 90 502 2 2 3 3 3 4 5 Nservers %freq 60 1 70 60 50 70 60 60 50 70 605 5 6 60 25 35 45 55 65 75 85 95 105 115 125 135 145 155 165 175 185 2nd server 3rd server 4th server 5th server 6th server Nrequests 1 server 2 servers 3 servers 5 servers 4 servers on on on on on 2nd server off 3rd server off 4th server off 5th server off 6th server off 6 servers Figure 5.8: Graph for reconfiguration (with hysteresis) The decision to set a suitable value for the hysteresis proportion is studied in Section 9.4 by means of the evaluation of an example with different proportion values. 5.5.3 Petri net model of a plan The Petri net in Figure 5.9 models the system reconfigurations that an energy aware adaptation plan could carry out, in this example there are depicted configurations Conf0,Conf1, Conf2,Confsand Confs+1 of the plan. Places representing configurations, Confi, are in mutual exclusion and can contain at most one token. Transitions in the right hand side (t4and t5) allow to upgrade the power of the system changing to a configuration that increments its Frequency when the system is supporting a load that exceeds the configuration threshold Nrequestinc Confi(weight of the test arc linked to systemLoad). Transitions in the left hand side (t1and t2) allow to downgrade the power of the system changing to a configuration that decrements its Frequency when it receives less than Nrequestdec Confirequests, in this case an inhibitor arc (those having a circle at the end) prevents the firing of the transition when the number of tokens in systemLoad is more than Nrequestdec Confi.SystemLoad place will be filled by the workload subnet (the subnet shown in Section 5.3, Figure 5.4), and its tokens removed by a timed transition with infinite server semantic and firing rate 1 MonitoredT imeSpan , so it accounts for the number of requests the system has received during the lasts monitoredTimeSpan seconds. Some downgrades in the system configuration imply to increment the frequency and to decrement the number of servers, transition t3represents them. In this case, the Frequency is increased with the difference of frequency between configurations (Freq(Confi)− Freq(Confi+1)). While the number of servers is decremented sending an event (token in SwitchoffEvent) to start the switch off process. 5.5. Performance and energy trade-off 59 systemLoad Conf0 Conf1 Conf2 Confs Confs+1 Conf Nrequests 0 Inc Conf Nrequests 1 Inc Conf Nrequests s Inc Conf Nrequests 1 Dec Conf Nrequests 2 Dec Conf Nrequests s+1 Dec Frequency SwitchOnEvent SwitchOffEvent ConfFreq( s)ConfFreq( s+1 ) ConfFreq( s)ConfFreq( s+1 ) Waiting For Booting BootedEvent t1 t2 t3 t4 t5 t6 t7 λ 1 monitoredTimeSpan = Figure 5.9: Petri net modeling the adaptation plan behavior On the other hand, some upgrades of system configurations imply to decrease frequency and increase the number of servers, they are trickier and need of two transitions, in the example t6and t7. In this case, the change of frequency and the switch on of the servers cannot be concurrently executed since switch on entails booting time. So if the frequency is changed when the new servers have not been yet added (servers are booting), the servers currently working will be the ones suffering the frequency change and they will provoke a transitory quality degradation of the system instead of its power enhancement. Then we split up the upgrade process in two steps. In the first, t6orders the system to switch on the server (tokens in SwitchOnEvent and WaitingForBooting places). During this booting time the system works at the frequency in the source configuration (no degradation). When the server is already booted (token in BootedEvent), the frequency is decreased using transition t7, and the system reaches the new configuration. 5.5.4 The Petri net for trade-off evaluation The Petri nets for the adaptation plan, the workload, the state of the servers and the software service are merged to create a new one where to carry out the proposed trade-off analysis. Figure 5.10 depicts an abstract view of this Petri net, where the places that are interfaces clearly emphasize how interact the nets. Although we do not present in this chapter a Petri net of a software service, Figure 5.12 illustrates the workflow of a software service, and we obtain the corresponding Petri net automatically, using ArgoSPE [GMM06]. 60 5. Self-adaptation for Energy Conservation Workload PN StartWorkflow Processing infrastructure PN OperativeServers Workflow PN Adaptation Plan PN Frequency SwitchOffEventSwitchOnEvent BootedEvent Ongoing Requests SystemLoad (in Fig.6.4)(in Fig.6.6) (in Fig.6.9) Figure 5.10: Abstract view of the Petri net for evaluation. 5.6 Deployment and evaluation In this section we present a possible deployment of the modules in the architecture in Figure 5.1. The UML deployment diagram in Figure 5.11 depicts a deployment in which the computing platform is made of servers, where the software services in the Component control layer are deployed. The bottom layer of the architecture is completed with the LoadMonitor and the HwController which are software modules that accommodate in the hardware that receives the requests from clients, also separated hardware could be used. The software module that comprises the Change management layer, Energy Manager, is deployed in a separate hardware that only communicates with the other two layers for sending and receiving the orders and information specified in the architecture. Finally the Adaptation Plan Generator, which is a software that evaluates SPNs as explained in Section 5.5, is deployed in a high performance computing platform to create the plans on demand, this service could be even provided by a third-party in the cloud. 5.6.1 Evaluation framework The SPN in Figure 5.10 represents all the elements in the deployment, although some implementation was required to carry out evaluation. The requests of the clients are modeled as proposed in Section 5.3, which confer us the advantages previously presented as well as the choice of performing a plethora of experiments as discussed in Section 5.7. The actions of the HwController are embedded in the SPN in Figure 5.6. The software services are simulated by the SPNs that represent them, note that the main interest is to simulate the time they spend, which is accurately represented by the timed transitions of the SPN. These SPNs are obtained from the UML models of the software services using the ArgoSPE tool [GMM06]. Regarding the middle layer, Change management, it is embeded in the SPN in Figure 5.9 which represents the adaptation plan. We have implemented a java program that creates the basic plan, evaluating PNs and applying Algorithm 5.1. The evaluation was carried out using 5.6. Deployment and evaluation 61 computing platform Monitor Load Controller Hardware Energy Manager Plan Generator Adaptation <<HPC>> <<exe>> <<service>> <<exe>> <<service>> <<exe>> <<service>> <<server1>> LAN L A N <<host>> <<client>> <<client>> Internet <<server2>> <<server N>> Figure 5.11: Deployment of the reference architecture the GreatSPN tool [Gre]. The program also creates the plan with hysteresis. The resulting plan gives the parameters for the SPN in Figure 5.9. Hence, we have created a model-based framework, that being able to evaluate our proposal, frees us of developing this expensive deployment, specially in regard to acquire or rent a real computing infrastructure. Being our purpose a model-based evaluation, we consider interesting to summarize the differences between it and an hypothetical evaluation carried out using the deployment in Figure 5.11: •We do not have “real” clients but a model of workload. However consider that this part of the deployment does not belong to the architecture, i.e., to our contribution. Moreover, we have shown a method in this chapter to appropriately leverage the workload. •We have not traded an expensive computing platform made of hundreds of servers. However our SPNs models carefully represent the workload they support and our plan considers their consumption, frequency and booting and shutdown times. •The HwController has not been implemented since we have not the computing platform it manages. However, this task just means to program the WoL facility of the servers and the remote control of the frequency. •The Load Monitor is not necessary in our evaluation since the workload is generated by our model. •The Adaptation Plan Generator has been implemented for our model-based evaluation and it could be reused in the deployment in Figure 5.11. 62 5. Self-adaptation for Energy Conservation 5.6.2 Example of evaluation: relay mail server The model-based framework above described has been carried out to evaluate a simplified version of a relay mail server, a kind of system very common for enterprises and institutions. Relay servers use to be replicated to cope with highly dynamic workloads usually being a few the number of replicas, except for extremely large mail providers. The server receives requests, to route mails to destinations, from both external and local users. First activity is to accept the service. For example, mails from local users are allowed to be delivered to anywhere, while external users could only be allowed to send mails to local users, then avoiding open-relay risky configurations. For accepted mails, the relay analyzes the content regarding security, trying to mark viruses, spam or phishing. Safe mails are delivered with a header indicating the analysis result. Mails containing viruses are rejected. The destiny of safe mails can be either an external relay server, the one of the addressee, or the own company mail inbox server. Finally, the relay server writes a log about the operations performed, time stamps and related information (indeed, this kind of logs have been very useful for our research in Section 5.3). Figure 5.12 depicts the workflow, using UML, as well as the performance information, in this case annotated with the standard MARTE [Obj05] profile: a) mean host demand for each operation and b) system routing rates as probabilities. Host demands annotations assume the server working at its maximum frequency. The performance requirement states that mean response time for a legitimate request should be less than two seconds. Workload model For the sake of simplicity we adopt the monitored workload of the University web server presented in Section 5.3. So, the workload is the one depicted in Figure 5.2 and the corresponding Petri net model in Figure 5.4. Let us assume the following mean arrival request rates per minute in each state: 1800 for peak, 1300 for working, 100 for night and 500 for weekend. They are modeled by transitions of name λstate in the Petri net. Rates of transitions that model state changes were explained in Section 5.3. Evaluating this Petri net in isolation (without considering the workflow Petri net), we obtain that its long term mean inter-arrival time is 943.4 requests per minute. Characteristics of the processing resources We have supposed a set of identical servers and Round-robin technique to balance requests. We have followed classical techniques to create the SPN that models the load balancing technique, which inserted in between the workload and workflow SPN submodels. The characteristics of a server are: 1. Maximum power consumption, Wmax = 100W. 2. Idle power consumption, Wstandby = 15W. 3. Others power consumptions, Cstartup =Cshudown = 6000 Joules. 4. Frequencies range from 1600MHz to 3200MHz in steps of 266.6MHz. Thus, the set of frequencies is {50%,58.33%,66.66%,75%,83.33%, 91.66%,100%}. 5. Booting and shutdown times, Tstartup =Tshutdown = 1min. 5.9. Related work 69 the importance of the problem of energy wastes is recognized. They treat the problem from different points of view, such as the consumption from hardware devices, operating system or software applications. They sum up previous efforts in the field, raise current problems and devise ways to reduce the energy consumption. [EKR03] evaluates five strategies to save energy: two strategies manage processor frequency, another one switches on and off servers and the last two result from the combination of frequency and number of servers management. The authors study the performance degradation of applications with respect to the strategy used. In our work, we propose to generate an adaptation plan that uses the same techniques as in their latter strategy. Besides, we share the modeling of servers startup, shutdown and waiting for ongoing requests times. To predict execution demands of requests from each user our analyzable SPN models include more fine-grained information. The goals of the work in [CDQ+05] are close to ours: to reduce costs while satisfying quality contracts. We share the techniques to save energy when the system is overdimensioned for the supported workload: switch off of the servers and modification of their frequency. Their optimization technique also considers the problem of wear and tear on servers when repeated on-off cycles are performed.They proposed methods based on queuing theory, feedback control and hybrid mechanisms, instead, we use SPN models in an architectural framework. We also differ because their proposal reconfigures the system just in predetermined time instants, however we do it as soon as a better configuration is recognized. The authors in [AAA+06] propose a framework for hosting multi-service platforms that allows the management of reallocation of the correct amount of resources for each service while satisfying the performance requirements. The work in [CVP+08] extends the previous one by considering energy consumption constraints and situations where the system is under illegitimate users requests. Our work differs from the previous ones in the goals. While their main objective is to maximize company profits (they consider cases when providers pay penalties), our goal covers both the savings in energy consumption and continuous performance requirements satisfaction. Mistral [JHJ+10] handles multiple distributed applications and large-scale infrastructures to optimize power consumption, performance and the transient costs of adaptations. As in our approach, Mistral reconfigures the system when variations in the monitored workload are appreciated, however they implement a workload predictor that estimates these workload variations, in our case the SPN model of the workload owns this knowledge. They present an algorithm, that can increase exponentially, to create a graph that represents the system configurations and adaptation actions, in our approach the reconfiguration plan is represented also by a SPN model. For the computation of applications response time, Mistral, as well as our approach, relies on formal models, in this case queuing networks instead of Petri nets. [HBK11] presents an approach to self-adaptive resource allocation in virtualized environments that cares for SLAs. Their adaptation algorithm differs from ours since it proceeds in two phases: a first one to allocate resources to meet SLAs and a later one to deallocate those not utilized. The approach is validated using standard benchmarks. The approach in [KKH+09] implements and validates, using a benchmark, a dynamic resource provisioning framework for virtualized server environments. It also accounts for the switching costs of the machines. As in our approach, the excessive switching and the 70 5. Self-adaptation for Energy Conservation variations in the workload intensity are taken into account. However, the approaches differ considerably. For example, they use a Kalman filter to estimate the number of future arrivals, while our approach allows accurate modeling using SPNs of multiple kinds and combinations of variable workload. The dynamics of the system are expressed using equations, however we use SPNs as a modeling paradigm. Finally, [CJH+11] is an interesting work that develops a measurement-based approach as alternative to queuing models, which clearly differentiates it from our work. They also create a new set of metrics to predict runtime trade-offs between performance and energy use. Moreover, the alternative is extensively validated. Chapter 6 Workload Modeling for Self-adaptive Software As we have seen, software can be often embedded in dynamic contexts where it is subject to high variable, non-stable, and usually bursty workloads. A key requirement for a software system is to be able to self-react to workload changes by adapting its behavior dynamically, to ensure both the correct functionalities and extra functional requirements. Research on fitting variable workload traces into formal models had been carried out using Markovian modulated Poisson processes (MMPP). These works concentrated on modeling stable workload states, but accurate modeling of transient times still deserves attention since they are critical moments for the self-adaptation. In this chapter, after a detailed problem description, we build on research in the area of MMPP trace fitting and we propose a Petri net fine-grained model for modeling highly variable workloads that also accounts for transient times. 6.1 Motivation Among the multiple sources of change that a self-adaptive software can face and multiple adaptation mechanisms, in this chapter we deal with changes in the workload and the adaptation of the processing resources allocated to the application task. The workload, for some kind of systems, is far from being stable but it presents high variability and shows burstiness, i.e., irregular spikes of congestion. This is a fact for example in networked and service-based systems, but not only [MZR+07]. If the workload model does not account for the existing burstiness, then the model analysis can lead to optimistic results; e.g., it declares a fair resource utilization and probability of congestion, while in the real setting they would not be guaranteed. In this chapter, we present our research on the modeling of workloads that show bursty periods. Some formal methods that can model workloads considering the burstiness in the arrival rate are the Markov arrival processes (MAP) and a concrete subtype of them, the Markov modulated Poisson process (MMPP) [FMH93]. Research on workload and network traffic 71 72 6. Workload Modeling for Self-adaptive Software fitting using MAPs and MMPPs have been already done and their results show an accurate modeling of the workload variability. In particular, work on fitting MMPP and MAP parameters from workload traces with burstiness is very useful for the analysis of properties, such as performance or availability, of a wide range of systems. However, when we observe workload-aware self-adaptive systems carefully, we realize that their optimal configurations are different depending on the workload they are receiving. Moreover, differences between optimal configurations during the bursty periods and any other period can be huge. These systems should adapt (e.g., provisioning or release of resources) during transient periods, i.e., when the workload is becoming bursty and when the burst of arrivals is finishing. Usually, there is no need for this type of self-adaptive software to change its configuration during stable periods of workload, it should have been adequately provisioned before, in fact during these transient periods. Therefore, to properly analyze the performance or availability of self-adaptive systems under bursty workloads, we need an accurate model of that workload. This model should include transient times, even when they correspond to a small percentage of the total time (the rates normal and burst can last for hours while the change between them lasts just some minutes). Otherwise, results from model-based system analysis can be far away from results of the real working system. The reason is that the system starts the adaptation when it anticipates the workload is close to be bursty. In this way, when the burst of requests arrive, the system is already in its optimal configuration. However, a system model whose workload does not care about transient times is not able to anticipate workload changes, and it will start its adaptations when the bursts of requests are already arriving. This can lead to too pessimistic performance and availability results from the model analysis. In this chapter, we propose a model to take into account these transient periods. We build on the work done in [Gus91, CMCS12] for MMPP and MAP parameter fitting and we extend the generated models to be able to deal with self-adaptation. We start with the description of MAPs and MMPPs in Section 6.2, and we present the research on which we rely for MMPP parameter fitting from a workload trace. Section 6.3 explains the meaning of the transient time and proposes a model for its representation. In Section 6.4 we put together the MMPPs model and the new model for the transient time and we present the aggregated workload model. Using that aggregation of models, we are able to analyze more accurately the extra functional properties of the software. This is illustrated in Section 6.5 through an experimental analysis that shows the difference between considering or not the transient time in the workload model by evaluating the performance and availability requirements of a selfadaptive system. Sections 6.6 and 6.7 present the chapter conclusions and related works, respectively. 6.2 MAP’s and MMPP’s Accurate characterization of real workload traces is a need to devise a proper workload model. For some kind of systems, e.g. networked ones, such characterization should capture the high variability of the requests as well as the fact that they can burst in on the system sometimes [MZR+07]. MMPPs are suitable to model variability and autocorrelation for event generation. An 6.2. MAP’s and MMPP’s 73 MMPP is a stochastic process that has been extensively used to model event arrivals processes and network traffic [FMH93, Gus91, HL86], which is able to represent high variability and temporal dependencies in the arrivals. In an MMPP, the arrival rate at each moment is determined by the state of a continuous-time Markov chain (CTMC). So, when the chain is in state i, the arrival process is a Poisson process with rate λi. An MMPP with Nstates is defined by an NxNmatrix Σrepresenting the CTMC and a vector Λof Ncomponents representing the arrival rates in each state. Σ =       −σ11 σ12 ... σ1N σ21 −σ22 ... σ2N ... σN1σN2... −σNN      ,Λ = (λ1, ..., λN), where ∀i, j, σij ≥0, λi≥0and ∀i, � j:j�=iσij =σii. The research in this chapter considers MMPPs with two states. One of the states will represent the normal arrival rate (and we call it normal) and the other will represent the bursty arrival rate (and we call it bursty). A graphical representation of this two-state MMPP is given in Figure 6.1. λ1, the normal arrival rate, and λ2, the bursty arrival rate, are supposed to be much higher than transitions rates σ12 and σ21. Bursty 12 σ21 λ2λ1 Normal σ Figure 6.1: A two states MMPP A two-state MAP, Figure 6.2, can be seen as a continuous time Markov chain of two states, and the active state defines the arrival rate. In the chain, there can be transitions associated with the arrival of an event (called completion transitions, λij , darker in the figure) and transitions that are not associated with event arrival (called background transitions, σij). Moreover, when the chain is in state i, it can also generate arrivals with rate λii without changing its state, modeled as a self-transition, λii. Formally, a MAP can be defined by two squared matrices D0 and D1, where D0ij, i �=j represents the background transition rates from state ito j,D1ij describes completion transition rates, and D0ii =−(� j:j�=iD0ij +� jD1ij). Thus, Q=D0+D1is the infinitesimal generator matrix of the chain. An MMPP is a MAP that do not admit completion transitions that change the CTMC state, i.e., the elements not in the diagonal of D1must be zero. Then, a two-state MMPP can be seen as a MAP whose matrices D0 and D1 are: 74 6. Workload Modeling for Self-adaptive Software Bursty 12 σ21 λ11 λ22 λ21 λ12 Normal σ Figure 6.2: A two states MAP D0 = � −(σ12 +λ1)σ12 σ21 −(σ21 +λ2) � , D1 = diag(Λ) 6.2.1 MMPP fitting from a workload trace Finding the characterizing values of a trace To fit a real workload trace to a two-state MMPP we just need to set its four parameters: λ1, λ2,σ12, σ21. To this end, we will use four characterizing values from the workload trace. The first value is the index of dispersion for counts (IDC) of the trace. The IDC is frequently used as an estimator of the burstiness in a trace. The higher IDC value is, the more burstiness the trace has. In [Gus91, HL86] it is calculated as IDCt=var(Nt) E(Nt) where Ntis the number of arrival in an interval of ttime units. So, the IDC is the variance in the number of arrivals in ttime units divided by the mean number of arrivals in ttime units. Since we are interested in the index of dispersion of arrivals in the steady state, we calculate lim t→+∞IDCt To calculate the IDC we use the algorithm presented in [MCCS08, CMCS12]. This algorithm is able to estimate the index of disperson IDCt→+∞of a single workload trace. For the rest of the characterizing values we take advantage of the work in [CMCS12], that indeed fits workload traces to MAP caring about the burstiness. Besides the IDC, these values are: the mean inter-arrival time of requests (m), the 50th percentile (i.e, the median) and the 95th percentile. Since in that work the authors are characterizing the burstiness of service times, the burstiness happens for high values of these service times, then making important to know the value for which the 95% of service times are lower. However, we are dealing with inter-arrival times, and the burstiness happens when the values of inter-arrival times are low. 6.2. MAP’s and MMPP’s 75 So, we prefer to know the value for which the 95% of times the inter-arrival time is higher than. For this reason, we use the 5th percentile instead of their 95th. Experiment proposed As example of workload trace, we have used the monitored arrival times of requests to the FIFA 1998 World Cup site [Wor98]. This is the most complete example of workload trace we have been able to find. The timestamps are provided with granularity of one second and we have just used the requests that arrived to the Paris server region. Figure 6.3 shows the count of requests received by this region per minute. Since the workload was very low when the system was started and also the last days after the world cup, we have just concentrated in the middle days. We have used the arrivals of 34.7 consecutive days, then from minute 60,000 until minute 110,000. The arrivals in these 50,000 minutes have been considered in groups of 10 seconds and they are depicted in Figure 6.4. It is easy to see that the shape of the graph depicts a quite bursty workload. The selection of this time interval is not a restriction just to make the fitting algorithm work better but it exemplifies the kind of workloads we are really interested in. Since we are dealing with systems that are intended to continue working in the long term, we assume that the workload should not start and finish being low (as it happened to the World Cup website), but be always in the normal regime. So, we consider the first and last minutes as the system warm up and cool down, and we consider only the world cup days where the system was most used. Figure 6.3: Requests per minute received in Paris region 76 6. Workload Modeling for Self-adaptive Software Figure 6.4: Requests every 10 seconds Fitting MMPP parameters The characterizing values of the trace are the following. The number of requests that we have dealt with is 140,998,569. The mean inter-arrival time of requests is 0.021276 seconds (i.e, close to 47 requests per second), calculated as the number of received requests divided by 3·106(the amount of seconds in 50,000 minutes). The median (percentile 50th) of the inter-arrival times is 0.0159744408 and the 5th percentile is 0.00367 (this is, the inter-arrival time of the 95% of requests was higher than this value). The IDC is 686,200, we admitted a tolerance of 1·10−7for its calculation using the algorithm in [CMCS12]. The amount of time that the algorithm considered approximate to infinite and for which the algorithm stopped was 45,140 seconds. From these characterizing values, we fitted the MMPP. To fit the mean, 50th and 5th percentiles we have used the same equations as [CMCS12]. To fit the ICD, we have used the equation in [Gus91, HL86] that concretely deal with two-state MMPP parameters1. The results are: σ11 =σ12 = 0.0000001314169 σ22 =σ21 = 0.0000273058047 λ1= 45.5395329586 λ2= 350.195877 1This equation is IDCt→+∞= 1 + 2σ12 σ21(λ1−λ2)2 (σ12+σ21)2(λ1σ21 +λ2σ12) 6.2. MAP’s and MMPP’s 77 As expected, we can see that the mean sojourn time in each state, σ−1 12 , σ−1 21 , is orders of magnitude higher than the mean requests inter-arrival times, λ−1 1, λ−1 2. 6.2.2 GSPN workload model An accurate workload model with burstiness, as the one proposed by the MMPP, is necessary for the eventual analysis of systems that execute under such conditions. GSPNs [AMBC+95] are broadly used to model the behavior and workload of systems and also as analyzable models to predict properties of software systems. GSPNs have been used to analyze some properties of self-adaptive software systems, such as performance and energy, as it has been shown in Chapters 3 and 5. Since our workload model should represent the injection of requests in the system in the same language as the behavioral system model, we pursue the proposed MMPP workload model in terms of GSPN. Since both GSPNs and MMPPs represent markovian processes, we can get a GSPN with the same behavior as the MMPP in a quite straightforward manner. This GSPN, the one in Fig. 6.5 representing the two state MMPP in Fig. 6.1, has as many places as states the MMPP, in this case P1and P2(for normal and bursty, respectively). Another place, Parrivals, will mean the injection of requests in the system, i.e. injection of tokens in the GSPN that represents the behavior of the self-adaptive system. The time transitions T12 and T21 represent the MMPP change of state, then their firing rates are σ12 and σ21 obviously. The last two transitions, Tarrival1and Tarrival2, represent the arrival rates in the MMPP, therefore their firing rates are λ1and λ2and they feed the Parrivals place. Parrivals P1P2 T12 T21 Tarrival1 Tarrival2 λ1λ2 σ12 σ21 Figure 6.5: GSPN for the two states MMPP 78 6. Workload Modeling for Self-adaptive Software 6.3 Modeling transient time between states 6.3.1 Problem statement As declared in the beginning of the chapter, a self-adaptive system needs some time to perform corrective actions (e.g., provisioning or release of resources) to fit into the new execution context. In systems whose adaptations depend on workload variations, such adaptations should happen when the system changes from normal to bursty or vice versa, i.e., the system adapts to the environment during the transient times between states. When looking at the real workload trace in Figure 6.6 we observe that such transient time, although fast, is not immediate, it lasts for around 41.6 minutes, starting around 850 and ending around 1100 (1100−850 6= 41.6). The figure shows a period of 250 minutes which corresponds to the zoom in the range from 209,500 to 211,000 in Figure 6.4. The transient time is assumed to be fast w.r.t. the mean sojourn time in each stable state that last for many hours. Our workload model should reflect the transient time accurately since in this period the self-adaptive system: •perceives that the workload is leaving the normal state and the burst of arrivals are near to arrive, and •performs its adaptations to change its configuration to a new one able to withstand the burst of requests. In a two-state MMPP the transient time is not modeled as we can see in Figure 6.7. This figure represents a workload trace generated by the fitted MMPP in Section 6.2 and we observe that the change from normal state (arrival rate around 455 requests each 10 seconds) to bursty state (around 3500 requests during 10 seconds) is abrupt, no transient time is perceived. 6.3.2 Setting parameters of workload model We pursue a GSPN to model transient times in the real workload trace, i.e., the increments and decrements in the arrival rates of the requests. The zones of increment or decrement can be characterized by three parameters: •the well-known λ1and λ2, •the amplitude of the zone, we call it mtinc or mtdec, they are measured in seconds, and they represent the mean amount of time that the workload is increasing from normal state to bursty state or decreasing from bursty to normal respectively, •and additionally, from these parameters we can also calculate the acceleration of the curve in the zone, mrinc or mrdec, in requests ·seconds−2. In the following we describe how these parameters can be obtained from a real workload trace. Algorithm 6.1 shows the case of the calculation of the mean amount of time that the workload is increasing. First (line 1 in Algorithm 6.1), we apply the technique presented in Section 6.2.1 to get λ1and λ2. 6.5. Experimental analysis 85 Σ = 0 B B B B B B B B B B B B B B B B B B B B B B B B @ −σ11 σ12 0... 0 0−σinc σinc 0... 0 ... ... ... 0... 0−σ22 σ22 0... 0 0... 0−σdec σdec 0... 0 ... ... ... 0... 0−σdec σdec σdec 0... 0−σdec 1 C C C C C C C C C C C C C C C C C C C C C C C C A Λ = (λ1, λ1+λinc, ..., λ1+ (w1−1)λinc, λ2, λ1+w2λdec, ..., λ1+λdec) Then, a question arise: could that M-state MMPP be directly obtained from the workload trace using the technique presented in Section 6.2 for two-state MMPP? The answer is yes. Nevertheless, there are some restrictive challenges to obtain the characterizing values of an M-state MMPP. These are: the algorithm to fit parameters of an Mstate MMPP is much more time consuming and the estimation of its parameters are much more prone to inaccuracies. Moreover the current techniques to fit MMPP parameters do not directly deal with our problem (gaining accuracy in the transient times models). 6.5 Experimental analysis In this section, we illustrate the results obtained in our experimentation. To this end we have considered a very simple system with different workload models: first MMPPs and second our GSPN model, that includes the transient time between workload states. A third experiment is used as a benchmark for comparing the accuracy of the obtained results, it is a system simulation having a real workload trace, the one in Figure 6.4. The system we use in this experimentation is a very simple software made of only one activity that requires on average 3ms of processing time 5. There is a single processor executing a maximum of ten concurrent requests, queueing and serving them following a FIFO policy. Requests above ten are rejected. We assume that requirements to architect the system are: •R1availability: at least 99% of requests must be served, and •R2performance: the mean response time should be lower than 1 second. 5To be able to compare approaches without including more variables that can distort results, we assume that the mentioned processing time is exponentially distributed with mean 3ms 86 6. Workload Modeling for Self-adaptive Software Note that the response time is not a critical requirement, since the maximum length of queue of requests to be served is nine, and they are served in a mean of 3ms. On the contrary, requirement R1 is the critical one. When we analyzed the system considering a workload model without burstiness (i.e., taking into account the mean inter-arrival time derived from the real trace), the requirements were satisfied. On the contrary, when taking into account the arrival in bursts, the analysis of the system showed that R1 cannot be guaranteed. A possible solution passes through the addition of a second processing resource. Now, having two processing resources, the system is able to satisfy both R1 and R2 also during bursty periods. However, the second processing resource has been added just to allow the requirements satisfaction during the periods of burstiness, which represents the worst-case scenario for the system. So, during the normal arrival rate periods, there is a waste of resources. We can use the model proposed in Section 6.3 to take into account the workload variability. To this end, we consider a system enhanced with a monitoring component. The monitor is a passive observer that measures the system workload. Then, the monitor notifies to a separate component, which acts as a controller, when the workload is changing and when to add a second processing resource. In the same way, it also decides to switch off one of the processing resources when the workload decreases. So, the system deployment is no longer static but it is dynamically adaptable. It can be seen that we are applying architectural concepts, the monitor and controller are acting as the sensor and adaptation manager of the architecture presented in Chapter 2. We have set the following parameters for the self-adaptive system: •The maximum arrival rate of requests that can be served by only one processing resource is the 80% of its maximum capacity. In other words, the controller decides to add a new processing resource when the workload goes above 1 3ms ·0.8≈266 requests per second. •The maximum arrival rate of requests that can be served using both processing resources is 40 requests per second. When the workload rate is under this value, the second processing resource is shut down. •Booting and shutting down times of the processing resources is one minute. In the following, we explain the set-up of each experiment and the obtained results. After, we compare and discuss results. MMPP workload model As MMPP workload we used the one already calculated in Section 6.2. We composed the MMPP model, in GSPN terms, with the GSPN that models the behavior of the described system. We analyzed the resulting GSPN and obtained the following results: The percentage of requests rejected is 1.43%, so the availability is 98.56%; and the mean response time is 5.3ms. Then, R2 is satisfied while R1 cannot be guaranteed. 6.5. Experimental analysis 87 MMPP with transient times workload model Using the MMPP parameters already calculated in Section 6.2 we applied the process described in Section 6.3 to identify in the trace in Figure 6.4 periods of coarse-grained-constantly-increasing workload. The parameters Land tol have been set to 5 minutes and to 0.2, respectively. Then, the workload parameters mtinc,mrinc,mtdec and mrdec are: mtinc = 5192s mrinc = 0.58requests ·s−2 mtdec = 3770s mrdec =−0.8081requests ·s−2 Following the procedure described in Section 6.3 we defined the structure of the GSPN models for the transient times. We then used the previous results as parameters of these GSPN models. To complete the model definition, we decided the amount of affordable increment in the state space as w1= 10, w2= 9. Using these values, the remaining GSPNs parameters w1, λinc, σinc, w2, λdec and σdec have been derived. The GSPN modeling the workload has been obtained as described in Section 6.4 by composing the MMPP part with the GSPN derived for the transient times. Next, we composed the GSPN workload model with the GSPN that represents the behavior of the system. We analyzed this GSPN and we obtained the following results: The percentage of requests rejected is 0.56%, so the availability is 99.44%; and the mean response time is 5ms. Hence, R1 and R2 are satisfied. Real workload trace execution For validation purpose, we have implemented a simulator of the system described in the example. We run the simulator and we injected the requests following the real workload trace. We have obtained the following results: The percentage of requests rejected is 0.05%, so the availability is 99.95%; and the mean response time is 3.7ms. With the simulation and the real workload both requirements are satisfied. MMPP with Real MMPP transient times trace Availability 98.56% 99.44% 99.95% Performance 5.3ms 5ms 3.7ms Table 6.1: Evaluation results with different input workload 6.5.1 Results discussion Looking at Table 6.1 we can observe that the results obtained with both the MMPP model and MMPP with explicit transient time workload model are pessimistic with respect to the 88 6. Workload Modeling for Self-adaptive Software real ones. Indeed, the analysis of the models produced results showing lower availability and higher average response time with respect to the results obtained by the system simulation using the real workload trace. However, the results obtained with the MMPP including the transient time model are better than the ones obtained with the simple MMPP and closer to the system simulation results. Actually, in this simple example we can see that the expected rejection probability of requests from model analysis with MMPP is 1.43 0.05 = 28.6times higher than the calculated by simulating the real trace. Adding the transient times to the MMPP model, we have reduced this error to be 0.56 0.05 = 11.2times higher; so, we have brought the result a 60% closer to the real one. Besides, the conclusion from the analysis of the model with MMPP workload would be that the proposed adaptive solution for the system does not satisfy the availability requirement. This decision would be wrong because the actual system satisfies it. Regarding the mean response time, adding the transient times to the MMPP model, we have just reduced the error of the results from being 1.43 times the real ones to be 1.35 times. Note that, although all the experiments regarding requirement R1 seem to produce very similar results, this is not the case since availability is used to be measured as the “number of nines”. In other words, if we compare a system with 99% of availability and another one with 99.9%, the latter is not just 0.9% more available than the first one but it is ten times more available. In our experiments, the availability obtained with the MMPP workload model without transient times resulted 28.6 times lower than the availability of the system with the real workload. Adding the transient time between states to the workload model we have been able to reduce the error of around the 60%, of course this is still not enough to guarantee results very close to the real ones. 6.6 Conclusion Modern techniques to model high variable workloads and burstiness are based on markovian models such as Markov arrival processes and Markov-modulated Poisson processes. They offer a powerful theory to model workload. In this chapter, we have identified a need for the accurate workload modeling for self-adaptive systems. This need refers to the modeling of the transient time between workload states in the presence of burstiness. This transient time is not modeled in MMPPs, because they focus on modeling stable workload states. Although these transient times may not be important for static systems or workloads without burstiness characteristic, they are crucial when analyzing bursty worklodaware self-adaptive systems. To solve this challenge we have built on previous results on MMPP fitting and we have proposed a model based on Petri net taking into account the arrivals during the transient time between states. The obtained model has then been integrated in a Petri net describing the MMPP, so allowing a more complete representation of the workload. A first experimentation comparing the results obtained with the proposed model and the classical MMPP models tested against a real trace workload, showed an increment in the analysis accuracy when transient times are taken into account. Besides, from our experimentation we have shown that we have reduced the errors in the analysis results; although there is still a gap between model analysis results and real 6.7. Related work 89 simulation ones. A direction that deserves further investigation is the representation of the workload transient times when there are more than two stable states. In these cases, the MMPP that models the stable states has more than two states. Since the addition of the transient time models increases the state space of the model to analyze, it may not be appropriate to represent the incrementing and decrementing transient times between any two states. Contrarily, we should search which state transitions deserve attention to model their transient times and which ones do not deserve it. 6.7 Related work The parameter fitting of Markovian models such as MMPPs and MAPs is an extensive research field. For example, works [HL86, HT02, OD09, Gus91, Ryd96, CZS10, CMCS12] propose MAP and MMPP parameter fitting techiques starting from traffic traces. Some of these fitting works also deal with the modeling of burstiness characteristic and use the index of dispersion as burstiness estimator. This chapter builds on the results obtained in [Gus91, CMCS12] to choose the estimators of the workload trace and fit a two-sate MMPP that models the same characteristics as the workload trace for these estimators. However, to the best of our knowledge, our work is the first one modeling the transient times between workload states and using them when evaluating workload-aware self-adaptive systems. 90 6. Workload Modeling for Self-adaptive Software Chapter 7 Measuring and Correlating System Adaptability Previous chapters dealt with system properties that can be quantified: performance and energy consumption. However, adaptability property was considered as a purely qualitative property: a system can be non-adaptive or self-adaptive; and usually only these two states are distinguished. Once a system is classified as self-adaptive there is not any manner to compare its adaptability with the adaptability of other systems; it is not possible to rank them attending to adaptability. The goal of our research in this chapter is to overcome this limitation and to enable comparison of software systems regarding their adaptability. 7.1 Problem statement Adaptability is a property that can be evaluated at different stages of the application development, e.g., at architectural level. Indeed, in recent decades, software architecture has emerged as an appropriate level for dealing with software behavior and qualities [CKK01, SW02b, BCK05] and several efforts have been devoted to the definition of methods and tools able to facilitate the actual system development and to evaluate quality at the architectural level (see, for example, [BCK05, BDIS04, DN02, SW02b]). In this chapter, we propose the definition of metrics allowing the description and the evaluation of the system adaptability at the architectural level. We believe that the existence of metrics able to quantify (even if in a simple way) the system adaptability could provide a key capability for the development of systems that can adapt when necessary. These metrics can allow the comparison of different possible architectures with respect to their potential for adaptation. Besides, we argue the importance of defining a relationship between the adaptability and the quality properties of the system. Our metrics can then be used to drive the system adaptability in order to meet the overall QoS requirements. Moreover, the metric definition can be seen as a first step towards future research on formal approaches for the evaluation of system adaptation. 91 92 7. Measuring and Correlating System Adaptability The idea of defining metrics for quantifying software adaptability is not new. This idea was first proposed in [SC01] and then refined in [RM09]. Our approach is built on these previous works and improve them by presenting a wider set of metrics and by defining the aforementioned relationship between them and the quality requirements. Indeed, adaptability can influence software qualities such as performance, reliability or maintainability and in the worst case, improving the adaptability of a system could decrease other qualities. Finding the best balance between different, possibly conflicting quality requirements that a system has to meet and its adaptability is an ambitious and challenging goal that this research pursues. As a first step towards this goal, in this chapter we present a method for evaluating the relationships between the system adaptability and two qualities, concretely availability and cost. Far from being “a solution for every situation” these metrics and relationships can enable software architects to discover suitable architectures leading to quality requirement satisfaction. The obtained adaptability values of each requirement can then be combined to evaluate the various trade-offs and decide whether there exists an architecture that fulfills all client requirements. The required input to perform these tasks concerns the execution context, in terms of existing or planned software resources, and their quality attributes. The evaluation of architecture alternatives is executed when the software architect should take into account, for example, the introduction of new clients, or changes either in already known clients requirements or in the context (in terms of its existing elements or the quality attributes of an element) possibly preventing the clients satisfaction. After the generation of the knowledge about a suitable set of architecture solutions that fulfill the requirements, software architects will choose one solution based either on client desires or on any ownsystem preference. The rest of the chapter is organized as follows: Section 7.2 describes the proposed metrics for quantifying the adaptability of a software. Section 7.3 investigates relationships between the adaptability metrics and extra functional requirements. We apply this approach to a simple example in Section 7.4. Section 7.5 presents a trade-off analysis among different extra functional requirements. Sections 7.6 and 7.7 complete the chapter by explaining our conclusions and describing the related works. 7.2 Architectural adaptability quantification This section presents the definition of some metrics for quantifying the adaptability of software systems at architectural level. The goal of these metrics is to give a means for evaluating the potential of the system to adapt rather than a description of how the the system will adapt. 7.2.1 Architectural assumptions For the metrics definition we refer to an architectural description formed by components (hereafter denoted as software unit) and connectors. We will use the UML component diagram to represent them, see Figure 7.1. By software unit we mean for example components, in the context of component-based software engineering, or Internet services, probably provided by third-parties, in the context of SOA. The connectors in our description represent the 7.2. Architectural adaptability quantification 93 relationships between the different software units and indicate, for example, that a software unit requiring a service is connected to other software units offering the service. By software unit of interest we mean a software unit chosen by the architect, among all available in the market, as candidate to make up the system. In the example, the system offers functionality f1 exclusively through SU11, which in turn needs f2 (offered by SU21 and SU22) and f3 (by SU31,SU32 and SU33). Therefore, SU1={SU11},SU2={SU21, SU22}and SU3={SU31, SU32, SU33}. The units of interest are in grey, E1={SU11},E2={SU21}and E3={SU31,SU32}, then the only adaptable functionality is f3, since there is not any choice for modifying f1 and f2 provider. SU11 <<delegates>> COTS f1 f3 SU21 SU22 f2 f1 SU31 SU32 Third party services f3 in−house component SU33 Figure 7.1: System example In the component diagram we identify a functionality with a service. The interface for an offered service is represented by a ball, while the required one by a semicircle, see Figure 7.2(a). When we need to combine several interfaces for the same service (as in Figure 7.2(b)), we simplify as in Figure 7.2(c), which means that both, SU11 and SU12, need f3, which is offered either by SU31 or SU32 or SU33. We do not make assumptions about which software unit is actually invoked and how. SU11 SU12 SU32 SU33 SU31 f1 f1 f3 f3 f3 f3 f3 SU31 SU33 SU11 SU12 f1 f3 f1 f1 f3 f3 f3 f3 SU11 SU31 SU32 SU33 SU12 SU32 (a) (b) (c) f3 Figure 7.2: How to interpret interfaces We will also assume: a) a system requiring ndifferent functionalities, fi|i={1..n}; b) the existence of nsets of software units, SUi, each set offering an fi. Then, for each fi, an architect can select a subset of software units of interest, Ei⊆SUi1. 1Note that to create the architecture of a non adaptable functionality fi, it is enough to select one software unit that offers it; therefore |Ei|= 1. 94 7. Measuring and Correlating System Adaptability For the sake of simplicity, we avoid to represent software entities devoted to manage the infrastructure of the self-adaptive system2. In fact, we consider them as aggregated to the functional software units, i.e., a new software unit is assumed to add to the infrastructure a new proportional complexity for its managing. It is well-known that there exist software units that expose mechanisms to manage their adaptability. For example, a software unit devoted to perform heavy graphics computations can offer on-demand settings to set the accuracy of the computation. In this case, we assume each on-demand setting as a different software unit providing the target functionality. Naturally, we suppose a discrete and finite number of settings. Figure 7.3 depicts an example for an hypothetical software unit that exposes two settings, i.e., two choices for the system to adapt f1. SU1 = {SU1, SU2} f1 SU f1 SU SU2 f1_normal f1 f1_accurate Figure 7.3: Adaptable software unit 7.2.2 Adaptability metrics Absolute functionality adaptability index (AFAI) represents the number of software units of interest for a given funtionality. AFAI ∈INn|AFAIi=|Ei| Inspired by the element adaptability index in [SC01], here a natural number, instead of a boolean one (0 no adaptable, 1 adaptable), quantifies how much adaptable the functionality is. Referring to the example in Figure 7.1, we observe that AF AI = [1,1,2]. Relative functionality adaptability index (RFAI) represents, for a given functionality, the number of software units of interest w.r.t. the number of units actually offering such functionality. RFAI ∈Qn|RFAIi=|Ei| |SUi| 2Those necessary to: make requests compliant with the actual interfaces; monitor the behavior of the functional software units, and; develop the logic that manages the adaptation. 7.4. Example 101 Table 7.3. Web application example Generic Notation Student registration f1 Student requirement satisfaction f2 Send email f3 Bank payment f4 Presentation and notification component SU11 Presentation and notification + application logic component SU12 Application logic 1 SU21 Application logic 2 SU22 Third-party email provider 1 SU31 Third-party email provider 2 SU32 Local email provider SU33 Bank 1 payment service SU41 Bank 2 payment service SU42 Table 7.3: Notations relationship Note that Figure 7.7 slightly increments Figure 7.1 example by adding functionality f4 and software units SU12,SU41 and SU42. We assume that the quality requirements to fulfill are the system availability shall be higher than 0.9, and the system cost shall be lower than 30 monetary units. Availability means “readiness for correct service” [ALRL04], while the cost property simply describes the price of the set of software units that will make up the system. For the rest of the example, we differentiate software units as terminals and non-terminals. Terminals are those not needing other functionalities (e.g., SU31 or SU32), while non-terminals do need (e.g., SU11 or SU12). Note that in the example some software units offering the same functionality are not completely replaceable. For example, SU11 cannot completely replace SU12, since the former needs f2but not f4, and the later needs the opposite. System operational profile In the components diagram we depict the quantitative information needed to compute the system availability and cost. For simplicity, this information appears inside the components and in the contiguous table. However a more formal approach, like the MARTE [Obj05] standard profile, could be used. •Pfj imeans for a software unit i, the probability of requiring functionality j. •Nfj imeans for a software unit i, the mean number of requests to functionality j. 102 7. Measuring and Correlating System Adaptability <<delegates>> P <<delegates>> f3 f4 cost=4 availability=0.92 cost=4 availability=0.98 f3 f2 availability=0.9 cost=7 availability=0.95 cost=8 availability=0.85 cost=2 availability=0.93 cost=1 availability=0.95 cost=1 availability=0.9 cost=4 availability=0.95 SU31 SU32 SU12 SU11 SU33 SU21 SU22 SU42SU41 f1 cost=4 X=SU22X=SU21 , ,2 1 0.9 0.1 ,, , 0.9 , X=SU12X=SU11 0.8 1.0 0.5 2 3 5 1 x f3 N f4 ,x f3 P , f2 x x f2 NP Nx,x f4 Figure 7.7: The architecture of a complex -w.r.t. adaptabilitysystem •The availability of a software unit is a measure obtained from the third-party provider or monitoring the software unit. •The cost of a software unit is the value we pay to a third-party provider for using it. Pfj iand Nfj icould be combined to form the “mean number of requests per execution”, however we prefer to keep them separated for the sake of system availability computation. For example, we could need to call a software unit only for the 20% of our executions, but we have to call it five times per execution; for another software unit, it may happen that we have to invoke it once for each execution. In both cases the “mean number of requests” is one. However, in the latter case all the system executions are prone to fail depending on the availability of the software unit, while in the former, the remaining 80% of executions are safe. 7.4.1 Computation of system qualities Availability computation. Definition 7.1. The availability of a terminal software unit is the one annotated in the diagram. E.g., Av(SU31 ) = SU31 .availability = 0.9. 7.4. Example 103 Definition 7.2. The availability of a functionality fiis: Av(fi) = 1 −� suij ∈Ei (1 −Av(suij)) (7.1) A functionality is available if any of the components in Ei(as defined in Section 7.2) is available. For example, if E3={SU31 ,SU32 }, then Av(f3) = 1−(1 −0.9) ·(1 −0.95) = 0.995 (note that all components providing f3are terminals). When Eiincludes non-terminals, we previously compute the availability of the nonterminals. Definition 7.3. The availability of a non-terminal is: Av(suij) = suij.availability ·� fk∈RF (suij ) ((1 −Pfk ij ) + Pfk ij ·Av(fk)Nfk ij ) where RF (suij)is the set of functionalities suij requires. For example, RF (SU12 ) = {f3, f4}, if we consider E3={SU31 ,SU32 }and E4= {SU42 }. Then, Av(f4) = 0.98 and Av(SU12 ) = 0.85 ·((0.1 + 0.9·0.983)·(0.5 + 0.5· 0.9952)) = 0.801. Definition 7.4. The system availability is recursively computed from the main functionality using equation (7.1). In our example, if we suppose the architecture made of SU12,SU31,SU32 and SU41, then the result is: Av(f1) = 1 −(1 −Av(SU12 )) = 1 −(1 −0.801) = 0.801. Cost computation. Definition 7.5. The cost of the system is: Cost =� i � cij ∈Ei cij.cost For example, the cost of a system made of SU11,SU21,SU31,SU32 is 2+1+4+7 = 14 monetary units. The calculation of the availability is a simple but interesting method we propose in this example. However, for the calculation of the cost, we recognize it to be simplistic3, yet we consider that the focus of the work is on trade-offs between qualities. 3We have not considered deployment costs, developed cost or distinguished among advanced payment manners to service providers such as payment for execution requests, payment for temporal contract or payment for a COTS component acquisition. 104 7. Measuring and Correlating System Adaptability (a) (b) Figure 7.8: (a) Relation among ASAI and availability (b) Relation among ASAI and cost 7.4.2 Relation of adaptability to availability and cost Applying to our example the models of computation in Section 7.4.1 we discovered that the availability requirement belongs to Helps since the availability increases when the adaptability does and it is required a value higher than a given threshold (0.9). On the other hand, the cost requirement belongs to Hurts, since the cost increases when the adaptability does and the requirement is lower than. From the metrics presented in Section 7.2 we have used ASAI (the number of software units that compose the system w.r.t. the number of the software units that could be used). Following the method presented in Section 7.3 we created the corresponding graphs, we started considering the architecture made of only one unit A0= 1. Moreover, since we are not assuming a maximum adaptability, then AdaptMax = 1. It is worth noticing that although any metric in Section 7.2 can be used for this study, we have chosen one of the simplest for the sake of clarity. For example, vectorial metrics prevented us from showing the results in graphical form, since there would be necessary n+ 1 dimensions to depict the relation, while scalar ones are represented in 2D graphs. Graph to relate adaptability and availability For A0= 1, the selected software unit should be the one providing the main functionality f1, i.e., SU11 or SU12.SU11 shows an availability equals to 0, since it needs to request f3with probability 1, but f3is not available at present. SU12, instead, shows an availability equals to 0.0425. Figure 7.8(a) depicts the lower and upper bounds of the system availability for each value of ASAI. The graph shows the existence of solutions satisfying the requirement, i.e., architectures with availability higher than 0.9. The first suitable solution is for an ASAI equals to 5 9software units, then Adapt−=5 9. In this case the availability is 0.954 and the architecture is made of E1={SU11, SU12},E2={SU22},E3={SU32}and E4={SU42}. For informative purposes we computed all the metrics for this solution, see second column in Table 7.4. 7.4. Example 105 Regarding Adapt+, the graph clearly shows that all architectures with ASAI >7 9fulfill the required availability4. For ASAI =8 9, the lower bound (worst architectural alternative) offers an availability of 0.9271. In such case, the system is made of E1={SU11},E2= {SU21, SU22},E3={SU31, SU32, SU33}, and E4={SU41, SU42}. Third column in Table 7.4 shows the other metric values for this architecture. Graph to relate adaptability and cost We apply again the method in Section 7.3 to compute in this case the cost of the system for each value of ASAI, from A0=1 9to AdaptMax = 1. Results in Figure 7.8(b) show that it is possible to find solutions satisfying the requirement up to an ASAI =8 9. Moreover, all architectures with ASAI lower than 7 9will satisfy the requirement. Again, for informative purposes, we computed all the metrics for the values of Adapt−and Adapt+, they appear in Table 7.4. n= 4 |SU1|= 2 |SU2|= 2 |SU3|= 3 |SU4|= 2 Availability Cost Adapt−Adapt+Adapt−Adapt+ AFAI [2,1,1,1] [1,2,3,2] [2,1,2,1] [1,2,3,2] RFAI [1,1 2,1 3,1 2][1 2,1,1,1] [1,1 2,2 3,1 2][1 2,1,1,1] ASUI 5 8 6 8 MFAI 1.25 2 1.5 2 MRSAI 0.58˙ 3 0.875 0.˙ 6 0.875 ASAI 0.˙ 5 0.˙ 8 0.˙ 6 0.˙ 8 Table 7.4: Metric values of the architectures in Figure 7.8 for bounding values QAdapt−Uand QAdapt+L Adaptability, availability and cost Putting together both studies, we can foretell that: •No suitable architecture can be found for an ASAI <5 9or an ASAI = 1, since either the requirement of availability or the one of cost cannot be satisfied. •There are suitable architectures for values of ASAI =5 9, ASAI =6 9and ASAI =8 9. •There can exist suitable architectures for ASAI =7 9. 4We remark that, following indications in Section 7.3, the non-suitable architectural alternatives have been discarded. 106 7. Measuring and Correlating System Adaptability 7.5 Relating quality requirements We have hitherto proposed an approach to relate system adaptability to availability and cost. To make this approach easily applicable our goal is to define an automated framework that effectively assists to architect a system that meets several quality requirements within an adaptability threshold. To this end we formalize below these relationships. Definition 7.6. Let us define Reqs as the set of the requirements of the system. RHelps and RHurts as the requirements that respectively belong to Helps and Hurts as in Table 7.2. Then, Reqs =RHelps ∪RHurts. Definition 7.7. ∀req ∈RHelps, we define MAdapt−=max(Adapt−)and MAdapt+= max(Adapt+)and ∀req ∈RHurts, we define mAdapt−=min(Adapt−)and mAdapt+=min(Adapt+). Definition 7.8. We define ADAPT(arch)as the adaptability value of architecture arch, while SAT (arch, req)means that arch satisfies req. Proposition 7.9. When (MAdapt−≤mAdapt−)∨(MAdapt+≤mAdapt+)(7.2) then ∀Ai∈[MAdapt−, mAdapt−]∨[MAdapt+, mAdapt+],∃arch |ADAPT(arch) = Ai∧ ∀req ∈Reqs, SAT (arch, req). Proposition 7.10. When (MAdapt−≤mAdapt−)∧(MAdapt+≤mAdapt+)(7.3) then (∀Ai∈[MAdapt−, mAdapt−]∩[MAdapt+, mAdapt+]) ∧ (∀arch |ADAPT (arch) = Ai)−→ ∀req ∈Reqs, SAT (arch, req). Obviously, (7.2) and (7.3) are sufficient conditions, when they do not hold, we can at least assess whether it is impossible to fulfill the requirements. This is guaranteed by proposition 7.11. Proposition 7.11. When mAdapt+< MAdapt−(7.4) then �arch | ∀req ∈Reqs, SAT (arch, req). Otherwise, if neither (7.2) nor (7.4) hold, then it cannot be proved the existence or absence of architectures that satisfy the requirements. However, if such solutions exist, then their adaptability values must belong to the interval: [MAdapt−, mAdapt+]∩[mAdapt−, MAdapt+](7.5) Proof. Section 7.5.1 sketches the demonstrations of 7.9, 7.10 and 7.11 graphically. 7.6. Conclusion 107 7.5.1 Graphical representation We use the location in the graph of MAdapt−,MAdapt+,mAdapt−and mAdapt+to show the propositions above. So, they can be arranged up to 4! different permutations. However, since by definition MAdapt−≤MAdapt+and mAdapt−≤mAdapt+, then the amount of permutations is reduced to 4! 2!2! = 6. Figure 7.9 depicts these six possible scenarios. Suitable architectures appear only in scenarios (a),(b),(c) and (e). For the sake of simplicity, we have considered |RHelps|=|RHurts|= 1. The symbols in the figure have to be interpreted as follows: •The symbol ‘∃’ represents a region where condition (7.2) holds, then ensuring the existence of at least one architectural solution for each adaptability value in such interval. •The symbol ‘∀’ represents a region where condition (7.3) holds, then ensuring that all architectures within the region satisfy all requirements. •The symbol ‘�’ represents a region where none architecture satisfies all requirements. For example, in Figure 7.9(f) the �symbol covers the entire region because here formula (7.4) holds. •The symbol represents a region where condition (7.5) holds, then it is not possible to prove the existence or absence of architectures satisfying the requirements. 7.6 Conclusion In this chapter, we have presented a set of metrics helpful to quantify and evaluate the adaptability of software systems at the architectural level. Besides, we have defined a relationship between these metrics and the quality requirements of the system. The approach can be used during design time to help software architects in the generation of a suitable adaptable architecture. One of the aims related to the definition of metrics is the possibility to have some means for the evaluation and comparison of different systems in terms of adaptability and quality requirements. A trade-off analysis in this case should be carried out in order to take the decision that better fulfills the various stakeholders needs. The approach can be improved along several directions. We are extending the set of metrics and applying them to a great many case studies to guarantee their usefulness also from a statistical viewpoint. Specifically, we are working towards the inclusion of aspects such as the “criticality” or “importance” of the offered functionalities, adding for example, some reasonable weights to our metrics and defining new metrics that include this concept. We plan also to relax the constraint requiring that each software unit offers a single functionality. This is not a trivial step since it requires to take into account also the interdependencies between the different offered functionalities and their quality requirements and it would probably entail a definition of new adaptability metrics. 7.7. Related work 109 ware architects to compare adaptive system designs with the system design without adaptability. Finally, the development of an automatic tool that implements the approach would bring several benefits. One of these benefits is that this tool would allow the integration of the approach at runtime -when human intervention is not possible-. Autonomic systems would benefit from the integration at runtime since they can need to re-architect themselves, and this approach would offer a set of suitable adaptability ranges to guide the re-architecting process. 7.7 Related work The set of metrics we offer in this chapter is strongly inspired by the one in [SC01], work in which authors also give a set of metrics for adaptability applicable at architectural level. Our extension aims at supporting a higher degree of quantification starting from the most basic metric. In our approach, the metric itself does not only track if a required functionality of the system is adaptable or not, but we also quantify how much adaptable it is by means of a natural number. The same authors propose in [CS01] a framework that is a specialization of a general qualitative framework to reason about non-functional requirements [CNYM99, MCL+01]. That framework is concentrated on adaptability requirement and works with quantitative values. Our work, on the contrary, is based on the addition of adaptability property to systems in order to make such systems able to meet also the non-functional quality requirements. In [RM09, KRG+10], the authors wonder whether it is possible to measure and evaluate the adaptability of systems in order to compare different adaptive solutions. To take a step forward, they propose a set of quantitative metrics grouped by categories. These metrics are calculated statically. However, their approach can be extended to be applicable in a dynamic environment. In this direction, we foresee a possible integration between the metrics defined in this chapter and the approach proposed in [RM09, KRG+10]. Indeed, our approach can be used to discover which are the suitable architecture adaptabilities that can make the system able to meet the desired quality non-functional requirements, and then use their higher-level metrics to offer an evaluation and comparison of the already calculated suitable architectures. In [RWvM10], authors define a methodology to evaluate the adaptivity of a system. This evaluation is based on measurement traces or simulation traces that can be obtained, in testbeds, real systems or software tools for discrete-event simulation. Besides, this methodology is enhanced with the definition of a simple metric that evaluates adaptivity on a scale from zero to one. In [YHZ+09] a trade-off analysis among quality properties of adaptive systems is presented. This approach takes into account changes in runtime contexts and the decision to adopt an adaptation strategy is performed during runtime, when the system knows the current real context. To achieve that goal, the authors propose a three-phases methodology, where the firsts two phases are done during design time and the third one is executed by the system during runtime. The phases are: (i) analyze the target architecture to find trade-off points among qualities, (ii) design different adaptive strategies and record them in the architecture model, (iii) deploy the system collecting context information and selecting the best strategy during runtime. 110 7. Measuring and Correlating System Adaptability With respect to existing work, in this chapter we propose a more extensive set of architectural metrics that can be used in the quantitative evaluation of software adaptability. These metrics have been empowered with the definition of explicit relationships between adaptability and quality values, such as availability and performance. Chapter 8 Model To Model Transformations: From CSM To GSPN In this chapter we present part of our research in model-to-model transformations for software performance evaluation. We describe the transformation theory between an intermediate model and an analyzable model. The source model is a Core Scenario Model (CSM), which is a scenario-oriented intermediate performance model that filters out the information unrelated to performance in a software design, and the target model are GSPN, which are a formal and analyzable modeling paradigm that have been shown feasible for software performance evaluation. In this chapter we also describe a tool that implements such transformation. 8.1 Problem description The assessment of software non-functional properties such as performance, is a challenging issue for the software engineering community. Software Performance Engineering (SPE) [Smi90] promotes the use of standard design languages like the Unified Modeling Language (UML) [BJR99] and associated OMG standard profiles, with the aim of leveraging software designs for a prediction of system performance [BDIS04]. The OMG-MARTE (Modeling and Analysis of Real-Time and Embedded systems) [Obj05] profile augments a UML design with information relevant for performance prediction. In the work carried out in Part I, we needed to evaluate performance of software systems under different configurations and execution environments. Owing to the research already done in the SPE community, we decided to heed their proposals to ease our task. SPE proposals work on both types of model-driven evaluation: direct transformations of design models into performance models, and transformation paths that include intermediate models between design and performance models. The work in [BDIS04] summarizes some of the main proposals regarding the former approach, while for example, works in [DSP11, GMS07a, WPP+05] follow the latter. As motivated in previous introduction, we decided to follow the latter approach. In this chapter, we present our research in the model-to-model 117 118 8. Model To Model Transformations: From CSM To GSPN transformation from the intermediate model CSM [PW07] to the analyzable model GSPN [AMBC+95] and its automation. CSM language is fully described in [PW07]. A CSM model represents software execution scenarios in terms of well-known performance concepts: steps, workloads, path connectors or resources. In [PW07] it is also explained the model-to-model transformation from UML designs to CSM. Besides, CSM language was proposed in [WPP+05] as intermediate language within the Performance by Unified Model Analysis (PUMA) framework, which is an open architecture that enables the integration of performance analysis in different kinds of software design tools. In that work, there are outlined the model-to-model transformations from CSM to queueing network models (QN), layered queueing network models (LQN) and GSPN. This chapter extends the description of CSM to GSPN presented in [WPP+05], it presents the tool and algorithms we have developed for the transformation of a CSM into a performance model in terms of GSPN. The GSPN can be analyzed or simulated by using engines such as GreatSPN [Gre] or TimeNET [ZFGH00]. Our tool implements a CSM-GSPN “compositional” translation and uses software standards, such as XML [XML] format. This fact also enables a future integration of the tool within the PUMA architecture. The compositional issue forced us to define a composition operator for GSPN, we present it in appendix B. The rest of the chapter is organized as follows. Section 8.2 recalls the needed background, the CSM meta-model. Section 8.3 details how CSM concepts are converted into the GSPN models. Section 8.4 describes the tool issues and lessons learned in its development. Section 8.5 applies CSM to GSPN transformation to a case study taken from literature [XWP03], presents performance results and compares them with those obtained using layered queuing networks (LQNs) as performance model. Section 8.6 gives a conclusion. 8.2 Core Scenario Model The goal of the CSM metamodel is to capture the essentials for building performance models. The class structure of the CSM is shown in Figure 8.1, it corresponds to the one presented in [PW07], however we have added two new abstract classes: the VertexOperation and the ResourceManager. The CSM represents the performance Scenario flow via a PathConnection type. There is a PathConnection object between each pair of VertexOperations. Indeed, the VertexOperation class has been introduced to distinguish Steps from ResourceManagers. So, a Step is a sequential piece of execution which may in turn be refined as a scenario. While a ResourceManager only manages the resource utilization of steps. The subtypes of PathConnections correspond to the common sequential relationships: branches, merges and forks and joins. A scenario has a Start point and End points. Start points may associate a Workload, then representing the scenario usage. There exist two kind of Resources: Active, which execute steps, and Passive, which are acquired and released during scenarios by special ResAcquire and ResRelease operations. Steps are executed by (software) Components which are passive resources. In turn, Components are associated to the ProcessingResource in which are hosted. CSM meta-classes own attributes defining their properties. For example a Step has the HostDemand to describe its aggregate use of its host resource (CPU). Table 8.1 gathers the 8.3. CSM meta-classes translation 119 CSM Scenario Step General Resource Active Resource Passive Resource External Operation Processing Resource Open Workload Closed Workload Path Connection Component Sequence Branch Merge Fork Join End Start Workload Resource Acquire Resource Release Message 1..* 1 1..* +host 0..1 0..1 0..1 mn +source +target +predecessor +successor 2..* * (m=1,n=1) (m=1,n=2..*) (m=2..*,n=1) (m=1,n=2..*) (m=2..*,n=1) (m=1,n=0) (m=0,n=1) VertexOperation Resource Manager 1..* 0..1 * +subscenario 0..1 Figure 8.1: Core Scenario Model attributes used in this work, the whole list can be found in [PW07]. Figure 8.13(a) depicts a simple example of CSM, where we observe the start and end Vertices, the acquisition and release of a resource, the workload and a couple of Steps - cycleInit and procOneImage-. Figure 8.13(b) is a more complicated CSM which indeed refines the procOneImage Step in Figure 8.13(a). 8.3 CSM meta-classes translation This section presents the set of patterns that we propose to represent CSM meta-classes. These patterns are at the core of the translation and they will be used by our tool to convert a CSM model into a GSPN [AMBC+95]. A pattern in this context is actually a GSPN subnet parameterized with the attributes of the CSM meta-class the subnet represents. The places and transitions of the GSPN subnets are named as name |label 1|... |label n (e.g., t1|getImage|disk release). These labels refer names of the CSM model elements and they will be useful to keep track of the CSM operations and to eventually compose the subnets. In the following, we describe for each CSM meta-class, the 120 8. Model To Model Transformations: From CSM To GSPN CSM meta-class Attribute name Scenario ID1, Name GeneralResource ID, Name, Multiplicity ActiveResource Same as GeneralResource + OperationTime ProcessingResource Same as ActiveResource VertexOperation ID, Probability Step Name, HostDemand, ExtOp, RepetitionCount ResourceManager ResourceUnits, Priority OpenWorkload ID, ArrivalPattern2, ArrivalParameter3 ClosedWorkload ID, Population Message ID, Kind4 1. ID means a unique identifier. 2. [Poisson |periodic |phase-type] 3. The ArrivalPattern description. 4. [async |sync |reply] Table 8.1: Some attributes of some CSM meta-classes GSPNs subnets patterns implemented by the tool. 8.3.1 Step translation We revise now all different options to translate a Step. The choice is based on the values of the attributes of the Step: Name, HostDemand, ExternalOperation, RepetitionCount and Probability. The latter inherited from VertexOperation. The ExternalOperation refers to a service external to the model. •Figure 8.2(a) depicts the subnet for a “dummy” step, i.e., a step that only has a Name but the rest of the attributes are not used. This step, as explained in [PW07], is only used to link PathConnectors, e.g., for linking two consecutive branches. The translation provides a subnet with one place and one transition, both labeled with the name of the Step. •When the Step declares a Name and a HostDemand, then the subnet is the one in Figure 8.2(b). Transition t2is an immediate one and it will be useful to acquire the processor or host where the Step executes. Transition t1is exponentially distributed with firing rate 1/HostDemand, it will also release the execution host. The labels host acq and host rel are generic for all the translations in this subsection. Algorithm 8.1 will change the word host for the actual name of the host that executes this step. At this moment this information is not known because it is not stored in the Step. 8.3. CSM meta-classes translation 121 •A Step with Probability is translated as in Figure 8.2(d), which reflects the two flows that the system can follow, the one that really executes the step (right part) and the one that avoids it (left part). There is a special case, the Step with Probability that is preceded by a Branch connector, indeed all the successor Steps of a Branch have a probability of execution. In this case, pattern in Figure 8.2(c) is applied and this translation will be composed with the one of the Branch as given in Figure 8.4(e). •Pattern in Figure 8.2(e) gives the translation for Steps with RepetitionCount. The RepetitionCount is simply the mean number of times the step repeats when executed. The probabilities for transitions t5and t6are pand 1-prespectively, where p=RepCount/(1 + RepCount). •When the Step has both, Probability and RepetitionCount, then it mixes the two previous translations. Figure 8.2(f) depicts the solution to mix (d) and (e), the mix of (c) and (e) is a trivial one. •Sometimes a Step is refined by a sub-scenario, as expressed by the association between the Step and the Scenario in Figure 8.1. This means that the engineer will refine the specification of the Step. In this case, the Step does not declare a HostDemand since it is implicitly aggregated by the demands of the steps in the sub-scenario. Figure 8.2(g) depicts the translation: place p1will be composed by algorithm 8.1 (later described in Section 8.4) with the starting point of the subnet of the sub-scenario and transition t1with the ending of the scenario, hence the sub-scenario will be integrated into this subnet. Figure 8.2(h) depicts the most complex situation, i.e., the Step that represents a sub-scenario with RepetitionCount and Probability. The cases of a sub-scenario Step with RepetitionCount or with Probability are particular cases of (h). 8.3.2 Resource translation Resources involve two main classes of the CSM in Figure 8.1: the GeneralResource for their definition and the ResourceManager for their management, i.e., their acquisition and release. As previously explained, a resource can be active or passive, the active resources can be external operations or processing resources. For the GeneralResource class its attributes are Name and Multiplicity (number of units, e.g., number of buffers). The ActiveResource classes adds the OperationTime attribute. When the Multiplicity of a resource is infinite there is no need for it to be translated, since the resource can be shared at any time by any number of execution steps. Figure 8.3(a) depicts a part of a CSM model with a passive resource –DB component– and the active one where it executes, the CPU for the DB. The component is explicitly acquired and released by the corresponding ResourceManagers (ResAcq and ResRel). Active and passive resources are translated the same way, as given in Figure 8.3(b,c). They are modeled by: a) a place with as many tokens as the Multiplicity indicates, one in this case, b) an input transition modeling the release of the resource and c) an output transition modeling its acquisition. Labels refer the name of the resource as well as its acquisition and release. 122 8. Model To Model Transformations: From CSM To GSPN Step::dummy p3|getImage t3 π = 0.6 t4|getImage π = 0.4 (a) (c) (b) (d) p2|getImage t1|getImage |host_rel t1|getImage |host_rel p1 t5 π = 10/11 t6|getImage π = 1/11 p1 p3|getImage t3 π = 0.6 t4|getImage π = 0.4 t1|host_rel p4 (e) t2|host_acq p1 t2|host_acq p2 p3|getImage p2 t5 p1 p2 t2|host_acq t1|host_rel t2|host_acq t6|getImage π = 1/11 π = 10/11 p3|getImage p1 t1|getImage |host_rel t3 π = 0.6 p2 t2|host_acq t5 π = 10/11 t6|getImage π = 1/11 p1|start_Sce p3|getImage t3 π = 0.6 t4|getImage π = 0.4 t1|end_Sce p4 (f) p2 t1|dummy p1|dummy (h) HostDemand=2 sec. HostDemand=2 sec. Probability = 0.6 HostDemand=2s RepCount = 10 HostDemand=2 sec. Probability = 0.6 +subscenario="subScen" Probability = 0.6 HostDemand=2 sec. Probability = 0.6 RepetitionCount = 10 RepetitionCount = 10 Step::getImage λ=1/2 Step::getImage Step::getImage λ=1/2 λ=1/2 Step::getImage λ=1/2 λ=1/2 Step::getImage Step::getImage Branch Branch p1|start_subScen p3|getImage t1|end_subScen|getImage p2 (g) +subscenario="subScen" Step::getImage t2 Figure 8.2: Step patterns On the other hand, the ResourceManager vertices follow the pattern in Figure 8.3(d). Transition t1 takes its priority from the Priority attribute that represents the execution priority of the component in the host. Labels (DB acq,DB rel) are useful for the composition with the passive resource (Figure 8.3(d)). Figure 8.3(e) composes the subnet in (c) and the subnets in (d) to obtain the final subnet that represents the CSM in part (a). 8.3.3 PathConnections translation As explained in section 8.2, the path connectors are the means used by the CSM to represent the control flow of the system. Therefore they are meant to explicitly link the steps of the system and their acquisition and release. A path connector can be the source of several VertexOperations and also the target of several of them. The Sequence pathConnection is graphically represented in the CSM by an arrow connecting two VertexOperations. Figure 8.4(a) depicts its representation in the CSM and also its translation into a GSPN subnet. The subnet is made of a place and a transition labeled 8.3. CSM meta-classes translation 123 Component DB ResAcq Priority=2 DBCPU p1|ResAcq priority=2 t1|DB_acq t2|ResAcq p2 p1|ResRel t1|DB_rel t2|ResRel p2 t2|DB_acq t1|DB_rel p1|DB t2|DBCPU_acq t1|DBCPU_rel p1|DBCPU p7|DB Priority=2 t1|DB_acq t4|DB_rel p2 p5 ResourceUnits=1 ResRel Resource Acquire Resource Release p1|ResAcq p4|ResRel Pasive Resource Component Processing Resource DBCPU (a) (c)(b) ResourceUnits=1 Multiplicity=1 Multiplicity=1 t2|ResAcq t5|ResRel (d) Active Resource CSM representation GSPN representation (e) Pasive Resource Figure 8.3: GeneralResource and ResourceManager patterns with the name of the source and target steps. These labels will be useful to merge this subnet with those coming from the steps as proposed in section 8.3.1. A Fork connector represents the beginning of the parallel execution of different branches in the system that can be eventually connected by a Join. The CSM representation and the translation of these two connectors are given in Figure 8.4(b,c). As in the case of the Sequence, the labels represent the name of the Steps to which eventually these subnets will be merged. The Branch and the Merge are connectors to represent the start and the end, respectively, of the probabilistic choice of execution in the system. Figure 8.4(e) depicts the translation of the Branch, that is made of a transition and a place labeled with the names of the predecessor and successor Steps. To ease the understanding, we have depicted a translation and composition of the Branch and its precedent and successor Steps (here, Step 2and Step 3 124 8. Model To Model Transformations: From CSM To GSPN are translated as proposed in Figure 8.2(c)). We have also depicted the translation of these Steps following the patterns described in Section 8.3.1. Finally, in Figure 8.4(d) we can see that the Merge proposes a subnet to connect the alternative execution flows. (a) BRANCH Step_2 Step_1 Step_3 π = 0.6 π = 0.4 t3|Step_1 |host_rel p2|Step_1 p4|Step_2 t4 π = 0.6 p5 t6|Step_2 |host_rel p7|Step_3 t7 π = 0.4 p8 t9|Step_3 |host_rel p1|Step_2 |Step_3 t1|Step_1 BRANCH Step_3Step_2Step_1 p2|Step_1 p147 |Step_2 |Step_3 t4 π = 0.6 π = 0.4 t7 t6|Step_2 |host_rel t9|Step_3 |host_rel p6 p8 Step_1 Step_2 MERGE Step_3 t1|Step_1 t2|Step_2 p1|Step_3 MERGE (b) FORK Step_2 Step_1 Step_3 p1 |Step_2 t1|Step_1 FORK p2 |Step_3 (c) p1 t1|Step_1 JOIN p2 t2|Step_2 t3 p3|Step_3 Step_1 Step_2 JOIN Step_3 (d) Step_1 Step_2 SEQUENCE SEQUENCE p1|Step_2 t1|Step_1 (e) p3 t5|host_acq p6 p9 t8|host_acq t2|host_acq t2|host_acq p3 t3|Step_1 |host_rel p5 p8 t5|host_acq t8|host_acq Figure 8.4: PathConnections patterns Start and End connectors translation The Start and End connectors are used in the CSM to mark where the model begins and the different ways to finish it. A Start connector is translated into two places and a transition as given in Figure 8.5(a). The label of place p2will be useful to merge the subnet of the Start with the subnet of its successor step, in this case Step 1. A scenario may own more than one End. When the End is associated with an asynchronous Message, we call it “asynchronous End”, otherwise we call it “synchronous End”. 8.3. CSM meta-classes translation 125 Concerning “synchronous Ends”, they can play two roles: either they belong to a subscenario or to a scenario with its own ClosedWorkload. The scenario in Figure 8.13(b) owns both: a “synchronous” End, see left hand side, and an “asynchronous” one. Currently, the CSM allows at most one “synchronous End” per scenario, the rest have to be “asynchronous” [PW07]. Both kinds of “synchronous End” are translated the same way, as in Figure 8.5(b), and the resulting subnet is composed with the subnet of the predecessor step. Moreover, this subnet is also composed in the first case with the subnet of the Step it refines, and in the latter case, the subnet will be composed with the subnet of the ClosedWorkload. The translation of the “asynchronous End” is proposed in Figure 8.5(c), this subnet will be composed with the subnet of the predecessor step. 8.3.4 Workload translation A Start connector may associate a workload, which can be closed or open. A ClosedWorkload element of the CSM is translated into a place and a transition, as given in Figure 8.6(a). The attribute Population indicates the maximum number of concurrent executions in the scenario. The Population is represented, in the subnet, by the number of tokens in p1. The subnet of the ClosedWorkload has to be merged with the subnet of the Start and with the subnet of the “synchronous End”. The resulting PN, see Figure 8.6(a), is a cyclic net. This kind of nets is useful to perform system analysis in steady state. On the other hand, when a Start connector is attached to an OpenWorkload, it models the distribution function for the scenario arrival events. Among potential arrival patterns, we have implemented in the tool some commonly used: Poisson, periodic and a class of phase type. Poisson distributions are modeled using an exponential transition with parameter λ, where λcharacterizes the arrival rate. Figure 8.6(b) depicts the translation of the OpenWorkload and the resulting Petri net when it is merged with the Start connector. Workloads whose arrivals are periodic (i.e. the arrival of events follows a constant pattern) are translated as depicted in Figure8.6(c). The difference between this periodic patterns and previous Poisson distribution is that it is used a deterministic transition instead of an exponential one. In Figure8.6(c), trasition t2 is deterministic and has constant firing time. Therefore, this net is not a GSPN but a Deterministic Stochastic Petri Net (DSPN) [AMC87]. However, we can analyze DSPNs using analysis techniques based on those ones for GSPN as long as the DSPN has at most one deterministic transition enabled [Bal98]. Phase type distributions consist of a set of phases with a given execution time and an absorbing state with a probability for each phase to enter in it. Our tool, instead of implementing the general phase-type distribution, implements a subtype of it, the generalized Coxian. This distribution can be approximated to any probability distribution function changing the number of phases, the mean time in each one and the probability of moving among them. On the other hand, an increment in the number of phases of a Coxian distribution means an exponential increment in the number of possible states; so, this could lead to a large Petri net with a state space explosion problem preventing its performance analysis. Figure 8.6(d) shows the solution we implemented, which is an extension of that in chapter 7 of [AMBC+95]. The 126 8. Model To Model Transformations: From CSM To GSPN parameter of this function must be made of 4 vectors, each one with as many components as phases: one with the starting probabilities for each phase; one with the moving probabilities to the previous phase; one with the moving probabilities to the next phase and the last with the probabilities of each phase to move to the absorbing state. The sum of ith component of the 2nd, 3rd and 4th vector must be 1. End1 End2 Start Step_1 Step_N Step_M p1|start_Sce t1|start_Sce Start p2|Step_1 p1|End1 t1|end_Sce End1 t2|Step_N p1|End2 t1 End2 t2|Step_M Message Async (a) (b) (c) Figure 8.5: Start and End patterns 8.4 Tool development The CSM to GSPN model transformation patterns proposed in previous section have been implemented in a software tool. This section describes the main points of its development. The tool can be downloaded from [CSM], where a guide about how to use it is also available. 8.4.1 Tool design Concerning the approach adopted to develop the tool, we studied several choices and their trade-offs. Among them, an interesting one proposed to create an XSLT stylesheet [XSL] to perform an XSL transformation of the CSM into an XML [XML] based PN standard format [BCvH+03]. We ruled out this choice since we were not completely convinced about the current applicability of the PN standard, concretely regarding the stochastic extension and the GSPNs. Finally, we decided to implement, using Java [JAVa], the patterns in section 8.3. This implied to transform the XML representation of the CSM into an application program interface (API) representing GSPNs. The API is the set of java classes in Figure 8.7(a). This API proposes the abstract class PetriNet as an aggregation of the classes Transition, Arc and Place, abstract as well. The PetriNet class is specialized into concrete classes that will represent the actual PN, e.g., the GSPNPetriNet class or the DSPNPetriNet class. The GSPNPetriNet class aggregates the places, arcs and transitions of the PNs actually created by the tool. The attributes of these classes represent all the features of our translation (e.g., probability in the transitions or tokens in the places) and graphical information as well. Table 8.2 lists some of these attributes. GraphicElement has the attributes that define the position in a canvas of the Petri net elements. In the Arc class, the attribute toTransition specifies whether the arc targets a transition or a place. In the Place class, initialTokens means 8.4. Tool development 133 to its predecessor and successor steps, however they still need to be linked to the subnets of the resources they manage, as in Figure 8.3(e). The second part of the algorithm carries out the composition of the End connector subnets with the partial mlgspn. If we composed the Ends and the partial mlgspn in the first part of the algorithm, then partial mlgspn would be wrong, concretely in the case of sub-scenarios which refine more than one Step. Figure 8.9(a) depicts the translation and “too-early” composition of a sub-scenario that is called by two different Steps. We observe that the result is that the sub-scenario cannot return the execution flow to the requester scenario. However, Figure 8.9(b) depicts the translation obtained by delaying the composition of the Ends, which is the expected one for the system. In fact, this was the only case in which we could not find a solution to meet E2, so we had to delay the composition. After the execution of this second part, partial mlgspn represents everything in the system except the resources. This is so because we are translating scenario by scenario. Not being part of a concrete scenario, the resources belong to the root CSM -as shown in the metamodel in Figure 8.1-, their position in the DOM tree is illustrated in Figure 8.8. Therefore, the third part of the algorithm translates passive resources and compose them with the partial mlgspn. The last part of the algorithm (lines 21..24) is dedicated to the translation and composition of the active resources. But prior to this task, it is called the function add-host-characteristicsto-steps (line 20). Considering that each Step executes on a processing resource, this function is responsible for discovering this target resource following the “scope rules” given in [PW07] and substitutes the generic labels host acq and host rel (recall Figure 8.2) by the actual name of the host. Thanks to this, the algorithm correctly merges each active resource with the net in this last part. At the end of the algorithm, partial mlgspn already represents the behavior of the whole CSM. Although the tool checks the input CSM for some inconsistencies, it is worth noting that we ideally assume a “well-formed” CSM, otherwise the tool could produce an incorrect GSPN. For example, when entering a Fork, the nunits of the previously acquired passive resource may be used by at most nthreads of the Fork and they will be eventually released. Figure 8.10(a) depicts an erroneous CSM since 1unit is acquired but 3released. Figure 8.10(b) depicts the erroneous Petri net that the tool will produce. 8.4.3 Remarks on the analysis of the resulting GSPN The subnets obtained in Section 8.3 are GSPNs free of choices (formally speaking, they are state-machine or marked-graph PNs). However, when they are composed by Algorithm 8.1, the free-choice property is no longer kept. Therefore, the modeling power of the final GSPN is not restricted to free-choice systems, it can also model resource sharing and competition (formally speaking, the type of the GSPN produced by Algorithm 8.1 is a simple-net). This can be observed in Figure 8.15 where transitions t92|BufferManager acq and t59|BufferManager acq work at the same time as synchronization and choice regarding place P78|BufferManager. Regarding boundedness, the final GSPN will be unbounded when there exist at least one open workload. For bounded GSPNs it can be applied classical exact solution techniques based on analyzing the underlying continuous time Markov chain (CTMC). For unbounded 134 8. Model To Model Transformations: From CSM To GSPN End1 Start Step_1 Step_N Step_M Step_2 Step::subscenario() Step_3 Step_4 Step::subscenario() Scenario_1 Scenario_2 Subscenario repCount = 10 repCount = 20 t3 π = 10/11 t2 |subscenario π = 1/11 p2 t1|Step_1 p1|Step_1 p9|Start t9|Start t10|Step_N p10|Step_N t11|Step_M p11|Step_M p12|End1 t12|sce_End1 t7 π = 20/21 t6|subscenario π = 1/21 p7 t5|Step_3 p5|Step_3 t4|Step_2 p4|Step_2 t8|Step_1 p8|Step_1 Scenario_1 Subscenario Scenario_2 t3 π = 10/11 t2 |subscenario π = 1/11 p3 t1|Step_1 p1|Step_1 p9|Start t11|Start t12|Step_N p10|Step_N t13|Step_M p11|Step_M p12|sce_End1 t9|sce_End1 t8 π = 20/21 t7|subscenario π = 1/21 p7 t6|Step_3 p5|Step_3 t5|Step_2 p4|Step_2 t10|Step_4 p8|Step_4 Scenario_1 Subscenario Scenario_2 t4|sce_End1 (a) (b) p3 p6 p2 p6 Figure 8.9: Different End compositions 8.5. Example of system analysis 135 GSPNs, the state space is not finite and consequently its underlying CTMC neither. In this case, depending on the structure of the GSPN, matrix geometric techniques[Hav95] or performance bounds[CS93] can be successfully applied for performance analysis. In cases where the GSPN cannot be analyzed using the previous techniques, simulation may be a good choice. For a comprehensive boundedness characterization of the GSPN produced by the tool, we can say that the net will be bounded if and only if one of the following situations arise: 1. all the workloads are closed and there is no Fork with asynchronous paths. 2. all the workloads are closed and all the elements in the asynchronous paths of the Forks (i.e., the paths that finish in asynchronous Ends) are in the scope of some PassiveResource with multiplicity less than infinite. Formally speaking, if any of the previous situations happens, all the places will be covered by a P-invariant, and then the Petri net will be bounded. (a) (b) Passive Resource Buffer t1|Buffer_acq t3|Buffer_rel p1|Buffer t1|Buffer_relt2|Buffer_rel Step_s1 Resource ResRel Units=1 ResRel ResourceUnits=1 Fork ResAcq ResourceUnits=1 Units=1Resource ResRel Figure 8.10: Erroneous modeling and translation of a Fork 8.5 Example of system analysis This section applies the proposed translation to the models of a system with two scenarios. The system is a secure building and has been taken from [XWP03]. The first scenario represents the acquisition and storing of the building video images (A/S-V), Figures 8.11 and 8.13 depict its models: sequence diagram (SD) and the CSM, respectively. The second scenario represents the access control (AC) of the secure building doors, Figure 8.12 depicts its SD, while the CSM can be found in [PW07]. [XWP03] provides an LQN model of this system, 136 8. Model To Model Transformations: From CSM To GSPN GetImage <<Resource>> VideoController BufferManager StoreProc Database {PAcapacity=10} procOneImage {rep=(value=$N)} getBuffer() cycleInit <<GaScenario>> <<GaAcqStep>>{acqRes=Buffer, resUnits=1} allocBuf() extOpCount=(value=$P)} <<GRMpass>> {PAname=Buffer, PAunits=1} freeBuf() <<GRMrelease>>{PAname=Buffer,PAunits=1} releaseBuf() passImage(i,b) storeImage(i,b) {hostDemand=(value=1.1,unit=ms, statQ=mean,source=assm)} {hostDemand=(value=$B*0.9,unit=ms, {hostDemand=(value=$P*1.5,unit=ms, getImage(i,b) {hostDemand=(value=0.9,unit=ms, statQ=mean,source=assm)} (1,’s’)), {hostDemand=(value=2,unit=ms, statQ=mean,source=assm)} store(i,b) writeImg(i,b) statQ=mean,source=assm), externalOpCount=(value=$B)} <<Resource>> <<Resource>> <<Resource>> <<Resource>> statQ=mean,source=assm)} {hostDemand=(value=0.5,unit=ms, statQ=mean,source=assm)} <<GaStep>> <<GaStep>> <<GaWorkloadEvent>> {pattern=(closed=(population=1, <<GaStep>> extDelay=(source=est,statQ=percent, statQ=mean,source=assm), <<GaStep>> <<GaStep>> {hostDemand=(value=0.5,unit=ms, statQ=mean,source=assm)} value=$Cycle,unit=,precision=95)))} <<GaStep>> {hostDemand=(value=1.5,unit=ms, <<GaStep>> <<GaStep>> {hostDemand=(value=0.2,unit=ms, statQ=mean,source=assm)} statQ=mean,source=assm)} <<GaStep>> <<GaStep>> <<GaStep>> {hostDemand=(value=1.8,unit=ms, <<GaStep>> Figure 8.11: Sequence diagram for A-S/V scenario, taken from [XWP03] moreover the LQN is profiled through several experiments which offer interesting performance results. We will compare these results with ours. 8.5.1 Qualitative properties analysis From the CSM of the A/S-V scenario we obtained the corresponding GSPN automatically, using our tool. We firstly perform a qualitative analysis of the GSPN, which revealed a deadlock in the procOneImage sub-scenario, Figure 8.13(b). The deadlock was then studied in the UML SD and projected into the CSM as follows. The Fork splits the sub-scenario into two execution threads: the long part (sub-scenario asynchronous part) and the short one (synchronous part). The synchronous part cycles to the start of the sub-scenario and acquires the BufferManager again but has to wait for the Buffer, which could be still being used by the asynchronous one. In turn, the asynchronous part tries to acquire the BufferManager, then leading to a deadlock caused by a circular wait. To evade the problem, the acquisition of resources was swapped in the CSM, see Fig- 8.5. Example of system analysis 137 <<GaStep>> {hostDemand=(value=0.2,unit=ms,statQ=mean,source=assm); prob=(value=0.2,source=assm)} <<GaStep>> {prob=(value=0,source=assm)} <<GaScenario>> {hostDemand=(value=1.8,unit=ms,statQ=mean,source=assm)} prob=(value=1,source=assm)} {hostDemand=(value=500,unit=ms,statQ=mean,source=assm); <<Resource>> <<Resource>> <<Resource>> <<Resource>> <<Resource>> DoorLock Alarm AcessController Database Disk {extOpCount=(value=1)} <<GaStep>> ReadCard admit(cardInfo) getRights() O O readRights() [not_in_cache] readData() prob=(value=0.4,source=assm)} checkRights() [OK]openDoor() [not OK]alarm() writeEvent() [need to log?] logEvent() writeRec() <<Resource>> CardReader <<GaStep>> <<GaStep>> <<GaStep>> {hostDemand=(value=0.3,unit=ms,statQ=mean,source=assm)} <<GaStep>> {hostDemand=(value=3,unit=ms,statQ=mean,source=assm)} <<GaStep>> {hostDemand=(value=1.8,unit=ms,statQ=mean,source=assm)} {hostDemand=(value=1.8,unit=ms,statQ=mean,source=assm)} {hostDemand=(value=1.5,unit=ms,statQ=mean,source=assm); <<GaStep>> <<GaStep>> {hostDemand=(value=1.8,unit=ms, statQ=mean,source=assm)} (value=$UserR,unit=s,statQ=percent,precision=95,source=est)} {pattern=poisson(value=0.5,unit=s)} <<GaWorkloadEvent>> <<GaStep>> {respT=(value=1,unit=s,statQ=percent,precision=95,source=req), Figure 8.12: Sequence diagram for AC scenario, taken from [XWP03] ure 8.14. The GSPN was again generated automatically, from the new CSM, see Figure8.151. The new analysis showed that the GSPN was deadlock free. In the LQN paradigm, the one applied in [XWP03], when a resource is acquired, its layer cannot be traversed again until the execution flow returns back to a previous layer. Then, the layer of the BufferManager cannot be traversed back (and the resource released) before its next layer is completed. To avoid this situation, in [XWP03], the BufferManager is duplicated, which solves the problem of the not nested operations with resources. But in our opinion, it creates a new one, the problem is that if the scenario could reach a deadlock then it would not be realized with the LQN. As a conclusion, the use of the LQN paradigm for performance analysis is motivated when nested services prevail in the system. 8.5.2 Quantitative properties analysis Once the GSPN has been shown to own good qualitative properties (deadlock free and liveness), we carry out similar experiments to the ones presented in [XWP03]. Tables 8.3 to 8.6 offer results about: cycle time in seconds for polling all the cameras in the A/S-V scenario; response time (RT) in seconds for a human user accessing the door in the AC scenario; and the normalized utilization of the resources shared by both scenarios. The normalized utilization means the ratio of the mean number of busy resources out of the total number of the corresponding resources. The results in the Tables have been obtained computing, in the GSPN in Figure 8.15, the throughputs of some transitions and the mean number of tokens in 1To avoid cluttering, the GSPN in Fig.8.15 appears without the arcs between ProcessingResources and Steps. 138 8. Model To Model Transformations: From CSM To GSPN (b) (a) ResRel Block ExtOp write Applic CPU Processing Resource Component StoreProc Manager Component Buffer releaseBuf ResRel ResRel ResRel Message Async ResAcq freeBuf ResAcq storeImage store ResAcq Component Database Processing Resource DB CPU Passive Resource Buffer ResRel End ResAcq ResAcq ResAcq ResRel getImage passImage allocBuf FORK ResAcq cycleInit procOneImage repetitionCount=$N ResRel Controller Component Video Workload closed population=1 End getBuffer Start procOneImage Component GetImage Start End writeImg Figure 8.13: CSMs: (a) A-S/V scenario and (b) procOneImage sub-scenario. Taken from [PW07] 8.5. Example of system analysis 139 ResAcq ResAcq ResAcq allocBuf Component GetImage Manager Component Buffer Passive Resource Buffer Start getBuffer Workload closed population=1 Figure 8.14: The A/S-V scenario without deadlock some places: •The Cycle time is computed as the inverse of the throughput of transition t END. •Using Little’s law, the response time (RT) of AC scenario is equal to Mean number of tokens in P InExe T hroughput(T Arrival) •The Normalized resource utilization of X, where X∈ {GetImage,Buffer,StProc,AppCPU}, is computed as Number of X resources−Mean number of tokens in X Number of X resources Table 8.3 presents the results when there exists a unique instance of each resource. Experiments considered 10, 20, 30 and 40 cameras in the system. GetImage and Buffer components show to be the critical resources, they are busy almost all the time. The other resources are not affected by the number of cameras. The A/S-V cycle time shows an increment proportional to the number of cameras, while the RT is not affected. The purpose of the next studies is to decrease the A/S-V cycle time for 40 cameras without increasing the AC response time. Table 8.4 gives the results when the number of Buffers is increased. The A/S-V cycle time decreases only when the number of Buffers changes from 1 to 2, this is because the “synchronous and asynchronous parts” in the A/S-V can now work concurrently. However, new increments in the number of Buffers do not increment the system concurrency, then the A/S-V cycle time is not decreased. The utilization of the Buffer, which is always saturated, confirmed this. However this resource is not the bottleneck since its increments do not decrease the A/S-V cycle time. So, the bottleneck has to be either the StoreProc or GetImage components, which are fully saturated too. Actually, the bottleneck is the StoreProc because the GetImage only works in the synchronous part and can never exist concurrent executions of the synchronous part. This conclusion can be reached when simulating the GSPN, then counting the mean number of tokens in place P69 in Figure 8.15, that is 0. This bottleneck in StoreProc forces the execution of the asynchronous part to be sequential. Our next study (Table 8.5) gives the results when there are 40 cameras, 4 Buffers and the number of StoreProc is increased. When a new StoreProc is added, then the asynchronous 140 8. Model To Model Transformations: From CSM To GSPN P108 Video Controller t77|Endrep AppCPU_acq t75|CicleInit P64 ACQUIRE/STORE-VIDEO SCENARIO t78|rep_proc OneImage wait P79|Buffer P78|BufferManager P72|GetImage P88|StoreProc T81|procOneImage P69 t62|Buffer_acq t59|BufferManager_acq T83|allocBuf t64|BufferManager_rel T85|passImage T82|getBuffer T84|getImage t57|GetImage_acq t76|Store Proc_acq T86|StoreImageT87|Store t72|Database_acqT88|writeImg P16|Database 10 t69|Database_rel T89|freeBuf T90|releaseBuf t92| Buffer Manager_acq t96|BufferManager_rel t96|Buffer_relt76|Store Proc_rel P8|AccessController P108 P11|CardReader t12|Card Reader_acq T5|ReadCard t14|AC_acq T6|admit T7|getRights T8|readRights t24|dummy t25|disk_acq T9|readData t25|disk_rel t31|Database_rel T10|chekRights t37|DoorLock_acq P39|DoorLock T41|openDoor T58|logEventT55|write_Event T59|write_rec ACCESS CONTROL SCENARIO PROC ONE IMAGE SUBSCENARIO t72|Database_acq P10|AppCPU P17|DBCPU t51|disk_rel t52|Database_rel t53|AC_relt54 t47|Database_acqt50|disk_acq t53|AC_rel P25|Disk t_END T_Arrival P_InExe T104|writeBlock Figure 8.15: GSPN for AC and A/S-V scenarios 8.5. Example of system analysis 141 Average Normalized (1) time resource utilization Cycle RT GetImage Buffer StProc. AppCPU 10 0.328 0.187 0.992 0.9992 0.590 0.569 20 0.656 0.186 0.998 0.9996 0.590 0.569 30 0.985 0.182 0.997 0.9997 0.590 0.569 40 1.316 0.183 0.998 0.9998 0.592 0.570 (1) Number of cameras. Table 8.3: GSPN results part will allow concurrent executions, then decreasing the A/S-V cycle time. Before the replication of the StoreProc, the Buffer was almost fully saturated, because the synchronous part had to wait for an empty Buffer. After the replication, the Buffers are released faster and the synchronous part does not have to wait so long for a free Buffer. It is worth noting that now the utilization of the AppCPU has increased, what explains the slight increment in the AC user RT. When the StoreProc changes to 3 units, the A/S-V cycle time does not decrease anymore, so, the StoreProc is no longer the bottleneck. Therefore, to improve the system performance with the current design, the unique option already available is to replicate the AppCPU, which actually is saturated. Table 8.6 gives the results of these experiments. When an AppCPU is added, both RT and A/S-V cycle time decrease their estimated values. Average Normalized (2) time resource utilization Cycle RT GetImage Buffer StProc. AppCPU 11.316 0.183 0.998 0.9998 0.592 0.570 21.130 0.198 0.998 0.9940 0.998 0.675 31.117 0.188 0.998 0.996 0.999 0.672 41.100 0.186 0.998 0.997 1.0 0.673 71.110 0.190 0.998 0.998 1.0 0.673 10 1.111 0.178 0.998 0.998 1.0 0.673 (2) Number of Buffers. Table 8.4: GSPN results: number of Buffers 142 8. Model To Model Transformations: From CSM To GSPN Average Normalized (3) time resource utilization Cycle RT GetImage Buffer StProc. AppCPU 11.100 0.186 0.998 0.997 1.0 0.673 20.798 0.198 0.997 0.830 0.940 0.947 30.756 0.189 0.997 0.690 0.651 0.986 (3) Number of StoreProc. Table 8.5: GSPN results: number of StoreProc threads Average Normalized (4) time resource utilization Cycle RT GetImage Buffer StProc. AppCPU 10.798 0.198 0.997 0.830 0.940 0.947 20.640 0.171 0.997 0.620 0.665 0.589 30.645 0.173 0.997 0.615 0.652 0.393 (4) Number of AppCPU. Table 8.6: GSPN results: number of AppCPU 8.5.3 LQN and GSPN results comparison When comparing the results obtained here with those in [XWP03], we can see that they are very close, for example, if a resource is saturated in the LQN, then it is in the GSPN analysis too. Therefore, for this case study there is no loss of information in the CSM representation, nor in the CSM-GSPN translation. Then, it seems that the proposed translation and its automatic implementation may work as good as a performance analyzable model that has been directly conceived by a domain expert. Figure 8.16 shows graphically a comparison between our results and the ones in [XWP03]. Among the results discussed in the previous section, we have chosen a representative subset for comparison: the cycle time of A/S-V scenario, the utilization of the StoreProc and of the AppCPU. In each graph, we represent information in Table 8.3 and in Table 8.6. Table 8.3 is the base case of the study, while Table 8.6 is the most complex case –the one where more resources are replicated–. Of course we compare these two cases with their analogous in [XWP03]. For the base case, the x-axis represents tens of cameras. For the case in Table 8.6, the x-axis represents the number of AppCPUs used. In graph 8.16(a), for the base case our results are identical to those obtained in [XWP03] using LQNs, indeed you cannot distinguish these two lines in the graph. Also for the base case but in graphs (b) and (c) results are extremely close.