Antonio Filieri

Martina Maggio

Konstantinos Angelopoulos

Nicolás D'ippolito

Ilias Gerostathopoulos

Andreas Berndt Hempel

Henry Hoffmann

Pooyan Jamshidi

Evangelia Kalyvianaki

Cristian Klein

Filip Krikava

Sasa Misailovic

Alessandro Vittorio Papadopoulos

Suprio Ray

Amir M Sharifloo

Stepan Shevtsov

Mateusz Ujma

Thomas Vogel

Software Engineering Meets Control Theory

The software engineering community has proposed numerous approaches for making software self-adaptive. These approaches take inspiration from machine learning and control theory, constructing software that monitors and modifies its own behavior to meet goals. Control theory, in particular, has received considerable attention as it represents a general methodology for creating adaptive systems. Control-theoretical software implementations, however, tend to be ad hoc. While such solutions often work in practice, it is difficult to understand and reason about the desired properties and behavior of the resulting adaptive software and its controller.

This paper discusses a control design process for software systems which enables automatic analysis and synthesis of a controller that is guaranteed to have the desired properties and behavior. The paper documents the process and illustrates its use in an example that walks through all necessary steps for self-adaptive controller synthesis.

I. INTRODUCTION

Software's pervasiveness in every context of life places new challenges on Software Engineering. Highly dynamic environments, rapidly changing requirements, unpredictable and uncertain operating conditions demand new paradigms for software design. Runtime adaptation mechanisms are required to deploy robust software that operates correctly despite a lack of design-time knowledge.

In the last decade, the Software Engineering community developed a multitude of approaches for developing selfadaptive software systems [START_REF] Abdelzaher | Introduction to Control Theory And Its Application to Computing Systems[END_REF][START_REF] Brun | Engineering Self-Adaptive Systems through Feedback Loops[END_REF][START_REF] Cheng | Software Engineering for Self-Adaptive Systems[END_REF][START_REF] Filieri | Reliability-driven dynamic binding via feedback control[END_REF][START_REF] Garlan | Rainbow: architecture-based self-adaptation with reusable infrastructure[END_REF][START_REF] Leva | Controlbased operating system design[END_REF][START_REF] Maggio | Comparison of Decision Making Strategies for Self-Optimization in Autonomic Computing Systems[END_REF][START_REF] Patikirikorala | A Systematic Survey on the Design of Self-adaptive Software Systems Using Control Engineering Approaches[END_REF][START_REF] Weyns | Claims and Evidence for Architecture-based Self-adaptation: A Systematic Literature Review[END_REF]. While these approaches describe general techniques, their implementations focus on specific problems and do not extend to broadly implementable methodologies [START_REF] Filieri | Automated Design of Selfadaptive Software with Control-theoretical Formal Guarantees[END_REF]. Furthermore, many proposed adaptation mechanisms lack the theoretical grounding to ensure their dependability beyond the few specific cases for which they are implemented [START_REF] Hellerstein | Applying control theory in the real world: experience with building a controller for the .NET thread pool[END_REF][START_REF] Lu | Feedback Control Architecture and Design Methodology for Service Delay Guarantees in Web Servers[END_REF][START_REF] Sun | LPV Model and Its Application in Web Server Performance Control[END_REF][START_REF] Tanelli | LPV model identification for Power Management of Web service Systems[END_REF]. In the last century, Control Theory has established a broad family of mathematically grounded techniques for adaptation. Controllers provide formal guarantees about their effectiveness and behavior under precise assumptions on the operating conditions.

Although the similarities between industrial plant control and software adaptation are self-evident, most attempts to apply off-the-shelf control-theoretical results to software systems have achieved limited scope, mostly tailored to specific applications and lacking rigorous formal assessment of the applied control strategies. The two main difficulties in applying control theory to software systems are:(i) developing mathematical models of software behavior suitable for controller design, and (ii) a lack of Software Engineering methodologies for pursuing controllability as a first class concern [START_REF] Diao | Self-managing systems: a control theory foundation[END_REF][START_REF] Dorf | Modern control systems[END_REF][START_REF] Hoffmann | Self-aware computing in the Angstrom processor[END_REF][START_REF] Zhu | What does control theory bring to systems research?[END_REF].

A theoretically sound controller requires mathematical models of the software system's dynamics. Software engineers often lack the background needed to develop these models. Analytical abstractions of software established for quality assurance can help fill the gap between software models and dynamical models [START_REF] D'ippolito | Synthesis of Live Behaviour Models[END_REF][START_REF] Filieri | Self-adaptive software meets control theory: A preliminary approach supporting reliability requirements[END_REF][START_REF] Wang | A simple approximation for modeling nonstationary queues[END_REF], but they are not sufficient for full control synthesis. In addition, goal formalization and knob identification have to be taken into account to achieve software controllability [START_REF] Papadopoulos | A Dynamic Modelling Framework for Control-based Computing System Design[END_REF].

Several approaches have extended control-theoretical results into more general methodologies for designing adaptive software systems. Pioneering works in system engineering [START_REF] Abdelzaher | Introduction to Control Theory And Its Application to Computing Systems[END_REF][START_REF] Diao | A Control Theory Foundation for Self-managing Computing Systems[END_REF][START_REF] Hellerstein | Feedback Control of Computing Systems[END_REF] spotlighted how control theoretical results improve computing system design. These contributions have been especially influential for performance management and resource allocation; however, new trends in self-adaptive software introduce new software models and a variety of quantitative and functional requirements beyond the scope of those works. More recently, methodological approaches for performance control [START_REF] Arcelli | Control Theory for Model-based Performance-driven Software Adaptation[END_REF][START_REF] Parekh | Feedback Control Techniques for Performance Management of Computing Systems[END_REF] and the design of self-adaptive operating systems [START_REF] Leva | Controlbased operating system design[END_REF] have been proposed. Software Engineering and Autonomic Computing has also highlighted the centrality of feedback loops for adaptive systems [START_REF] Brun | Engineering Self-Adaptive Systems through Feedback Loops[END_REF][START_REF] Kephart | The vision of autonomic computing[END_REF].

Control theory has developed during the years for physical systems, where what to measure and what to control is very clear, as well as how to define physical models of the actors. For these systems, many of the problems have been solved and the resulting solutions have been mathematically grounded. However, the software engineering domain poses different challenges, with respect to the physical world. On one hand, quantities that are difficult to measure in the physical world could be extremely easy to measure instrumenting code. On the other hand, there is no basic physic that one could rely upon and it could be extremely complex to come up with equations that properly describe the running system. This paper casts the control-theoretical framework of time-based controllers into the problem of applying control theory to software systems and provides a comprehensive analysis of one of the paradigms in the control theoretical design for self-adaptive software systems, matching the various phases of software development with the relevant background and techniques from Control Theory. For space limitations we restrict this paper to time-based controllers. Other paradigms, e.g. event-based controllers [START_REF] Ippolito | Synthesis of live behaviour models for fallible domains[END_REF][START_REF] D'ippolito | Synthesis of Live Behaviour Models[END_REF], allow achieving similar or complementary results for specific control problems. The goal is to bootstrap the design of mathematically grounded controllers, sensors, and actuators for self-adaptive software systems, providing formally provable effectiveness, efficiency, and robustness.

II. ADAPTATION IN SOFTWARE AND CONTROL

ENGINEERING

The word "adaptation" means two different things to software and control engineers. For a software engineer, adaptive software reacts to changing environmental and contextual conditions by changing its behavior or structure. Adaptation, however, is only one of the software designer's concerns. For a control engineer, controlling a system is the only concern -adaptive control just adds another degree of flexibility, where the controller may change its own control policies as well. Even the simplest controller (e.g., one that maintains room temperature by turning a heater on and off) makes the system adaptive according to the definition understood by a software engineer. To avoid misunderstandings, this section discusses more precisely the meaning of adaptation in the two communities and subsequently analyzes how the two viewpoints can be reconciled.

From a software engineering perspective, a system is adaptive when it allows for modifying its structure or behavior at runtime; i.e. without interrupting its service. An adaptive system can be coupled with an adaptation manager to make it continuously satisfy its requirements. A requirement violation may occur during runtime due to changes in execution environment including user interaction, the behavior of third-party components, or because the requirements themselves change.

Coupling the system with its adaptation manager creates what is called a self-adaptive system.

Self-adaptive systems have been an aim of Software Engineering for about two decades. However, general frameworks have been proposed only since the late 90s, both in the Software Engineering community and on the new field of Autonomic Computing [START_REF] Huebscher | A Survey of Autonomic Computing -Degrees, Models, and Applications[END_REF][START_REF] Kephart | The vision of autonomic computing[END_REF][START_REF] Oreizy | An Architecture-Based Approach to Self-Adaptive Software[END_REF][START_REF] Salehie | Self-adaptive Software: Landscape and Research Challenges[END_REF]. While each framework is unique, all of them share a closed-loop structure where the software monitors requirements violations, plans counteractions, and enforces them.

To ground the concepts, we take as reference the most popular self-adaptive design framework: the Monitor-Analyze-Plan-Execute (MAPE) feedback loop (Figure 1) [START_REF] Kephart | The vision of autonomic computing[END_REF]. The adaptive system operates in a changing environment, affecting its ability to satisfy the requirements. The adaptation manager detects the changes, analyzes their impact, and, if needed, plans and executes actions in response to the changes. All phases can be supported by additional knowledge about the system; e.g., suitable models kept updated at runtime.

Adaptation Manager

Monitor

Analyze Plan Execute Knowledge

Adaptive System Environment Fig. 1: Adaptive system: the software engineering perspective.

Controller C Plant P ȳ(k) + e(k) u(k) y(k) - d(k)
Fig. 2: Adaptive system: the control perspective.

From the control engineering perspective, an adaptive system consists of a control loop (Figure 2 shows an example) [START_REF] Åström | Feedback Systems: An Introduction for Scientists and Engineers[END_REF][START_REF] Hellerstein | Feedback Control of Computing Systems[END_REF]. A closed loop system consists of a controller and a plant denoted as C and P , respectively. The time is assumed to be discretized and y(k) represents the value of the signal y at time instant k. The controller's input is the error e(k) between the goals ȳ(k) and the measured value of the outputs y(k) -where input and output are measurable quantities 1 . The controller's output u(k) is a vector of values for the configurable parameters of the plant, often called knobs or actuators. All inputs and outputs can be vectors, meaning that the measured output of the closed loop system can be, for example, a two-dimensional vector whose elements are reliability and response times. The number of goals ȳ(k) should be equal to the number of measured outputs, while the number of knobs for which the controller should compute a value can differ from the dimensionality of the output. When control is applied to software systems, the plant is usually identified with the adaptive software system under control, but it can also contain additional information about the execution environment and platform. A plant receives as input the knob configurations and produces as output some measures of quantities y(k) upon which the user sets the control goals. There are other entities that act on the behavior of the plant, other than the control variables u(k). For example, if y(k) is the execution speed of a loop in the software, the sudden start of the garbage collector can slow down the computation or a sudden lack of memory can stall instructions. Equivalently, if Turbo Boost is turned on by the hardware, computation might be accelerated. These quantities that act on the measured output but are not under the direct control of the controller, are called disturbances in control terms, and denoted by d(k) in Figure 2. It is not necessary to identify them at design time, but it is important to acknowledge their existence. One of the purposes of control theory is to provably minimize the effect of the disturbances on the controlled output variables.

The similarities between self-adaptive systems and controlled systems, i.e. the coupling of a plant with its controller, are self-evident, with ȳ(k) representing the system's goals and u(k) the adaptation actions that will achieve these goals.

Merging the design of self-adaptive systems with the theory of controlling industrial plants can enhance the software engineering process with a variety of mathematically grounded adaptation laws. This has an impact on every stage of software development process, from requirements analysis to design, implementation and testing. At the requirement analysis phase, the needs of stakeholders should be matched to control goals. At the design phase, controllers should become a first-class element together with the introduction of analytical views capturing the intended dynamic behavior of the software system. During implementation and quality assurance, the presence of controllers introduces new challenges for verification and testing. In the following, we sketch a development process that takes into account control theory as a powerful framework for developing self-adaptive systems.

III. CONTROL DESIGN PROCESS

This section discusses the design of a feedback control strategy for an existing software system. We provide details on the steps of the process that one should follow to develop a self-adaptive system with control-theoretical guarantees. The overall process is depicted in Figure 3.

The process starts by defining the system's goals, which are inputs of the control system. Values corresponding to the current state of the satisfaction of these goals need to be quantifiable and measurable so that they can serve as feedback to the controller. The goals are denoted by ȳ(k) (which in general depends on the time step k), while the measurements of their satisfaction is denoted as y(k) in Figure 2. The next step is identification of the software adaptation features (i.e. knobs or actuators) that can be changed at runtime, as denoted by u(k) in Figure 2. The next step is to define a mathematical model that describes how changes in knob settings affect the measurable feedback. This model is denoted by P in Figure 2.

Given the system model, the next step is to synthesize a controller (C in Figure 2) with the most appropriate method among the many different ones that control theory offers.

The next step is to analyze the closed loop system and to prove that it behaves as desired. Informally, the closed loop system should reach and stabilize at its goal(s), and be robust to external variations and changes. These properties should be also verified in the presence of disturbances (d(k) in Figure 2). If the desired properties are not exhibited, the process backtracks to one of the previous steps and a new iteration is started. Once the desired properties of the closed loop system are met, the controller should be implemented and tested, both in isolation and integrated with the system under control.

Running Example: To illustrate the end-to-end control design process we will focus on the self-adaptation of a specific software system: (real-time) video encoding.

A video encoder processes a stream of video frames. Each frame is analyzed and the encoder chooses some frames as the encoding basis (I frames) and some frames to be encoded with respect to their differences with previous frames (P frames) or with both backward and forward frames (B frames). The encoding of I frames is very quick, since the data have to be copied directly into the resulting chunk of video, while encoding of P and B frames requires more operations. There are different encoding algorithms (e.g., single pass, two passes, or three passes), and several parameters that can be tuned for each algorithm. For example, the resolution of the resulting frames can be tuned, along with the scene cut (a parameter that controls the insertion of I frames).

The video encoding example allows us to discuss different goals and different types of knobs. The encoding algorithm belongs to a non-ordered set of possible values. In contrast, the frame resolution belongs to a set of values ordered with respect to goal satisfaction. If the goal is accuracy, the higher the resolution, the more accurate the encoding. If the goal is frame latency, the lower the resolution, the lower the latency. The amount of computing capacity given to the application belongs to a continuous bounded set, between zero and the number of cores on the machine2 .

The video encoding example has already been studied in control literature [START_REF] Filieri | Automated Design of Selfadaptive Software with Control-theoretical Formal Guarantees[END_REF][START_REF] Hoffmann | CoAdapt: Predictable Behavior for Accuracy-Aware Applications Running on Power-Aware Systems[END_REF][START_REF] Maggio | Power optimization in embedded systems via feedback control of resource allocation[END_REF][START_REF] Muttreja | Automated Energy/Performance Macromodeling of Embedded Software[END_REF][START_REF] Shafique | enBudget: A Run-Time Adaptive Predictive Energy-Budgeting scheme for energy-aware Motion Estimation in H.264/MPEG-4 AVC video encoder[END_REF]. It presents some interesting challenges, like the tradeoff between encoding compression and quality, energy minimization, and the dependence on input data (the video stream can be almost static; e.g., a conference talk, where little effort has to be done to encode B and P frames, or very dynamic; e.g., a sporting event). In the following sections, this example demonstrates the steps required to design a control strategy for a software system.

A. Identify the goals

The first step is to define the quantifiable and measurable goals the controller is to achieve.

We distinguish between functional and non-functional goals [START_REF] Glinz | On Non-Functional Requirements[END_REF]. A functional goal concerns what functionalities the system exhibits, under a certain condition. A non-functional goal concerns how good the system has to perform, i.e. the quality it is expected to exhibit. A quality may target a specific functional requiremente.g., reliability of specific message passing -or may describe a global concern over the entire systeme.g., only authorized users can access the database. Performance, reliability, and energy consumption are typical non-functional requirements that can be quantitatively expressed. For example, one may specify a system's performance requirements by introducing response time and throughput metrics. However, not all non-functional requirements are easily quantifiable. Security and usability are instances of this category3 , although in special situations they may be measured.

Control strategies can be defined for the satisfaction of both functional and non-functional requirements. Though it is not a general rule, the former are usually managed by discrete-event controllers, capable, for example, of planning the composition of available components to introduce new functionality (e.g., [START_REF] Ippolito | Synthesis of live behaviour models for fallible domains[END_REF][START_REF] D'ippolito | Synthesis of Live Behaviour Models[END_REF]). The latter are often handled by means of equation-based controllers, tuning relevant knobs to change quantitative properties of the software system, like its timing properties or its energy consumption (e.g., [START_REF] Filieri | Automated Design of Selfadaptive Software with Control-theoretical Formal Guarantees[END_REF][START_REF] Hoffmann | CoAdapt: Predictable Behavior for Accuracy-Aware Applications Running on Power-Aware Systems[END_REF]).

(1) The simplest type of goal for an equation-based controller is a reference value to track. In this case, the control objective is to keep a measurable quantity (response time, energy consumption, occupied disk space) as close as possible to the given reference value, called a setpoint4 . For example, the frame rate of a video streamer should be kept constantly at a standard frame rate of 24, 25 or 30 frames per second, depending on the country and the broadcasting infrastructure.

(2) A second category of goals is a variation of the classic setpoint-based goal, where the goal resides in a specific range of interest; e.g., the average frame rate should be between 23 and 32 frames per second. Usually it is easy to transform these goals into equivalent setpoint-goals with confidence intervals.

Requirements elicitation plays an important role in defining the setpoints; it is in fact a systematic way to identify the critical requirements from the viewpoint of the stakeholders. Toward this end a new class of requirements, called Awareness Requirements (AwReqs) have been proposed. AwReqs constrain the success/failure of the system's critical requirements [START_REF] Souza | Awareness Requirements for Adaptive Systems[END_REF]. For example, for a web video streaming system a goal "Serve High Definition Video" could have as an AwReq "SuccessRate(80%)". This means that 80% of the time, high definition video should be delivered to the clients.

(3) A third broad category of goals concern the minimization (or maximization) of a measurable quantity of the system. For example, we may want to deliver our service with the lowest possible energy consumption. Depending on the specific quantity under control, certain optimization problems can be reduced to setpoint tracking. In particular, if the range of the measured property to optimize is convex and bounded, a setpoint tracker required to keep the measured property at its minimum possible value will drive the process as close as possible to the target, that is, toward the minimum possible value. Optimization problems, however, usually require more complex control strategies, especially when the optimization of one or more properties is subject to constraints on the values of others; e.g., minimize the response time while keeping the availability above a certain threshold 5 .

In our running example, a potential goal of this type is minimizing the video encoder's energy consumption. This goal can also be coupled with the timing properties of the software, which becomes an extra constraint. The precise formulation would be the minimization of the energy under the constraint that the frame rate is kept equal to a specific value. This formulation can generate conflicting goals. Speeding up the encoding process requires exploiting the hardware more and consuming in general more power. Reaching the timing goal can have a negative effect on energy consumption.

Special attention has to be paid when there are conflicting goals. Two simple types of conflict resolution strategies are prioritization and cost function definition. In the former, multiple goals are ranked according to their importance so that, whenever it is not be feasible to satisfy all of them at once, the controller will give precedence to the satisfaction of higher priority goals first 6 . Cost functions are another common means to specify the resolution of conflicting goals. In this case the utility function specifies all the suitable tradeoffs between conflicting goals as the Pareto front of an optimization problem. Optimal controllers can handle this type of specification guaranteeing an optimal resolution of conflicts.

A problem that is closely related to goal setting is the specification of graceful degradation strategies. Assuming a goal becomes temporarily infeasible, different reactions are possible. The simplest strategy may be to keep the system as close as possible to the target value. Setpoint tracking intrinsically provides this feature. However, the stability of the closed loop system for infeasible goals should be evaluated carefully. Another classic strategy for graceful degradation consists of disabling secondary functionality to free resources for achieving the primary goals, as done, e.g., in [START_REF] Klein | Brownout: Building More Robust Cloud Applications[END_REF] for cloud applications and in [START_REF] Angelopoulos | Dealing with Multiple Failures in Zanshin: A Control-theoretic Approach[END_REF] for a socio-technical system.

B. Identify the knobs

The second step is to find the knobs that change software behavior. In control theory, the knobs are generally determined by the fundamental dynamics of the physical system under control. For example, an inverted pendulum has a single knob: the torque applied at the pivot point. If the pendulum is on a cart, the position of the pivot point can also be changed by moving the cart. In both cases there is a single knob, either the torque, or the position of the cart.

In some cases, software systems exhibit the same property and there are clear knobs that one can use to change the behavior of the system. In the case of the video encoder there are many potential knobs: the amount of computing resources given to the encoding applications, the encoding algorithm, the sensitivity of the encoding algorithm to changes in the frame 7and many more. In contrast to physical systems, software systems are relatively easy to modify. As a consequence, there are cases in which knobs can be relatively easily added or removed. Both when using existing knobs and when devising new ones, the main issue is how to identify the best knobs to control the software system. In [START_REF] Souza | System Identification for Adaptive Software Systems: a Requirements Engineering Perspective[END_REF], an elicitation methodology is proposed, and the impact of each knob is evaluated with reference to the design goals.

Another important point when identifying the knobs is quantifying each knob's timescale. Some knobs, like powering up a new virtual machine, require time to bring about an effect. The control strategy should be aware of this time requirement and incorporate it into its model of the system's behavior.

In the video encoder case, the computing capacity given to the application can be considered a knob. In this case, the timescale of the visible changes is almost immediate and one expects the control action to have a measurable effect after the first second (when the average frame rate is updated).

C. Devise the model

The next step in the control design process is developing a model for the software system under control. In general, this model captures the relationship between the knobs identified in Section III-B and the goals identified in Section III-A, representing how a change in knob setting affects the goals.

In control theory, the model is analytical, so the interaction is formally described by mathematical relationships. This could mean that logical formulas are used (especially for discrete event control strategies) or that dynamical models are written (generally for continuous-or discrete-time-based controllers). Dynamical models are used to synthesize continuoustime or discrete-time-based strategies. A dynamical model can be either in state space form or expressed as an input-output relationship.

In the first case, one must choose the state variables that track the system's history and its evolution in time. Examples include the length of a queue, the percentage of frames already encoded, or the current encoding speed. Given the state variables' current values and the system's input values, one can formally determine the output variables' values [START_REF] Papadopoulos | A Dynamic Modelling Framework for Control-based Computing System Design[END_REF]. The choice of the state variables is not unique since an infinite number of equivalent representations can be found [START_REF] Åström | Feedback Systems: An Introduction for Scientists and Engineers[END_REF].

Once the state variables are identified, the relationship between the input and the state variables should be written, together with the relationship between the state and the output variables. For example, if the input variable of a queue is the number of incoming requests and the output variable is the average service time, the state variable is the number of enqueued requests. In principle, one could have many equations describing different inputs' effect on different state variables and the state variables' effect on the measurable outputs. These equations form the dynamical model used for the controller design. Depending on the equations' structure, there are different types of models: linear and nonlinear, switching, or parameter varying. Some examples follow (x(k) representing the state of the system at time k).

x(k + 1) = 3 • x(k) • k + u(k) (1)
x(k

+ 1) = -0.5 • x(k) + u(k) (2)
x(k

+ 1) = 3 • x(k) 2 + x(k) • u(k) (3)
x(k + 1) = -0.5 • x(k) + 3 (4)
To be more precise about the properties of the system, if the equations in the system do not have an explicit dependence on time, the system is time-invariant. If the equations directly depend on functions of time, the system is time-varying. Among the equations above, (1) is time-varying, while (2), ( 3) and ( 4) are time-invariant. When the equation is linear with respect to the state x and the input u, the system model is linear. If the function is nonlinear with respect to x and u, the corresponding model is nonlinear. (1), ( 3) and ( 4) are nonlinear, while (2) is linear. Notice that (4) is affine and does not correspond to a linear system. Affine systems can always be expressed as linear systems, using a change of variables.

Equations can also contain parameters that will vary over time. If the equations are linear, the corresponding systems can be analyzed as Linear Parameter Varying (LPV), for example as done in [START_REF] Sun | LPV Model and Its Application in Web Server Performance Control[END_REF].

In the second case, the system is expressed as a direct input-output relationship. Contrary to the state variables-based representation, this representation of the system is unique. State-of-the-art techniques in system identification often capture a system's input-output relationship directly from data, without using state variables. In the linear case, the inputoutput relationship can be expressed as a transfer function [START_REF] Åström | Feedback Systems: An Introduction for Scientists and Engineers[END_REF]. Transfer functions are very useful for control design, because they encode the input-output relationship with an algebraic relationship, that can be used to assess the system's satisfaction of desired properties. The same properties can be verified using state-space model, but that requires solving linear systems, which is harder than finding the roots of a polynomial (the standard way to assess the stability of a system specified with a transfer function).

In writing the model one should also consider potential disturbances acting on the system. In the video encoding example, there are inherently uncontrollable factors, such as operating system context switching and platform garbage collection.

Disturbances can be either modeled together with the system or their existence can be acknowledged. In the former case, a better control strategy can be designed; e.g., by coupling a feedback controller with a feedforward control strategy that measures the disturbance and cancels it. In the latter case, the feedback control strategy should reject the disturbances. For example, by increasing the number of cores given to a video encoder while a garbage collector is running, the controller can meet the desired frame rate without modeling the effect of the garbage collector or knowing when it starts and ends. The feedback mechanism would take care of that.

For the given video encoding example, we can use the resources assigned to the application as an actuator [START_REF] Hoffmann | A generalized software framework for accurate and efficient management of performance goals[END_REF][START_REF] Maggio | Power optimization in embedded systems via feedback control of resource allocation[END_REF]. We denote this value as speedup s(k). As the goal is the encoding rate y(k), we can express the relationship between these two quantities as

y(k) = s(k -1) w(k -1) + d(k -1) (5)
where w(•) is the possibly time varying application workload; i.e. the (nominal) time between two subsequent frame encodings, and d(•) is an exogenous disturbance accounting for any non-nominal behavior. If the workload parameter is considered constant w(•) = w, the model is linear. Otherwise, this is an instance of a Linear Parameter Varying (LPV) model. If w is a constant in (5), the transfer function of the plant, from s to y is

P (z) = Y (z) S(z) = 1 w • z (6)
where S(z) is the Z transform of the control signal (the speedup), and Y (z) the Z transform of the encoding rate.

The Z transform converts a dynamical model from the time domain (where time is represented with a sequence of k discrete instants) to the frequency domain (where z represents the frequency).

Although there is no direct correspondence of such controltheoretical models to software engineering models used for adaptation, some parallels can be drawn. In software engineering, a system at this phase is typically represented by its structure in an architectural model [START_REF] Garlan | Rainbow: architecture-based self-adaptation with reusable infrastructure[END_REF][START_REF] Kramer | Self-Managed Systems: an Architectural Challenge[END_REF]. Following a gray-box approach, only the details relevant for adaptation are modeled. For example, if we use the architectural model for performance analysis, we will typically annotate each component with its measured/predicted service time.

Architectural models are then either directly employed or transformed into analytical models and used in the adaptation logic of the system. The adaptation logic is typically captured in Event-Condition-Action rules, which model the connection between the state (captured in architectural models, deployment models, etc.) and the goals (captured in goal models, constraints, etc.). Such a connection can be drawn since different system configurations (architecture or parameter configuration) fulfill the goals to different degrees. The concrete adaptation is either determined at design time (though often in an ad-doc manner) or inferred at runtime based on knowledge about which configuration "best" fulfills the goals.

The connections between the state and the goals, however, are often not formalized in an analytical model.

Markov models are often used in the analysis phase of an adaptation loop. They are a class of state-based models describing systems that exhibit probabilistic behavior. There are a number of Markov models. We categorize them by the type of available control variables. The described models are for a discrete-time case, but for each model there exists a continuous-time counterpart.

In cases of fully deterministic systems, we can use discretetime Markov chains (DTMC). DTMCs describe the probability of moving between system states and the model itself does not include any controllable actions. There are several methods employing DTMCs in the context of controlling software [START_REF] Calinescu | Selfadaptive software needs quantitative verification at runtime[END_REF][START_REF] Epifani | Model evolution by run-time parameter adaptation[END_REF][START_REF] Filieri | A formal approach to adaptive software: continuous assurance of non-functional requirements[END_REF][START_REF] Filieri | Lightweight Adaptive Filtering for Efficient Learning and Updating of Probabilistic Models[END_REF][START_REF] Filieri | Self-adaptive software meets control theory: A preliminary approach supporting reliability requirements[END_REF]. A typical scenario includes verifying a DTMC model of a system against a property. If a violation is identified, a reconfiguration of the system is triggered. When some of the actions in the system are controllable, we can use Markov decision processes (MDPs). MDPs extend Markov chains by modeling controllable actions using non-determinism. The resolution of the non-determinism is then used as a controller of the system. Controller synthesis for MDPs is a well researched subject with a number of synthesis method for various types of properties [START_REF] Baier | Controller synthesis for probabilistic systems[END_REF][START_REF] Brázdil | Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives[END_REF][START_REF] Kwiatkowska | Automated Verification and Strategy Synthesis for Probabilistic Systems[END_REF][START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. Systems with multiple players with conflicting objectives where players exhibit probabilistic behavior can be formalized using stochastic games. Stochastic Games can be seen as an extension of MDPs where the control over states is divided between several players. Typically, we are interested in the resolution of the non-determinism that allows certain player to achieve his/her objective despite possibly hostile actions of other players. For stochastic games, controller synthesis has been a subject of recent interest [START_REF] Basset | Compositional Controller Synthesis Stochastic Games[END_REF][START_REF] Draeger | Permissive Controller Synthesis for Probabilistic Systems[END_REF] including development of a tool for generating controllers in practice [START_REF] Chen | PRISM-games: A Model Checker for Stochastic Multi-Player Games[END_REF].

D. Design the controller

Different techniques can be used to design a controller. These techniques differ in the amount of information required to set up the control strategy, in the design process itself, and in the guarantees they offer [START_REF] Boyd | Linear controller design: limits of performance via convex optimization[END_REF].

The technique requiring the least information is synthetic design, which combines pre-designed control blocks. It often relies on the experience of the control specialist who looks at data concerning the controlled system and decides which blocks are necessary. For example, given a noisy output signal, a filter block could reduce the noise. Synthetic design usually starts with a basic control block and adds more to the system as more experiments are performed. Although the information required to set up the control strategy is very low, the expertise necessary to effectively design and tune such systems is high and both controller design experience and domain-specific knowledge are required. Furthermore, the formal guarantees this technique offers are limited [START_REF] Boyd | Linear controller design: limits of performance via convex optimization[END_REF]. This is due to the empirical nature of the controller design, where trial and error is applied and elements are added and removed. The main obstacle to formal guarantees is the interaction between the added elements, which is hard to predict a priori.

The second technique is a variation of the first one. It is based on the selection of a controller structure and it is often called parameter optimization. The only difference is that the choice of the controller parameters is often based on optimization strategies or on analytical tuning methods [START_REF] Visioli | Practical PID Control[END_REF].

The last technique is often referred as analytical design, and it is based on the solution of an analytical problem. The information requirements greatly increase as an analytical model of the controlled entity is required. Based on an equation-based model, controller synthesis selects a suitable equation to link the output variables to the control variables. Depending on which analytical problem is used (the optimization of some quantities, the tracking of a setpoint, the rejection of disturbances), different guarantees are enforced with respect to the controlled system. In some cases, this process can be automatized and analytical control synthesis can be used with domain-specific knowledge but without prior control expertise [START_REF] Filieri | Automated Design of Selfadaptive Software with Control-theoretical Formal Guarantees[END_REF]. This generally imposes limitations on the models to be used and on the obtained guarantees. Also, not all the control problems can be formulated in such a way that the solution can be derived automatically.

In the example of video encoding, since we have the transfer function of the plant, we can use a common methodology, called loop shaping, that consists of selecting the closed loop system's transfer function and deriving the controller expression based on the selected closed loop function and the plant's transfer function (it is thus a case of analytical design). We have modeled the plant, obtaining the transfer function of Equation ( 6), also denoted with P (z). We define the transfer function of the controller as C(z) and we denote with G(z) the transfer function of the system after closing the loop (the transfer function that expresses the relationship between the desired value of the goals and the current real measurements). With the control design, we impose the closed loop transfer function G(z) to have the expression

G(z) = Y (z) Ȳ (z) = C(z) • P (z) 1 + C(z) • P (z) = 1 -p z -p (7)
where C(z)•P (z) 1+C(z)•P (z) is the generic expression of the loop of Figure 2, 1-p z-p is the particular expression that we want the loop to assume, p is a generic parameter and Ȳ (z) is the transfer function of the setpoint. The static gain of the closed loop transfer function (that is obtained by computing the function when z = 1) is 1, meaning that the value of the setpoint will be transferred to the output unchanged. Also, we choose the closed loop transfer function so that the parameter p is the root of the denominator. This parameter will be used later to prove properties on the closed loop system and enforce stability and robustness to disturbances.

Computing C(z) from Equation ( 7), substituting Equation (6) to P (z), one obtains

C(z) = w (1 -p) • z z -1 . ( 8
)
Moving from the transfer function domain back to the time domain, this corresponds to the following control law.

s(k) = s(k -1) + w • (1 -p) [ȳ(k) -y(k)] . (9)
Equation ( 9) requires us to know the value of w, or to estimate it with other techniques. For now, we assume we know the correct value of the parameter.

E. Formally evaluating the closed loop system

From a software engineer's perspective, a controller should provide the following properties [START_REF] Diao | A Control Theory Foundation for Self-managing Computing Systems[END_REF][START_REF] Filieri | Automated Design of Selfadaptive Software with Control-theoretical Formal Guarantees[END_REF][START_REF] Filieri | Self-adaptive software meets control theory: A preliminary approach supporting reliability requirements[END_REF]: Setpoint Tracking. The setpoint is a translation of the goals to be achieved. For example, the system can be considered responsive when its user-perceived latency is below one second. Here, the setpoint is the one second value for maximum user-perceived response time. In general, the self-adaptive system should achieve the specified setpoint, whenever this is possible. If the setpoint is changed during the software's lifetime, the controlled system should react to this change and achieve the new setpoint. Whenever the setpoint is not reachable the controller should make the measured value y(k) is as close as possible to the desired value ȳ(k).

Transient behavior. Control theory not only guarantees that the setpoint is reached but also how this happens. The system's behavior during the initialization phase or when an abrupt change happens is usually called the "transient of the response". For example, it is possible to enforce that the response of the system does not oscillate around the setpoint, but is always below (or above) it.

Robustness to inaccurate or delayed measurements. Oftentimes, in a real system, obtaining accurate and punctual measurements is very costly, for example because the system is split in several parts and information has to be aggregated to provide a reliable measurement of the system status. A controlled system's (in control terms a closed-loop system composed by a plant and its controller) ability to cope with inaccurate measurements or with late measurements is called robustness. The controller should behave correctly despite transient errors or delayed data.

Disturbance rejection. In control terms a disturbance is everything that affects the closed-loop system other than the controller's action. For example, when a virtual machine provider places a machine belonging to a different software application onto the same physical machine as the target software, the performance of the controlled software may change due to interference [START_REF] Govindan | Cuanta: Quantifying Effects of Shared On-chip Resource Interference for Consolidated Virtual Machines[END_REF]. Disturbances should be properly rejected by the control system, in the sense that the control variable should avoid any effect of this external interference on the goal. In the video encoding example, the controller should be able to distinguish between a drastic change of scene (like the switch between athletes and commentators in a sport event) and a temporary slow down due to the switch between speakers in a conference recording. In the virtual machine example, the controller should be able to distinguish between a transient migration that is slowing down the software for a limited period of time and a persistent co-location that requires action to be taken to guarantee the goal satisfaction.

These high level objectives have counterparts in control terminology and their satisfaction can be mapped into the "by design" satisfaction of the following properties [START_REF] Diao | A Control Theory Foundation for Self-managing Computing Systems[END_REF][START_REF] Stein | Respect the unstable[END_REF]:

Stability. An equilibrium is asymptotically stable when it the system tends to reach it and remains there, irregardless of the initial conditions. This means that the system output converges to a specific value as time tends to infinity. This equilibrium point should ideally be the specified setpoint value.

Absence of overshooting. An overshoot occurs when the system exceeds the setpoint before convergence. Controllers can be designed to avoid overshooting whenever necessary. This could also avoid unnecessary costs (for example when the control variable is a certain number of virtual machines to be fired up for a specific software application). Guaranteed settling time. Settling time refers to the time required for the system to reach the stable equilibrium. The settling time can be guaranteed to be lower than a specific value when the controller is designed.

Robustness. A robust control system converges to the setpoint despite the underlying model's imprecision. This is very important whenever disturbances have to be rejected and the system has to make decisions with inaccurate measurements.

These four properties can be analytically guaranteed, based on the mathematical definition of the control system and the software. A self-adaptive system designed with the aid of control theory should provide formal quantitative guarantees on its convergence, on the time to obtain the goal, and on its robustness in the face of errors and noise.

In the case of discrete-time control systems depicted in Figure 2, it is possible to analytically express the closed loop transfer function that relates the goal ȳ(k) as input and the measured value y(k) as output. This has the form of Equation [START_REF] Boyd | Linear controller design: limits of performance via convex optimization[END_REF] and, factoring the denominator, can be rewritten without loss of generality as

G(z) = f (z) i∈[1,m] (z -p i ) (10)
where f (z) is a generic function of z and the denominator is the product of m factors (zp i ). The values of p i are the poles of the closed loop system. The poles can be real or complex numbers. To guarantee stability for discretetime control systems, the poles p i should lay in the unit circle (the circle with radius 1 of the complex plane). If one restricts to the real number case, this means that to guarantee stability, the poles should lay in the open interval (-1, 1). For a more detailed explanation the reader can refer to [START_REF] Åström | Feedback Systems: An Introduction for Scientists and Engineers[END_REF]. Analogous analytical formulations are available for all the mentioned properties, hence it is possible to check if the original requirements are satisfied.

In the example of video encoding, the closed loop transfer function has the expression of Equation [START_REF] Boyd | Linear controller design: limits of performance via convex optimization[END_REF],

G(z) = 1 -p z -p ,
that has one pole in z = p. Depending on the choice of p, the system can be proven to be stable or unstable. If -1 < p < 1, the system is stable, therefore it reaches the setpoint. Moreover, if the value of p satisfies 0 ≤ p < 1 there are no oscillations in the transient response.

The settling time of the controlled system is also determined from Equation [START_REF] Boyd | Linear controller design: limits of performance via convex optimization[END_REF]. We can now convert the model from the frequency domain back to the time domain by appling the inverse Z transform. The inverse transform of the closed-loop transfer function G(z) gives

y(k) = ȳ • (1 -p k ) (11)
As k increases the system approaches ȳ, as confirmed by the stability and setpoint tracking properties. We define the settling time as the time it takes the system to achieve (100 -)% of the final value of ȳ, which means that the system's operating point is only a small distance from the desired goal. We refer to this region, which is within of the goal, as the confidence zone. Analyzing Equation [START_REF] Calinescu | Selfadaptive software needs quantitative verification at runtime[END_REF], the first value of k for which our output enters the confidence zone is

k = log 0.01 log |p| (12)
which means that after k control steps the signal reaches the confidence zone. That value depends on , which is often chosen to be 5%, defining the confidence zone as the interval in which the controlled variable has reached 95% of its final value. In that case k = log 0.05/log |p|, which depends only on p. Therefore, the position of the pole determines how fast the system will reach its equilibrium. Indeed, the pole's value p can trade responsiveness -how fast the controller reacts, measured as settling time -and robustness in the face of noise or unmodeled variance in system behavior. The controller acts based on its model, or estimation of the effect of its action on the system. Whenever the desired properties are not satisfied, one can step back in the design process and design a different controller, as discussed in Section III-D. In some other cases, the model can be refined or a more comprehensive model can be used, as discussed in Section III-C. The use of a more complex model can capture a part of the self-adaptive software system that can be necessary to provide formal guarantees on the time behavior of the system. Finally, in some cases, one can go back and add a different knob, as discussed in Section III-B, to have better control over the goals of the software system.

F. Implement and integrate the controller

The next step after the controller design is its implementation and integration with the system under control. Although this step appears to be quite straightforward, it has also been called "the hard part" [START_REF] Hellerstein | Engineering Autonomic Systems[END_REF].

One of the main problem is that the implementation team (software engineers) often works independently from the control team (control experts) [START_REF] Liu | Actor-oriented control system design: A responsible framework perspective[END_REF]. The transition from control algorithms, which are typically in form of formulas or simulation results, into software is a non-trivial process. It involves many ad-hoc decisions, not only in the controller implementation itself (e.g., types of state variables), but also in the implementation of the accompanying code that is responsible for the integration. This becomes particularly challenging in the case of remotely distributed systems.

Controller Implementation: Much of today's control code is not handcrafted, but automatically generated from block diagrams and equations by tools that control engineers use in their daily routine. Among others, these tools include MATLAB/Simulink8 , Modelica 9 , and SCADE 10 . Such a use of models as design blueprints differentiates model-based from model-driven development approaches. While both use models for design, communication, documentation, and analysis purposes, model-driven approaches also use them to automatically derive (parts of) the implementation via code generation.

Code generation is performed in both "classical" control (control of physical plants) and in control of software systems. As an example from classical control, MATLAB/Simulink can generate efficient Hardware Description Language (HDL), Programmable Logic Controller (PLC), or C/C++ code. In control of software systems, domain-specific languages (DSLs) have been proposed to model feedback loops. The resulting software models are used to generate code that can be traced back to the models [START_REF] Krikava | ACTRESS: Domain-Specific Modeling of Self-Adaptive Software Architectures[END_REF] or to directly execute the feedback loop via model interpretation [START_REF] Vogel | Model-Driven Engineering of Self-Adaptive Software with EUREMA[END_REF]. Another popular approach in software engineering is the use of frameworks (cf. [START_REF] Salehie | Self-adaptive Software: Landscape and Research Challenges[END_REF]) for control-theoretical controllers, such as [START_REF] Liu | Actor-oriented control system design: A responsible framework perspective[END_REF] that is based on Ptolemy 2 11 , or for rule-and utility-based controllers such as [START_REF] Garlan | Rainbow: architecture-based self-adaptation with reusable infrastructure[END_REF]. Finally, there are libraries for various programming languages that support implementing common controllers, such as for Python 12 .

Regardless of the specific implementation technology and the degree of automation in translating the control algorithm to runnable code, there are some recurring issues in every controller implementation. Namely:

Actuator saturation occurs when the controlled system is unable to follow the controller's output. This happens when a control knob is fully engaged. In classical control, actuator saturation is a direct result of a physical constraint (e.g., a valve can only open up to a certain point and not more); in software systems control, similar constraints can be observed as well (e.g., the number of servers used cannot exceed the number of available servers in the cluster).

Integrator windup is a direct consequence of the actuator saturation and occurs in controllers with integral terms (the I term in a PID controller). During actuator saturation, the integral control accumulates significant error, which causes a delay in error tracking when the system under control recovers to the point that the actuator is no longer saturated. Therefore, a conditional integrator (or integrator clamping) should be used to avoid the windup.

Integrator preloading is similar to windup and can occur (i) during system initialization, or (ii) when there is a significant change in the set point. In both cases, the integral term should be preloaded with a value to smooth the setpoint change.

Apart from dealing with the common problems presented above, the controller implementation has to be robust. Common mechanisms to achieve robustness are (i) determination and disregard of invalid input signals (e.g., out-of-bound values), (ii) preventing duplicate control actions, and (iii) graceful degradation in case design-time assumptions are invalidated (e.g., when the actual computation and communication jitter is larger than assumed by controller designers).

Controller Integration: After a controller has been implemented, it has to be integrated with the rest of the system. This includes wiring all responsible components together, ensuring that the measurements are consistently collected across all sources, and that adaptation actions are correctly coordinated.

Regarding the running example, in the simplest case, this involves (i) instrumenting the video encoding software with appropriate sensors (e.g., to observe the frame rate) and actuators (e.g., to adapt the encoding quality) [START_REF] Maggio | Power optimization in embedded systems via feedback control of resource allocation[END_REF], and (ii) providing a runtime with a protocol that connects these sensors and effectors with the controller.

When integrating a controller into a system, there are two basic approaches to follow, with respect to the separation of concerns between the controller and the system under control [START_REF] Salehie | Self-adaptive Software: Landscape and Research Challenges[END_REF]: (i) intertwine the control logic with the system under controlinternal control, and (ii) externalize the control logic into a "controller" component and use sensor and actuator probes to connect the controller and the system under control external control.

The external control provides a clear separation of concerns between the application and adaptation logic. Its advantages with respect to maintainability, substitutability, and reuse of the adaptation engine and associated processes makes it the preferred engineering choice [START_REF] Salehie | Self-adaptive Software: Landscape and Research Challenges[END_REF]. It also allows building adaptation on top of legacy systems where the source code might be unavailable. The main drawback of external control is the assumption that the target system can provide (or can be instrumented to provide) all the necessary endpoints for its observation and consequent modification. This assumption seems reasonable since many systems already provide some interfaces (e.g., tools, services, APIs) for their observation and adjustment [START_REF] Garlan | Rainbow: architecture-based self-adaptation with reusable infrastructure[END_REF], or could be instrumented to provide them (e.g., by using aspect-oriented approaches). There is also a potential performance penalty as a consequence of using external interface or running some extra components and connectors which cannot be tolerated in some resourceconstrained environments (e.g., in embedded devices where memory footprint and transmission delays matters).

The separation of concerns in the external approach also makes it possible to provide more systematic methods for control integration by leveraging model-driven engineering techniques and domain-specific modeling [START_REF] Krikava | ACTRESS: Domain-Specific Modeling of Self-Adaptive Software Architectures[END_REF][START_REF] Vogel | Model-Driven Engineering of Self-Adaptive Software with EUREMA[END_REF]. Essentially, these solutions raise the level of abstraction on which the feedback control is described and therefore make it amenable to automated analysis as well as complete integration code synthesis.

G. Test and validate the system

The next step involves the test and validation of the controller. This can be divided into two broad categories. first, one needs to test the controller itself and check that it does the correct thing. A part of this is already done with proving the properties of the closed loop system. This proof, however, does not test the controller implementation. Second, is the controller verification together with the system under control, to understand if the controller can deliver the promised properties. This should be true, in general, but there might have been model discrepancies that have been overlooked during the design process, therefore validation is needed despite the analytical guarantees given by control theory.

Verification and validation of the controller: Static analysis and verification techniques can be used to assess both the controller code's conformance to its intended behavior and the absence of numerical errors due to the specificity of different programming languages and execution architectures.

There is a growing area of verification theories and tools focusing on real analysis and differential equations. The most recent advancements include Satisfiability Modulo Theory (SMT), Ordinary Differential Equations (ODEs) and hybrid model checking. The former can be used to verify if a system described by means of a set of differential equations can reach certain desirable (or undesirable) states, within a set finite accuracy [START_REF] Gao | Satisfiability modulo ODEs[END_REF]. In terms of scalability, SMT approaches over ODEs have been proved to scale up to hundreds of differential equations. Hybrid model checking is instead focused on the verification of properties for hybrid systems [START_REF] Raskin | An Introduction to Hybrid Automata[END_REF], which can, in general, be defined as finite automata equipped with variables that evolve continuously over time according to dynamic laws. These formalisms are useful to match a system's different dynamic behaviors with its current configuration, and can be especially valuable to study and verify switching controllers and the co-existence of discrete-event and equation-based ones. Current hybrid model checkers are usually limited to linear differential equations [START_REF] Franzle | HySAT: An efficient proof engine for bounded model checking of hybrid systems[END_REF][START_REF] Henzinger | HyTech: A model checker for hybrid systems[END_REF].

Controller code usually relies on numerical routines. Using the primitives of general purpose programming languages to develop complex numerical procedures introduces unavoidable source of uncertainties, including the common issues related to finite numerical precision of their implementations. Some tools (e.g., jpf-numeric) use model checking techniques to identify possible sources of numerical problems for programs implemented with general-purpose languages (e.g., Java) and produce counter examples helping the developer with reproducing and fixing problems. Moreover, modern SMT tools can be used at compile time to verify the occurrence of numerical problems and automatically provide fixes guaranteeing the final results of the procedures to be correct up to a target precision [START_REF] Darulova | Sound Compilation of Reals[END_REF]. Ad-hoc languages for implementing numerical routines: apart from the code-generation functions and API provided by established mathematical programming environments, such as Matlab, Maple, or Mathematica, some extensions to general purpose programming languages provide constructs useful for specifying mathematical solutions that may support coding and compiler-level verification and optimization of controllers.

Verification and validation of the controlled software system: Once the controller itself is verified, it is necessary to verify the controller implementation together with the system under control. This can be done by means of extensive experiments but the process can be supported by different tools. Each tool comes with its own drawback and guarantees.

Rigorous analysis: one can use tools like the scenario theory [START_REF] Calafiore | Uncertain convex programs: randomized solutions and confidence levels[END_REF][START_REF] Campi | A Sampling-and-Discarding Approach to Chance-Constrained Optimization: Feasibility and Optimality[END_REF][START_REF] Campi | The scenario approach for systems and control design[END_REF][START_REF] Papadopoulos | Model reduction of switched affine systems: a method based on balanced truncation and randomized optimization[END_REF] to provide probabilistic guarantees on the behavior of the controlled system together with the control strategy. The performance evaluation can be formulated as a chance constrained optimization problem and an approximate solution can be obtained by means of scenario theory. If this approach is taken, the software system's performance can be guaranteed to be in specific bounds with a given probability. This, for example, allows for quantifying the probability that the proposed solution is fulfilling the Service Level Agreements in the case of failures or unexpected behaviors. This type of analysis requires performing an extreme number of experiments, varying many sources of randomness in the system, to cover potentially many cases with the randomized experiments. It is advisable to use this tool when one needs formal guarantees that the implementation meets specific requirements in all the possible conditions and when it is not too costly to experiment with the production-ready system.

Empirical study: other types of analysis are based on systematic testing. One common way to validate a controller implementation and its system under control is to show statistical evidence, for example, using cumulative distribution functions, as done in [START_REF] Klein | Brownout: Building More Robust Cloud Applications[END_REF][START_REF] Klein | Improving Cloud Service Resilience Using Brownout-Aware Load-Balancing[END_REF]. In this work, less experiment effort is required are than for the rigorous analysis mentioned previously. Based on the results of these experiments, one can compute the empirical probability distributions of the goals. If the most important test cases are covered with the experiments, an empirical guarantee of the system behavior is obtained. This type of guarantee, however, does not offer any bound or any formal characterization of the system's behavior. In fact, if the system experiences different conditions than those tested, it might expose an undiscovered bug and misbehave.

IV. CONCLUSIONS This paper discussed how control theory results can be integrated in the design of self-adaptive software. We have clearly defined the steps that are required to develop control strategies for a software system and used an example to clarify and discuss how each phase of the control loop design process can be cast in a practical application. We believe that this knowledge systematization is the first step towards introducing control strategies in the design of self-adaptive software systems that offer formal guarantees on their behavior.

The output signals of the plant are usually the values of measurable goals, while the input signals of the plant can be the configuration of the plant itself e.g., a vector composed of elements like the algorithm used to solve a specific problem, the amount of resource allocated to a running application, the length of a queue, and much more.

The set is continuous if we assume to use a scheduler such as SCHED DEADLINE, now in mainline linux kernel, that allows to distribute fractions of the CPUs[START_REF] Lelli | An efficient and scalable implementation of global EDF in Linux[END_REF].

An extended discussion on functional and non-functional requirements can be found in[START_REF] Glinz | On Non-Functional Requirements[END_REF].

Setpoint tracking is a very well studied problem in control theory[START_REF] Levine | The Control Systems Handbook, Second Edition: Control System Advanced Methods, Second Edition[END_REF].

In this case, optimal control, discussed in[START_REF] Zhou | Robust and optimal control[END_REF] is more appropriate.

Several control strategies support the achievement of prioritized goals, for example daisy chain control[START_REF] Levine | The Control Systems Handbook, Second Edition: Control System Advanced Methods, Second Edition[END_REF].

This parameter specifies the amount of change in the frame before a new I frame is produced and affects at least the encoding speed, accuracy, and energy consumption.

http://www.mathworks.fr/products/simulink/

https://www.modelica.org/

http://www.esterel-technologies.com/products/scade-suite/

http://ptolemy.eecs.berkeley.edu/ptolemyII/

http://sourceforge.net/projects/python-control/

Acknowledgements: This work was supported by: the Swedish Research Council (VR) with the projects "Cloud Control" and "Power and temperature control for large-scale computing infrastructures", the LCCC Linnaeus Center, the ELLIIT Excellence Center, the Datalyse project, the Irish Centre for Cloud Computing and Commerce (IC4), the European Union's Seventh Framework Programme FP7/2007-2013 under grant agreement 610802 "CloudWave", the ERC advanced grants 267856 "Lucretius: Foundations for Software Evolution" and 246967 "VERIWARE", and the Swiss National Science Foundation under project SCOPES-IZ74Z0 137352, ANPCYT PICT 2012-0724, ANPCYT PICT 2011-1774, AN-PCYT PICT 2013-2341, UBACYT 036, UBACYT 0384, CONICET PIP 11220110100596CO, MEALS 295261.


Gwenael Bothorel

Mathieu Serrurier

Christophe Hurter

Visualization of Frequent Itemsets with Nested Circular Layout and Bundling Algorithm

Keywords: Data Mining, frequent itemsets, graph visualization, bundling, optimization

Frequent itemset mining is one of the major data mining issues. Once generated by algorithms, the itemsets can be automatically processed, for instance to extract association rules. They can also be explored with visual tools, in order to analyze the emerging patterns. Graphical itemsets representation is a convenient way to obtain an overview of the global interaction structure. However, when the complexity of the database increases, the network may become unreadable. In this paper, we propose to display itemsets on concentric circles, each one being organized to lower the intricacy of the graph through an optimization process. Thanks to a graph bundling algorithm, we finally obtain a compact representation of a large set of itemsets that is easier to exploit. Colors accumulation and interaction operators facilitate the exploration of the new bundle graph and to illustrate how much an itemset is supported by the data.

Introduction

Frequent itemsets mining aims at finding links between data, which may not be easily detected. Among the varied fields of Data Mining, it is one of the most studied, because it is a key elements in mining pattern. This is why along two decades, it has been the subject of many studies and publications. For instance, in 1994, Agrawal and Srikant have presented Apriori algorithm which leans on frequent itemsets calculations [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF]. Later, other algorithms and methods have been studied, like CAP [START_REF] Ng | Exploratory mining and pruning optimizations of constrained associations rules[END_REF] or DHP [START_REF] Park | Using a hash-based method with transaction trimming for mining association rules[END_REF]. The frequent itemsets can be processed in a next step of automatic calculation, for instance in order to find associations rules. Representing and exploring data mining results is a challenging issue since the number of itemsets or rules can be very large when the complexity of the database increases. The association rules are displayed in systems like AViz, which is an interactive visualization system for discovering numerical association rules from large data sets [START_REF] Han | Aviz: A visualization system for discovering numeric association rules[END_REF], or ARVis which shows the rules and associated measures values in a 3D information landscape [START_REF] Blanchard | A user-driven and quality-oriented visualization for mining association rules[END_REF]. But before visualizing association rules, it is also interesting to visualize the frequent itemsets. FIsViz proposes such an approach [START_REF] Leung | FIsViz: A frequent itemset visualizer[END_REF]. It displays the frequent itemsets in a 2D space, by linking the items thanks to connecting edges. Such a tool gives a global graph of the dataset. It illustrates that it is necessary to use a graph when the purpose is the representation of itemsets. Indeed we have to show at the same time the data and the links between the different elements. Moreover, an element is generally involved in many itemsets that can have different sizes. So a graph layout is much adapted to show frequent itemsets. Thus, trying to find frequent itemsets patterns with such a presentation, is trying to find patterns in graph mining. This issue has been recently studied in [START_REF] Singh | Survey of finding frequent patterns in graph mining: Algorithms and techniques[END_REF]. It shows that graph mining has become an active and important theme in data mining. One problem is the complexity of the representation, considering the tremendous quantity of connections between the nodes.

As the number of edges can be very large in a graph representation of data, in recent years, graph bundling methods have gained increased attention. They stem from studies on confluent drawing by reducing non-planar graphs to planar ones [START_REF] Dickerson | Confluent drawings: Visualizing non-planar diagrams in a planar way[END_REF]. The purpose was to allow groups of edges to be merged together and drawn as 'tracks'. Bundling starts with a set of nodes positions, given as input data or computed by a layout algorithm. Edges being close in terms of graph structure, position, data attributes or combinations, are drawn as tightly bundled curves. This trades clutter for overdraw and produces images which are easier to understand and/or better emphasize the graph structure. Blending or shading can be used to add information or emphasize structure [START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF][START_REF] Lambert | Winding roads: Routing edges into bundles[END_REF][START_REF] Telea | Image-based edge bundles: simplified visualization of large graphs[END_REF]. Bundling algorithms exist for both compound (hierarchy-and-association) [START_REF] Holten | Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data[END_REF] and general graphs [START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF][START_REF] Cui | Geometry-based edge clustering for graph visualization[END_REF][START_REF] Gansner | Multilevel agglomerative edge bundling for visualizing large graphs[END_REF]. However attractive, many bundling algorithms for general graphs are relatively complex and have high computational costs. A recent study has proposed a faster method based on density maps using kernel density estimations. It relies on graphic cards acceleration techniques [START_REF] Hurter | Graph bundling by kernel density estimation[END_REF].

In this paper, we propose to apply a bundling method to a new graph representation of itemsets that takes advantage of their properties (Itemsets are described in Section 2). Itemsets are disposed on nested circles, each one corresponding to the number of items in the itemsets. Then an algorithm reorganizes the itemsets in order to have relevant proximities of the nodes. Finally the bundling algorithm is applied. As the proximity of the connections is a key factor indicating that they correspond to frequent itemsets, the bundling simplifies the clutter that becomes more readable (Section 3). Moreover, Infoviz techniques are used to enhance the visualization, particularly by using color and transparency accumulation, and interaction operators help the user to explore the bundle layout (Section 4).

Frequent Itemsets

Data mining consists in extracting knowledge from a vast volume of data. One purpose is to find relevant patterns that are underlied by this data. A database is a set of vectors < a i1 , a i2 , ..., a im >, also known as tuples, over an attributes space A = {A 1 , A 2 , ..., A m }. The attributes are qualitative (string, category, enumeration) or quantitative items which can be discretized. We denote an item as a value of an attribute (e.g. a i2 ). An itemset or k-itemset is a subset of values in the attributes space. k is the number of items concerned by the itemset: k ∈ {1, 2, ..., m}.

The database used to illustrate the paper is the Mushroom data set from the UC Irvine Machine Learning Repository1 . It includes descriptions of hypothetical samples corresponding to 23 species of gilled mushrooms. The database consists of 8416 tuples of 23 discrete attributes about the edibility, the cap shape, the odor, the ring, the habitat, etc. For instance the cap shape attribute may have curve, flat, bell values, and the odor may have almond, anise, none values. An example of 2-itemsets is {capshape = f lat, odor = anise}.

Itemsets are mainly characterized by the support which indicates the frequency they appear in the database (i.e. k-itemset with a frequency equals to 0.3 appears in 30% of the tuples in the database). A frequent itemset is an itemset which has a support greater than a threshold. Obviously, the support of a k-itemset is greater or equal than the support of a (k + 1)-itemset that contains this k-itemset. This (k + 1)-itemset is then named a superset of the k-itemset. So, as the value of k is increased, the support is decreased. As explained in [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF], the k-frequent itemsets are iteratively built thanks to the combinations of two (k -1)-frequent itemsets that differ only on a single item. For instance, the 2-itemset {a, b} is the combination of the 1-itemsets {a} and {b}. The 4itemset {a, b, c, d} is the combination of the 3-itemsets {a, b, c} and {a, b, d}, but it is also the combination of the 3-itemsets {a, b, d} and {b, c, d}, or {a, b, d} and {a, c, d}, etc. This type of approach ensures that all the k-frequent itemsets will be extracted given a support threshold and a maximal value of k.

One major challenge of data mining is the exploration and the analysis of the whole set of frequent itemsets which is usually very large.

Circular Graph Layout for Frequent Itemsets

Usually, frequent itemsets presentations are linear layouts as shown in Figure 1. This type of presentation becomes quickly unreadable as the number of nodes and frequent itemsets is increased, and the layout is horizontally stretched to show the whole graph. Moreover, to keep the unicity of each node in order not to clutter up the graph, several frequent itemsets are usually connected to the same nodes. Taking into account the construction of the itemsets, we propose a circular presentation shown in Figure 2. We build our representation in three steps:

1. Structure of the graph 2. Optimization of the itemsets positions 3. Graph bundling Structure of the Graph. The graph is built with concentric circles, separated from the same distance, each one corresponding to the cardinal of the frequent itemsets. The 1-itemsets are on the external circle, the 2-itemsets on the next smaller circle, and so on until the smallest circle corresponding to the frequent itemsets with the highest cardinal. On this circular graph layout, a node is a frequent itemset and the segments are the links between the frequent itemsets of two consecutive circles. An itemset is the combination of two previous itemsets. Note that it can stem from several pairs of previous itemsets (itemset {A, C, E} in Figure 2 for instance). In this case, all the combinations are represented. The distance between the nodes of a same circle is calculated in order to have an homogeneous repartition. Figure 4 shows examples of circular graphs.

Graph layouts with many nodes and edges have always to face the problem of readability due to the cluttering. A way to improve a circular graph layout, with one circle, has been studied in [START_REF] Gansner | Improved circular layouts[END_REF].

Optimization. In our study, to enhance the readability of the graph layout, we reorganize the itemsets on the circles, by minimizing the sum s of the segments length. In order to reduce s, we use a simple hill climbing algorithm which finds a local minimum. Two random itemsets are swapped on a random circle. If s is decreased then this permutation is kept, otherwise it is cancelled. This operation is done a large number of times in order to find a minimum value of s.

Graph Bundling. Graph bundling algorithms aims at simplifying a graph by merging close edges in order to obtain main tracks. We have chosen Kernel Density Estimation-based Edge Bundling [START_REF] Hurter | Graph bundling by kernel density estimation[END_REF] for its simplicity and speed. It is simple because it requires only an input graph with nodes positions. It is efficient because GPU processing allows to make it parallelizable and much faster than comparable methods. Considering that each edge links two itemsets of two consecutive circles, the begin and end points must not be moved. Thus the bundling algorithm must be applied to the partial graphs between two consecutive circles. So, with N circles, it must be applied N -1 times. The final layout is the combination of the partial bundlings (See Figure 3).

Our representation has many advantages:

• With the optimization, there is a coherence between the itemsets proprieties and their positions. Indeed if the itemsets are linked then they are more likely to be close. Otherwise, they are further. • Considering the way to build an itemset from previous ones, the combination complexity should always grow as the value of k increases, and become unreadable on a small circle. However, the constraints of the support limit this effect. Indeed the number of itemsets generally increases with the first values of k, and then decreases quickly. In Figure 4(a), there are 11 1-itemsets, then the number of itemsets increases and finally decreases to 8 5-itemsets. • The bundle layout is a way to simplify a complex graph. The optimization ordering the itemsets, the bundling groups edges that have common itemsets upstream or downstream. Thus the graph is more clear and easier to exploit compared to the original graph. The graph layouts of Figure 4(b) are completely unreadable, as the bundle graph gives information about the itemsets. Indeed with the latter it is easier to discriminate the edges leading to itemsets or leaving them. The whole process of generating the visualization takes less than two minutes. • The bundle representation is a way to detect many itemsets proprieties.

Indeed it is easier to notice if an itemset has many connections or not, to have an idea of the relations between itemsets. Thus areas where there are many connections correspond to areas where there is much information. This is illustrated in Figures 4 and5. Alpha Assignment. In order to emphasize the most relevant itemsets (i.e. the ones with greater support), we propose to use the support as the alpha transparency value. As the support concerns only the itemsets, that is to say the begin and end points of each edge, the value of the transparency gradients on the edges corresponds to the interpolation of the supports between these two points. It allows to have a continuous gradient of transparency, and that facilitates the layout overview. Color Accumulation. Another way to get information about the itemsets is to use accumulation. This technique is a consequence of edge bundling, because the bundling distorts the original segments to get bent overlaid edges. So, the more segments are involved in a bundle edge, the more accumulation there is, and it enhances the values of the color and the transparency. As a result the value of the support has a direct effect on the visibility and the color of the edges. Thus, a itemset with a high support appears with a high color level and a high opacity. This feature makes it easier to enhance the most itemsets that are involved in the database, and to reduce the others. Figure 5(a) illustrates these points. The RGBA value of the color is (1.00, 0.31, 0.21, 0.66). The right itemset corresponds to the attribute Gill attachment = free. It appears 8200 times in the database (support=97.4%), and has 11 supersets. As these values are large, the resulting accumulation of green and blue reaches 1.0, and it is the same for alpha. So the resulting color of the edges leaving this 1-itemset is (1.0, 1.0, 1.0, 1.0), which corresponds to white color without transparency. Moreover, the edge leaving leftward is white, whereas the edge leaving rightward is yellow. It indicates the area of the second circle where the 2-itemsets are more concerned by this 1-itemset, and where they are less concerned. The left itemset of Figure 5(a) corresponds to the attribute Stalk surface below ring = smooth. It appears 5076 times in the database (support=60.3%), and has 4 supersets. The visual aspect of the edges leaving this itemset shows that its support is lower and that it has fewer supersets than the right itemset. Indeed, the green component is quite low and the blue value is lower. So the resulting edge is orange, with some transparency. In Figure 5(b) we can easily remark that C and D have no supersets. This kind of remarkable itemset is known as maximal itemset. Such an itemset is especially valuable in data mining process. On the contrary, we can immediately deduce from the visualization that A and B are not maximal itemsets since they have at least one superset.

Itemsets Selection. In order to focus on one or more itemset we propose a selection tool. Selecting an itemset shows only its backward and forward connections, thanks to a propagation effect, while the other connections are hidden. Thus selecting the itemset A on Figure 2 highlights its connections to AC and AE, and from AC and AE to ACE. Selecting AC highlights its connections to A, C and ACE, and selecting ACE highlights its connections to AC, AE, CE, and then to A, C and E. Figure 6 shows an examples of this selection. On the left picture, the selection of the itemset Gill spacing=close (support = 81.1%) shows that it has five supersets on level 2. The propagation to the next levels gives seven, four and finally one itemset. Note that, as the algorithm (see Section 3) gathers the itemsets in the same areas, they are not spread on the graph.

It is also interesting to know for instance which 1-itemsets share the same 2-itemsets than the 1-itemset that is selected. A backward feature proposes to highlight differently these 1-itemsets, with a simple green color coding. So, by selecting a 1-itemset, there is a propagation to the supersets, and then to the other 1-itemsets that are previous itemsets of these supersets. As a consequence, when a 1-itemset is selected, it is easy to detect the other 1-itemsets that are linked to it. Thus it is easy to represent which attributes are related with a selected attribute. It is also possible to do it for any circle. The middle picture of Figure 6 illustrates this concept. We can see that the attributes that share the same supersets than Gill size=broad are Gill attachment=free, Veil color=white and Veil type=partial.

A second type of selection is the edges selection. By brushing an edge, it selects every edges that are grouped with it thanks to the bundling. This selection highlights all the connections forward and backward linked to the selected edges. It is a way to have a quick overview of the itemsets that are linked thanks to these edges. The right picture of Figure 6 shows an example of such a selection.

Finally, by considering the color properties of the edges, the proposed visualization gives a fast and relevant view of large set of itemsets. In addition to the advantages pointed out in the previous section, we enhance the visualization with the following properties:

• Identification of the relevant itemset. The itemsets with higher support are emphasized if the alpha value is associated with it. Moreover, the evolution of the transparency of an edge, from a larger circle to the lower one, gives information about the evolution of the support when the number of items increases. • Relevant areas of the circular graph. The accumulation of color, together with the optimization of the position, automatically emphasizes the areas where there is relevant information. It corresponds to areas where itemsets have a high support and are heavily linked. • Itemsets hierarchy identification. With selection, it is possible to focus on an itemset or a group of itemsets, by enhancing the other itemsets that are linked.

Conclusion

In this paper, we propose a new visualization of frequent itemsets based on a multi-circular graph which competes the state of the art visualizations in this domain. The position of the itemsets is optimized in order to improve the quality of the visualization while respecting and emphazing the properties of the itemsets. Then a Kernel Density Estimation-based Edge Bundling is applied. The result is a more simple graph of the frequent itemsets that shows the main streams in the layout, even when the number of itemsets is high. It enhances the most involved itemsets and their links. In other words it shows the most supported attributes in the database and how they are combined. We have proposed selection operators that can be used to focus on itemsets and on the way they take place in the graph. Thanks to color coding and accumulation, the importance of each itemset is highlighted or reduced. We have illustrated the effectiveness of our approach on the mushroom database from UCI Learning Repository.

In a future work, we plan to improve the optimization by using more efficient algorithms and allowing the itemsets to be placed more freely on the circles without keeping a constant distance between them. Moreover a view of the association rules stemming from enhanced or selected itemsets should be useful. Finally an evaluation will assess our visualization to verify that it is a good approach.

Fig. 1 .Fig. 2 .

 12 Fig.1. Examples of frequent itemsets linear layout. From[START_REF] Yang | Visualizing frequent itemsets, association rules, and sequential patterns in parallel coordinates[END_REF] (left) and WiFIsViz[START_REF] Leung | Wifisviz: Effective visualization of frequent itemsets[END_REF] (right)

Fig. 3 .Fig. 4 .

 34 Fig. 3. The final bundling is the result of successive partial bundlings between two consecutive circles. Example with four circles.

Fig. 5 .

 5 Fig. 5. (a) The accumulation of the color and the transparency is stronger on the right 1-itemset than on the others. It corresponds to a higher support. (b) Points C and D are maximal itemsets, whereas A and B are not.

Fig. 6 .

 6 Fig. 6. Different types of selections. Left: as a 1-itemset is selected, the propagation shows which itemsets stem from this itemset. Middle: the selection of a 1-itemset is disseminated to the supersets, and from these 2-itemsets to the 1-itemsets. It shows which attributes share the same itemsets than a chosen attribute. Right: brush selection of edges. It shows which itemsets are affected by this selection.

http://archive.ics.uci.edu/ml

Itemset Visualization EnhancementHaving built the itemsets circles, given a support threshold, we propose to enhance the visualization by three ways: