Keywords: Cloud Computing, Autonomic Computing, Service-based business process, Cloud resource allocation, Linear programming

Cloud Computing is a new paradigm that provides computing resources as a service over the Internet in a pay-per-use model. It is increasingly used for hosting and executing business processes in general and Service-based Business Processes (SBPs) in particular. Cloud environments are usually highly dynamic. Hence, executing these SBPs requires autonomic management to cope with the changes in Cloud environments, which implies the usage of a number of controlling devices, referred to as Autonomic Managers (AMs). However, existing solutions are limited to using either a centralized AM or an AM per service for managing a whole SBP. It is obvious that the latter solution is resourceconsuming and may lead to conflicting management decisions, while the former may lead to management bottlenecks. A main problem in this context consists in finding the optimal number of AMs for

Titre: Optimisation des ressources autonomiques pour la gestion des processus métier à base de services dans le Cloud Mots clés: Cloud Computing, Informatique autonome, Processus métier à base de services, Allocation de resources Cloud, Programmation linéaire Résumé: Le Cloud Computing est un nouveau paradigme qui fournit des ressources informatiques sous forme de services à la demande via internet. Il est fondé sur le modèle de facturation pay-per-use et il est de plus en plus utilisé pour le déploiement et l'exécution des processus métier en général et des processus métier à base de services (SBPs) en particulier. Les environnements Cloud sont généralement très dynamiques. À cet effet, il devient indispensable de s'appuyer sur des agents intelligents appelés gestionnaires autonomiques (AMs), qui permettent de rendre les SBPs capables de se gérer de façon autonome afin de faire face aux changements dynamiques induits par le Cloud. Cependant, les solutions existantes sont limitées à l'utilisation soit d'un AM centralisé, soit d'un AM par service pour la gestion d'un SBP. Il est évident que la deuxième solution représente un gaspillage d'AMs et peut conduire à la prise de décisions de gestion contradictoires, tandis que la première solution peut conduire à des goulots d'étranglement au niveau de la gestion du SBP. Par conséquent, il est essentiel de trouver le nombre optimal d'AMs qui seront utilisés pour gérer le SBP afin de minimiser leur nombre tout en évitant les goulots d'étranglement. De plus, en raison de l'hétérogénéité des ressources Cloud et de la diversité de la qualité de service (QoS) requise par les SBPs, l'allocation des ressources Cloud pour ces AMs peut entraîner des coûts de calcul et de communication élevés et/ou une QoS inférieure à celle exigée. Pour cela, il est également essentiel de trouver l'allocation optimale des ressources Cloud pour les AMs qui seront utilisés pour gérer un SBP afin de minimiser les coûts tout en maintenant les exigences de QoS. Dans ce travail, nous proposons un modèle d'optimisation déterministe pour chacun de ces deux problèmes. En outre, en raison du temps nécessaire pour résoudre chacun de ces problèmes qui croît de manière exponentielle avec la taille du problème, nous proposons des algorithmes quasi-optimaux qui permettent d'obtenir de bonnes solutions dans un temps raisonnable. the management of an SBP, minimizing costs in terms of number of AMs while at the same time avoiding management bottlenecks and ensuring good management performance. Moreover, due to the heterogeneity of Cloud resources and the diversity of the required Quality of Service (QoS) of SBPs, the allocation of Cloud resources to these AMs may result in high computing costs and an increase in the communication overheads and/or lower QoS. It is also crucial to find the optimal allocation of Cloud resources to the AMs, minimizing costs while maintaining the QoS requirements. To address these challenges, we propose in this work, a deterministic optimization model for each problem. Furthermore, due to the amount of time needed to solve each one of these problems, which grows exponentially with the size of the problem, we propose near-optimal algorithms that provide good solutions in a reasonable time.

I would like to thank the members of the thesis committee. I thank the committee president Professor Habib Ounelli for accepting to chair my thesis defense, the reading committee members Professor Xavier Blanc and Professor Leila Jemni Ben Ayed for their interest and Professor Hanna Klaudel for evaluating my work and being part of the defense committee.

I would like to express my deepest gratitude to my advisors, Professor Faouzi Ben Charrada and Professor Samir Tata, for their generous support without which this thesis would not have been possible. Despite their many responsibilities, they have always found time to provide feedbacks, new ideas and suggestions on my work. I thank them for allowing me to grow as a research scientist.

I owe my deepest appreciation to the members of the Computer Science department at Telecom SudParis. I would like to thank Brigitte Houassine for her kind help and assistance. Many thanks to Aicha, Nabila, Amina, Hayet, and Rania for the lovely moments we spent.

A special thank to my friends Sarra, Maweheb, and Anouer for their emotional support and for all their help. I am forever thankful to my family: my father, my mother, and my sister who were always there for me with encouraging words whenever I started doubting myself. Your encouragement made me go forward and made me want to succeed. Thank you so much for having faith in me. I love you so much.

Chapter 1

General Context

Over the last decade, Cloud computing has appeared as an emerging paradigm, based on the pay-per-use economic model, for the provisioning of on-demand computing resources (e.g. networks, servers, storage, applications, and services) as a service over the Internet. These resources can be dynamically and easily provisioned and released with a minimal effort [START_REF] Mell | Sp 800-145. the nist definition of cloud computing[END_REF]. The Cloud paradigm basically utilizes three delivery service models known as Infrastructure as a Service (IaaS), Platform as a Service (PaaS), and Software as a Service (SaaS). The adoption of this paradigm is rapidly increasing due to its capacity to reduce the management complexity and cost for enterprise customers while increasing scalability and flexibility and to provide ongoing revenue for providers [START_REF] Wu | Sla-based resource provisioning for hosted software-as-a-service applications in cloud computing environments[END_REF]. According to a survey conducted by the IDG Enterprise [START_REF] Enterprise | Cloud Computing Survey[END_REF] in 2016, 70 percent of the companies were at that time adopting the Cloud. However, 16 percent of them planned to adopt it in the following 12 months, while the remaining will have migrated to the Cloud within the following three years. Cloud environments are increasingly used for hosting and executing business processes, especially Service-based Business Processes (SBPs) [START_REF] Papazoglou | Blueprinting the cloud[END_REF]. An SBP is built according to 1 Service Oriented Architecture (SOA) and consists of a set of elementary and heterogeneous services which are related in terms of their contribution to the realization of the business process. Assembling services into an SBP can be ensured by using any appropriate service composition specification, such as Business Process Model and Notation (BPMN) [START_REF] White | Introduction to bpmn[END_REF], Unified Modeling Language (UML) activity diagram [START_REF] Booch | Unified Modeling Language User Guide, The (2Nd Edition) (Addison-Wesley Object Technology Series[END_REF].

However, executing SBPs in the Cloud is exposed to dynamic evolution workload and fluctuation during their life-cycle due to the dynamic nature of the environment. Consequently, the management of SBPs in Cloud environments is a challenging task. Indeed, the management of such business processes is time and effort consuming, not to mention the risks of being an error-prone process and the need for costly experts. In response to this problem, one of the main adapted technique is to resort to autonomic computing to enforce the autonomy and ensure the required Quality of Service (QoS) of SBPs. Autonomic computing [3] is the ability of a computing system to automatically and dynamically manage itself to respond to the requirements of the business based on on service level agreement. We advocate that coupling Cloud computing with autonomic management is really interesting since it allows intelligently coping with the dynamic evolution of Cloud environments with minimal human intervention [4]. This coupling is possible by means of Autonomic Managers (AMs) [3] that consist in collecting monitoring data from a running SBP, analyzing them, and planning and executing adaptation actions to meet the requirements of the managed SBP.

The autonomic management of an SBP implies the usage of one or more AMs, which are dedicated to the management of the services that make up the SBP. These services are generally deployed on different heterogeneous Cloud resources (i.e. virtual machines). Consequently, the efficiency of the management of SBPs as well as their performance depend highly on the allocation decisions of AMs and Cloud resources by these AMs in respect of the agreement between the service consumer and its provider.

Motivation and Problem Statement

When applied to SBPs in a Cloud environment, autonomic management becomes a complicated problem that faces many challenges. The first challenge faced by Cloud providers is to optimize the number of AMs for the management of SBPs. In fact, using a centralized AM for the monitoring and adaptation of a whole SBP can lead to management bottlenecks and single points of failure [START_REF] Florio | Gru: An approach to introduce decentralized autonomic behavior in microservices architectures[END_REF]. Thus, to reduce the load on the centralized AM and avoid bottlenecks and single points of failure, a solution is to dedicate different AMs to the SBP services, but this solution is resource-consuming. Consequently, it is interesting to autonomically manage SBPs such that the number of AMs is minimized while avoiding management bottlenecks.

It is obvious that determining the appropriate number of AMs for the management of SBPs is not sufficient to provide efficient management of deployed business processes. In fact, it is also necessary to consider the allocation decisions of Cloud resources to these AMs in the Cloud, which allows fulfilling the business process QoS requirements. Thus, the second challenge is to optimize the allocation of Cloud resources to host and execute AMs that will be used to manage SBPs. In fact, due to the heterogeneity of Cloud resources and the diversity of the SBP services QoS needs, the allocation of Cloud resources to SBPs may result in high computing costs and an increase in the communication overheads. Consequently, it is interesting to select the right Cloud resources to achieve an efficient SBPs deployment such that the overall deployment cost is minimized while fulfilling SBPs QoS requirements.

Many attempts to provide autonomic management of applications in the Cloud have been proposed, but as we will explain, almost all the proposed solutions are limited to modeling and implementing autonomic mechanisms. It is worth noting that the existing approaches either do not take care of management cost issue, they do not optimize the Cloud resource allocation during the SBPs management process or do not include an efficient management of SBPs. In addition, the existing works on the optimal resource allocation are not suitable to solve the previously described problems because the number of these resources is considered as an input, which is not the case for AMs.

Objectives and Contributions

The main goal of this thesis is to propose an efficient solution for allocating Cloud resources to autonomic SBPs based on optimization programs that aim to provide an optimal number of AMs for the management of SBPs as well as optimal placement of these AMs in the Cloud. The objective of the optimization programs is to minimize the Cloud resource allocation cost while ensuring the QoS of deployed SBPs and avoiding the management bottlenecks. This thesis does not discuss all the aspects related to the autonomic management of SBPs. For example, we do not deal with modeling and implementing autonomic mechanisms or coordinating AMs. While we believe that a lot of issues related to autonomic management are important to address, the problem discussed here is complex enough to deserve a separate treatment.

To achieve our targeted objectives, this thesis makes the following contributions:

• AMs optimization in SBPs.

• AMs components optimization in timed SBPs.

• Placement of AMs for the management of SBPs in the Cloud.

AMs Optimization in SBPs

Executing SBPs in Cloud environments requires AMs to cope with the changes in these environments. However, using a centralized AM for managing a large number of services can lead to management bottlenecks and performance degradation of SBPs. While using an AM per service is resource-consuming, we argue for a decentralized approach that aims to reduce the number of AMs while avoiding management bottlenecks.

In our work, we opt for the use of directed graphs to formally represent SBPs to focus on all service dependencies between them when processing their management. We propose an exact optimization model that aim to find the optimal number of AMs for the management of SBPs. The amount of time needed to solve this problem grows exponentially with the size of the graph, so we propose near-optimal approaches that provide good solutions in a reasonable time. We use the exact optimization model for smaller graphs to benchmark our approaches that exhibit better scaling behavior, possibly at the expense of optimality.

AMs Components Optimization in Timed SBPs

An AM consists of four main components: a monitor, an analyzer, a planner, and an executor. Therefore, to further optimize the Cloud resource allocation cost, we propose to extend our work by considering these components separately in the optimization process. Doing so, we first propose an exact optimization model to find the optimal number of monitors, analyzers, planners, and executors for the management of SBPs such that their QoS is satisfied while avoiding management bottlenecks. Then we introduce a nearoptimal algorithm that provides good solutions faster. We use the exact optimization model for smaller graphs to compare our algorithm to the optimal solution.

Placement of AMs for the Management of SBPs in the Cloud

Due to the heterogeneity of Cloud resources and the diversity of SBPs QoS needs, the allocation of Cloud resources to autonomic SBPs may result in high computing costs and an increase in the communication overheads and/or lower QoS if resource allocation is not well addressed. Indeed, several works [START_REF] Hoenisch | Cost-efficient scheduling of elastic processes in hybrid clouds[END_REF][START_REF] Mastelic | Predicting resource allocation and costs for business processes in the cloud[END_REF][START_REF] Rekik | A linear program for optimal configurable business processes deployment into cloud federation[END_REF] have been proposed to determine the optimal placement of SBP services in the Cloud, but there is no approach that tries to solve the optimal placement of AMs that will be used to manage these SBPs in the Cloud. Hence, we first suggest exact optimization models to solve this problem where the number of AMs is known or not known in advance. After that, we propose two different approaches that provide effective placement of AMs in the Cloud such that the required QoS of deployed SBPs is met while reducing the used Cloud resources in a cost-efficient way as per the economic model of the Cloud.

Thesis Outline

The rest of this thesis is organized as follows: Chapter 2 presents the different concepts used throughout our thesis as well as the state of the art of our research. In this chapter, we start by giving the definitions of Cloud computing, SOA and SBPs, autonomic computing as well as an overview of optimization problems. We then give an overview of the existing works related to autonomic computing as well as optimal resource allocation. Therein, we will cite the different works in each area to highlight the existing limitations and emphasize the significance of our work.

Chapters 3, 4, and 5 are the core of our thesis which elaborate our approach to optimize Cloud resource allocation for the management of SBPs. Illustrative examples and experiment results are provided in each chapter.

In Chapter 3, we present our solution to determine the optimal number of AMs for the management of SBPs. Our objective is to minimize the number of AMs while avoiding management bottlenecks. The proposal entails the Integer Linear Programming (ILP) solution as well as a set of algorithms to solve the problem based on the representation of SBPs (i.e. graph with or without cycles). The main content of this chapter was published in [START_REF] Hadded | An efficient optimization algorithm of autonomic managers in service-based applications[END_REF]21].

In Chapter 4, we push further our work by proposing to determine the optimal number of AMs components separately for the management of SBPs. The objective is to minimize their number while avoiding management bottlenecks. Our proposal entails the ILP solution as well as a set of algorithms to solve this problem. The main content of this chapter was published in [22,[START_REF] Hadded | Optimization of autonomic manager components in service-based applications[END_REF].

In Chapter 5, we present our solution to determine the optimal placement decisions of AMs or AMs components that will be used to manage SBPs. The objective is to minimize the Cloud resource allocation while fulfilling the QoS requirements of SBPs. The chapter content was published in [22,[START_REF] Hadded | Efficient resource allocation for autonomic service-based applications in the cloud[END_REF].

Finally, in Chapter 6, we conclude this thesis by summarizing our contributions and giving an outlook of future work.

Chapter 2

Background & State of the Art

Introduction

In this thesis, we aim to provide a solution for optimizing autonomic resources for the management of SBPs in Cloud environments. In order to understand the rest of this manuscript, we dedicate the first section of this chapter to briefly introduce a basic knowledge on different concepts and paradigms related to our work (Section 2.2). We start by presenting the environment of our work which is Cloud Computing. Afterwards, we define the service oriented architecture as well as SBPs that represent the type of applications that we basically target. Next, we introduce the concept of autonomic computing as well as a brief background about optimization problems. In the second section, we discuss the existing works on autonomic management in distributed systems and optimal resource 6 allocation to service-based applications (Section 2.3). Finally, we conclude the chapter in Section 2.4.

Background

In this section, we present definitions and basic concepts related to our work. First, we introduce the context of our work, which is Cloud Computing. Then, we introduce SBPs that represent the specific type of applications that we target. Finally, we define the concept of autonomic computing that we aim to address in our work.

Cloud Computing

Cloud Computing is an emerging paradigm in information technology. According to the National Institute of Standards and Technology (NIST) [START_REF] Mell | Sp 800-145. the nist definition of cloud computing[END_REF], it is a model for enabling ubiquitous, convenient, on-demand network access to a shared pool of configurable computing resources (e.g. networks, servers, storage, applications, and services) which can be rapidly provisioned and released with minimal management effort or service provider interaction. Cloud computing is characterized by its pay-per-use economic model that allows a user to consume Cloud resources as needed. Virtualization forms the foundation of Cloud computing, as it is a key technology that makes Cloud computing possible. It abstracts physical hardware resources typically as Virtual Machines (VMs) with associate storage and networking connectivity, allowing applications to run in different VMs in a flexible manner [25]. Through virtualization, a Cloud provider can ensure the Quality of Service (QoS) delivered to users while achieving an energy efficiency and high server utilization.

Services in the Cloud are basically delivered under three layers:

• Infrastructure as a Service (IaaS): It provides to consumers processing, networks, storage, and other computing resources so as to deploy and run software, which can include operating systems and applications. Examples of IaaS infrastructures are Amazon AWS1 and Google Compute Engine Nowadays, more services have appeared, called as XaaS, where X stands for anything that can be provisioned and abstracted as services. Examples include NaaS for Network as a Service, DaaS for Desktop as a Service, etc.

Clouds can be provisioned following different models according to the requirements of users. Whenever the Cloud infrastructure is exclusively used by a single organization that owns, manages and maintains the Cloud, we talk about Private Cloud. However, if the Cloud infrastructure is used by a specific community of consumers from different organizations that own and operate it, we talk about Community Cloud. Otherwise, if the Cloud infrastructure is exposed to public use, we talk about Public Cloud. There is another model in which the Cloud infrastructure is composed of two or more distinct Cloud infrastructures (public, private, or community), we talk herein about Hybrid Cloud.

Service-Oriented Architecture and Service-based Business Processes

Service-Oriented Architecture (SOA) is a software architecture that is based on services as fundamental elements for developing and integrating applications [26]. A service is a self-describing component that supports rapid, low cost development and deployment of distributed applications. The goal of this architecture style is to meet the requirements of loosely coupled, standards-based, and protocol-independent distributed computing. As defined by Papazoglou [START_REF] Papazoglou | Service-oriented computing: concepts, characteristics and directions[END_REF], SOA is a logical way of designing a software system to provide services to either end user applications or other services distributed in a network through published and discoverable interfaces.

The SOA is structured around the three actors illustrated in Figure 2.2: a service provider, a service consumer, and a service registry; whereas, the interactions between these actors involve publish, find and bind operations. Service provider is the role of a software entity providing a service. Service consumer is the role assumed by a requesting entity that seeks to consume a specific service. However, service registry is the role assumed by an entity that maintains information on available services as well as the way to access them. The advantage of this approach lies in the loose coupling of the services composing an application. Services are provided by independent parts of a platform, which implies that a client using any programming language, operating system and any computational platform can use the services, although different service providers and service customers may use different technologies to implement and access the services. Thus, an application can be made up of different services provided by heterogeneous parts with respect to their services descriptions.

A business process is an ordered set of services aiming to reach a business objective or policy goal, normally within the context of an organizational structure that defines functional roles and relationships. A process may be wholly contained in a single organizational unit or may span mutiple different organizations such as in a customer-supplier relationship [START_REF] Coalition | Terminology and glossary (wfmctc-1011)[END_REF].

An SBP is a business process that consists in assembling a set of elementary IT-enabled services which are related in terms of their contribution to the overall realization of the process. A service is typically the smallest unit of work that represents a module offering computation or data capabilities. It carries out the business activities of an SBP.

Assembling services into an SBP can be ensured using any appropriate service composition specification such as Event-driven Process Chains (EPCs) [START_REF] Van Der Aalst | Yawl: yet another workflow language[END_REF], Business Process Modeling Notation (BPMN) [START_REF] White | Introduction to bpmn[END_REF], and UML activity diagram [START_REF] Booch | Unified Modeling Language User Guide, The (2Nd Edition) (Addison-Wesley Object Technology Series[END_REF]. In this thesis, we aim to abstract away from these specific notations and focus on basic commonalities of these languages [START_REF] Van Der Aalst | Workflow patterns[END_REF]. Accordingly, we define an SBP as a set of services and gateways that are connected by control-flow arcs. Throughout this thesis, we consider the following types of gateways; each acts as either a split or a join node. Split gateways have exactly one incoming edge and at least two outgoing edges. Join gateways have at least two incoming edges and exactly one outgoing edge.

• Parallel (AND) indicates that all branches must be executed in parallel. AND-split enables all its outgoing branches to execute concurrently. AND-join waits until all its incoming branches have completed their execution.

• Inclusive (OR) is used when at least one branch must be executed. OR-split enables one or more of its outgoing branches to execute whose condition evaluates to true. OR-join waits until all the latter branches have completed their execution.

• Exclusive (XOR) specifies that only one branch must be executed. XOR-split enables only one of its outgoing branches to execute. XOR-join waits until the chosen branch has completed its execution.

Autonomic Computing

Autonomic computing aims to build computing systems capable of self-management without needing human intervention. It is inspired by the human body's autonomic nervous system that monitors heartbeat, checks blood sugar levels, and keeps the body temperature normal without any conscious effort from the human [2]. The term autonmic was originally coined by IBM in 2001 [3]. IBM defines autonomic computing as the ability to manage computing resources that automatically and dynamically respond to the requirements of the business based on Service Level Agreement (SLA). Management tasks like monitoring, protection, configuration and optimization are the non-functional objective of most applications, but they have a critical importance for applications to accomplish their tasks. Thus, the challenge is to enable self-managing computing systems that take control of all the non-functional tasks in order to let the developers focus on the main functional tasks of applications. To do so, there must exist a way to develop self-governing features and to integrate them with applications. To achieve autonomic computing, IBM has suggested a reference model for an autonomic resource called Autonomic Manager (AM), also known as the MAPE-K (Monitor, Analyze, Plan, Execute, Knowledge) loop [2], as illustrated in Figure 2.3. An AM is a software agent that implements the autonomic behavior. A managed resource represents any hardware or software resource that is coupled with an AM to exhibit an autonomic behavior. Sensors are used by an AM to collect information about the state of a managed resource, while effectors are used by an AM to carry out changes to a managed resource. A common element, called Knowledge, represents the management data (e.g. adaptation strategies, change plans, etc.), which can be shared between the phases (i.e. monitor, analyze, plan, and execute) of the control loop. An AM gathers monitoring information from the managed resource through sensors where this information is stored in the knowledge base. The latter data are then analyzed in order to determine whether an adaptation is required. If it is the case, an adaptation plan is provided by the AM and the latter plan is executed over the managed resource through effectors.

Optimization Problems

Classification of optimization problems

Optimization problems can be classified according to several criteria. An important classification of these problems is based on the nature of equations for the objective function and the constraints. Optimization problems can be classified into four classes: linear, nonlinear, quadratic, and geometric programming [START_REF] Rao | Engineering Optimization: Theory and Practice: Fourth Edition[END_REF].

• Linear Programming (LP): In this type of problems, both the objective function and the constraints are linear functions of variables. LP problems can be classified according to their decision variables as Integer Linear Programming (ILP), where all variables are integer, and Mixed Integer Linear Programming (MILP) problems, where some but not all variables are integer.

• Nonlinear Programming (NLP): In this type of problems, any of the functions among the objective function and the constraints is nonlinear.

• Quadratic Programming (QP): This category of problems has a quadratic objective function and linear constraints.

• Geometric Programming (GP): In this type of problems, the objective function and the constraints are expressed as polynomials.

Optimization problems can be classified also based on the deterministic nature of the variables as deterministic and stochastic programming problems [START_REF] Rao | Engineering Optimization: Theory and Practice: Fourth Edition[END_REF].

• Deterministic Programming: In this type of optimization problems, all the design variables are deterministic. A model is deterministic if, for a given input, it always produces the same output.

• Stochastic Programming: In this type of problems, some or all of the parameters of the optimization problem are considered as random or probabilistic variables (nondeterministic or stochastic). A stochastic variable is a variable that has different values with certain probabilities.

Complexity of optimization problems

There are mainly two classes of optimization problems: P and NP [START_REF] Bovet | Introduction to the Theory of Complexity[END_REF]. In fact, NP-Hard problems are generally difficult to solve and time-consuming. They are often addressed using approximation algorithms.

P

Definition 2.2.3. An approximation algorithm is an algorithm that always returns a feasible solution in polynomial time to an optimization problem.

Although approximation algorithms provide near-optimal solution, it is interesting to study the quality of approximate solutions where there are two equivalent measures of this quality: the relative error and the optimality gap. Definition 2.2.4. Given an optimization problem, for any instance i of this problem, we denote by m(i) the feasible solution and by opt(i) the optimal solution with respect to instance i. The relative error is defined as:

E(i) = m(i) -opt(i) opt(i)
For both minimization and maximization problems, if the relative error is equal to 0, the approximate solution is optimal. It becomes close to 1 when the obtained solution is very poor. Definition 2.2.5. The optimality gap of an approximate solution is expressed in % and is defined as:

G = E(i) × 100

State of the Art

In this section, we present a selection of works around autonomic computing in Cloud and distributed environments (Section 2.3.2) and optimal resource allocation (Section 2.3.3). In fact, a plethora of studies exists in the literature aiming to provide autonomic computing and optimal resource allocation solutions, but to the best of our knowledge, these proposals treat the two areas separately. In this manuscript, we will refrain from citing all these studies to highlight just a selection of them that we believe representative.

Evaluation Criteria

To address the autonomic management of SBPs issues mentioned in Section 1.2, the proposed approach should provide appropriate ways to efficiently manage SBPs by determining the appropriate number of AMs and selecting the appropriate Cloud resources to host and execute these AMs such that the management cost is minimized while avoiding management bottlenecks to fulfill the QoS requirements with minimal costs. In addition to that, it should cover complex business process patterns like AND-blocks, OR-blocks, XOR-blocks and Repeat Loop which are very common in real world business processes [START_REF] Van Der Aalst | Workflow patterns[END_REF]. It should also be suitable for small and large SBPs and structured and unstructured SBPs.

Autonomic Computing

IBM is a pioneer in the field of autonomic computing that proposed a dedicated toolkit, which is a set of tools and technologies designed to permit users to develop autonomic behavior for their systems. The authors in [3] introduced the needed steps to add autonomic capabilities to resources. One of the basic tools is the autonomic management engine that includes representations of an AM which provides self-management properties to managed resources. Furthermore, IBM suggested several tools to allow managed resources to create log messages using a standard format understandable by the AM. This is achieved using a touch-point that consists of a sensor and an effector. The sensor detects the state of the managed elements and generates logs, while the effector is used to carry out adaptations on the managed resource. Moreover, an adapter rule builder is proposed to create specific rules to generate adaptation plans. In [4], the authors put forward a conceptual architecture enabled the autonomic management of SaaS applications in Cloud environments. The proposed architecture was basically composed of a SaaS Web application that hosted the SaaS application and negotiates the SLA between the service provider and consumers, an Autonomic Management System (AMS) integrated in the PaaS level, and an IaaS layer that provided Cloud resources. As shown in Figure 2.5, the AMS incorporates an application scheduler assigns each service in an application to Cloud resources and an energy-efficient scheduler that minimizes the energy consumption during the application scheduling process. The AMS implements logic for provisioning and managing virtual resources according to the resource requirements specified by the application scheduler. It incorporates also a component to detect security infraction and attack tentatives. Rainbow [5] is a framework that uses an architecture-based approach to add selfadaptation mechanisms to software systems. The proposed framework uses an abstract model to represent an application as a graph. Vertices in the graph represent components, and arcs represent interactions between components. A model manager is used to continuously adapt the model. It collects monitoring data from the model through probes. The latter data is analyzed using a constraint evaluator to detect violations and trigger adaptation. The appropriate adaptation plan is chosen using an adaptation engine and is applied using an executor. As shown in Figure 2.6, the framework is divided into architecture, translation and system layers. The architecture layer consists of the needed components to self-manage a system. The system layer describes the managed system access interface (e.g. probes, effectors). Between these two basic layers, the translation infrastructure is used as a mediator to exchange information. In [START_REF] Ribler | Autopilot: adaptive control of distributed applications[END_REF], the authors proposed a framework for dynamically adapting applications to the changes of environments. A real-time monitor checks applications and triggers adaptation if a constraint violation occurs to meet the desired goals. The functionalities of the framework are implemented in separate components: sensors, actuators, distributed name servers, and clients. Sensors and actuators are used to remotely collect and modify the values of application variables. They have to register themselves to a name server (registry). Clients specify a set of desired properties, and the manager provides start points to the interesting sensors or actuators in order to allow clients to establish direct communication with applications.

The authors in [START_REF] Asadollahi | StarMX: A framework for developing self-managing Java-based systems[END_REF] introduced a generic framework to create Java-based applications with self-managing properties. It was an open source project that used Java management extensions to enable self-managing capabilities where management logic was separate from application logic. The framework implemented adaptive behavior using policy languages or Java codes following condition-action rules. As depicted in Figure 2.7, it consists of two main elements: the Execution Engine and a set of Services. The Execution Engine enables AMs to perform their jobs using services provided by the Services element. Management logic is implemented as a set of entities called processes where each process may implement one or more consecutive components of an AM. The composition of processes forms an execution chain which acts as an AM. C. Ruz et al. [START_REF] Ruz | Component-based generic approach for reconfigurable management of component-based SOA applications[END_REF] suggested a framework that allowed the monitoring and management of component-based applications. As presented in Figure 2.8, the authors separated components for the monitoring, SLA analysis, decision, and execution of a classical AM. These components were attached to each component to manage it, where these components could be added or removed if necessary and each one could communicate with other components. The monitoring component would gather information from the managed component. The SLA analyzer component would compare the collected data to previously defined SLA. The decision component would generate a sequence of actions to be applied on the managed component to meet SLA. The execution component would apply the decided actions. N. Belhaj et al. [START_REF] Belhaj | Self-adaptive decision making for the management of component-based applications[END_REF] introduced an approach to improve the decision making process of a traditional AM to dynamically adapt component-based applications. To do so, the authors equipped the analyzer component with sophisticated learning blocks instead of using inflexible hand-coded strategies where its decision making process was formulated as a Markov decision process with a finite set of states and actions. During each state transition, a reinforcement signal would indicate to the proposed decision maker whether it would choose the appropriate action for the current state or not. In this work, each component of an application is self-managed by its own AM.

In [START_REF] Mola | Collaborative policy-based autonomic management: In a hierarchical model[END_REF], the authors focused on the collaboration between multiple policy-based AMs to efficiently manage the overall system. AMs are organized in a hierarchical structure where the higher-level AMs have more authority over AMs of lower levels. The lower-level AM is responsible for allocating resources, such as memory and CPU, to the Web server to improve its response time and avoid SLA violations. An AM requests the help of a higher level AM when no further local adjustments are possible. These AMs communicate by exchanging predefined messages by means of a message broker. F. de Oliveira et al. [START_REF] De Oliveira | A framework for the coordination of multiple autonomic managers in cloud environments[END_REF] proposed a framework for the coordination of AMs in Cloud environments. This framework would improve the synergy between AMs. As shown in Figure 2.9, each application is managed by its own Application AM (AAM) which is responsible for determining the best architectural configuration and the minimum amount of VMs needed to deliver the best QoS under a certain workload. the IaaS layer (physical machines and VMs) is managed by a single Infrastructure AM (IAM) which is responsible for the optimal placement of VMs. The IAM is composed of a public knowledge while each AAM maintains a private knowledge. AAMs can make changes to the public knowledge using a synchronization protocol. This protocol uses a token to synchronize the actions executed by the access of AMs to the shared knowledge in order to avoid concurrency and consistency problems and to make the knowledge available to both SaaS and IaaS resources. An event-based coordination protocol is also proposed to coordinate the AMs actions. Beside the abovementioned approaches, there is a lot of other work in the literature related to autonomic computing [START_REF] Ionescu | A Robust Autonomic Computing Architecture for Server Virtualization[END_REF][START_REF] Baker | Towards Autonomic Cloud Services Engineering via Intention Workflow Model[END_REF][START_REF] Frey | Towards a generic architecture and methodology for multi-goal, highly-distributed and dynamic autonomic systems[END_REF][START_REF] Kurian | An autonomic computing architecture for business applications[END_REF][START_REF] Gueye | Component-based autonomic managers for coordination control[END_REF][START_REF] Martinovic | E-health Framework Based on Autonomic Cloud Computing[END_REF][START_REF] Mohamed | An autonomic approach to manage elasticity of business processes in the cloud[END_REF]. However, to the best of our knowledge, all the existing works have been limited to modeling and implementing autonomic environments. They either do not take care of the management cost issue by using an AM per SBP service, or do not include an efficient management of SBPs by using a centralized AM to manage all the SBP services that can lead to management bottlenecks and/or a violation of QoS. In addition, we have not found any work that aims to achieve good trade-offs between management performance and management costs by attempting to optimize the used AMs and Cloud resources allocated to these AMs during the management process while respecting QoS constraints and avoiding management bottlenecks. In contrast, in our proposal, we will give solutions to manage SBPs such that the number of AMs as well as the Cloud resources allocated to these AMs are optimized in a cost-efficient way while avoiding management bottlenecks and fulfilling the QoS constraints.

Optimal Resource Allocation

Cloud environments

In a Cloud environment, the resource allocation process consists in selecting an optimal set of physical machines to host the received services while respecting resource and QoS constraints. To solve this NP-Hard problem [START_REF] Rajkumar | Practical solutions for qos-based resource allocation[END_REF], many works have been proposed that aim to achieve good trade-offs between solution quality and computation time. Some of them are summarized below.

In [START_REF] Hoenisch | Optimization of complex elastic processes[END_REF], the authors presented a cost-efficient deployment approach for Business Processes (BPs) in the Cloud. They proposed an optimization model based on the MILP technique to achieve an optimal scheduling and placement of services that would compose a BP on VMs. The objective was to minimize the cost of leased Cloud resources and the penalty cost that would arise when a process execution did not meet a user-defined deadline while guaranteeing the defined QoS. In [START_REF] Hoenisch | Cost-efficient scheduling of elastic processes in hybrid clouds[END_REF], the authors extended this work by considering an inter-cloud data transfer cost.

In [START_REF] Bessai | Resources allocation and scheduling approaches for business process applications in cloud contexts[END_REF], Bessai et al. proposed resource allocation and scheduling models for BP applications in the Cloud. A BP was represented as a Directed Acyclic Graph (DAG). The authors defined two optimization models to determine the optimal assignment of tasks that would make up a BP to VMs such that the overall execution time (respectively cost) was minimized. They took into account the execution time and cost for each task and the data transfer time and cost between tasks that depended on resources that executed them. They also proposed three optimization algorithms that provide nearoptimal solutions based respectively on the execution cost, the overall execution time, and a priority-based Pareto efficient combination.

Fakhfakh et al. [START_REF] Fakhfakh | Dealing with structural changes on provisioning resources for deadline-constrained workflow[END_REF] suggested a provisioning solution of Cloud resources for dynamic workflow applications. The objective was to find a Cloud resource allocation that would minimize the execution cost while satisfying a defined deadline. The authors put forward an algorithm that mapped Cloud resources (VMs) to workflow tasks, and if needed, some adaptation actions could be performed to cope with exceptional situations and evolution where a workflow was modeled as DAGs. They considered the data transfer time between tasks that only depended on the amount of data to be transferred between the corresponding tasks.

The work presented in [START_REF] Jiajie | Incorporating structural improvement into resource allocation for business process execution planning[END_REF] addressed the problem of resource allocation for BPs. To this end, the authors proposed an approach that would improve the process structure based on resource allocation requirements such that the overall cost was minimized while meeting the process execution time requirement. The structure of a BP was modeled as a DAG. They applied a basic allocation strategy to minimize the overall cost without considering the time limit. Then an adjustment strategy was applied to adjust the allocation scheme to ensure that the overall execution time of the process did not exceed the time limit.

In [START_REF] Malawski | Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds[END_REF], the authors addressed the problem of scheduling and resource provisioning for scientific workflow where a scientific workflow was modeled as a DAG. They looked for an efficient mapping of tasks to available resources and selecting of the best resource provisioning plan under budget and deadline constraints. To this end, they proposed a set of algorithms based on offline and online strategies for task scheduling and resource provisioning that relied on estimates of task runtimes.

Goettelmann et al. in [START_REF] Goettelmann | Partitioning and cloud deployment of composite web services under security constraints[END_REF] suggested an algorithm for deploying BPs on different Cloud platforms under security constraints. The main idea was to split a BP into sub-processes and deploy them in different Clouds to meet security requirements. A security level was assigned to each BP task describing its security requirements, and arbitrary security levels were assigned to Cloud providers. The algorithm would select the suitable Cloud providers which offered the minimum communication costs between the derived sub-processes.

Beside the aforementioned approaches, there have been many other attempts to optimize resource allocation for deploying BPs in the Cloud [START_REF] Labba | Adaptive deployment of servicebased processes into cloud federations[END_REF][START_REF] Halima | Optimal cost for time-aware cloud resource allocation in business process[END_REF][START_REF] Jianfang | An optimized scheduling algorithm on a cloud workflow using a discrete particle swarm[END_REF][START_REF] Yusoh | Composite saas placement and resource optimization in cloud computing using evolutionary algorithms[END_REF][START_REF] Wu | Workflow-based resource allocation to optimize overall performance of composite services[END_REF][START_REF] Abrishami | Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds[END_REF][START_REF] Pandey | A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[END_REF]. Up to our knowledge, almost all of the proposed solutions have not dealt with the repeat-loop pattern, i.e. SBPs that could be represented as directed graphs with cycles. In addition, the existing works have not tackled the XOR-block pattern (i.e. XOR-Split, XOR-Join) in the optimization process. Furthemore, such work has not dealt with unstructured SBPs, and some of these studies [START_REF] Rekik | A linear program for optimal configurable business processes deployment into cloud federation[END_REF][START_REF] Halima | Optimal cost for time-aware cloud resource allocation in business process[END_REF] proposed exact solutions that can only solve for small SBPs. Moreover, the most important was that these works took as inputs the services that composed an SBP and the dependency relationship between these services and selected an optimal set of Cloud resources to host and execute these services while meeting resource and QoS constraints. In our case, the number of AMs and the dependency relationship between AMs and services are not known in advance. In fact, even though we consider an AM as a service, the existing works cannot be adapted to address our research needs. However, in this manuscript we propose solutions that deal with the different business process patterns (i.e. AND-blocks, OR-blocks, XOR-blocks and a repeat-loop) and can be applied to small and large SBPs as well as structured and unstructured SBPs.

Graph theory techniques

Besides the aforementioned approaches, there has been a lot of work on solving optimization problems based on graph theory techniques. In fact, graph coloring, graph partitioning and shortest and longest paths are among the most important and fundamental techniques that have been widely applied in the literature to find the solutions for real world problems in optimization, such as network design and computer science, and we can adopt/adapt them for solving the optimization problems that we tackle in this thesis. Broadly speaking, these problems belong to the class of NP-hard problems [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF], and generally only small problem sizes can be solved in acceptable times. Therefore, based on these problems, several heuristic approaches have been proposed to solve these various problems. Some of these studies are summarized in the following.

The graph coloring problem involves mapping a minimum number of colors to the vertices of a graph such that each two adjacent vertices, i.e two vertices connected with an edge, do not have the same color. Graph coloring has a wide range of applications, including task scheduling, resource allocation, and frequency assignment. In [START_REF] Ghribi | Exact and heuristic graph-coloring for energy efficient advance cloud resource reservation[END_REF], the authors proposed a new graph coloring model for resource reservation in Cloud datacenters with minimum datacenters energy consumption and maximum resource utilization (VMs). They introduced an ILP formulation to define the graph coloring optimization problem. They also suggested a near-optimal heuristic that would provide the efficient reservation of VMs in acceptable computational time even for large problem sizes. The main idea was to build a graph where vertices represented requested resources that would be associated (colored) to VMs, and links represented time overlap between these requested resources. It was noted that each VM represented a unique color in the graph coloring problem. With this representation, the VM reservation consisted in determining an optimal mapping between the requested resources and VMs.

In [59], the authors studied the problem of service deployment for efficient execution of SaaS applications in the Cloud. Among various QoS aspects of applications, they focused on the response time of applications. The authors proposed deployment strategies to determine the placement of services on VMs based on optimizing inter-task communication costs and parallelism. In order to reduce communication costs and increase parallelism simultaneously, two kinds of graphs, which represented two types of relationships among services, were proposed. The first one, namely the Service Dependency Graph (SDG), described the interdependence relationship between services, whereas the second one was the Service Concurrence Graph (SCG) where an edge between two vertices would indicate that the two corresponding services could run concurrently. To raise parallelism, the service deployment problem was transformed into a graph coloring problem for SCG where the number of colors represented the available VMs in order to deploy concurreny services onto different VMs for increasing the potential parallelism and thus improving the execution performance.

In [START_REF] Tsai | The on-line first-fit algorithm for radio frequency assignment problems[END_REF], the authors put forward an algorithm for the radio frequency assignment problem. The objective was to minimize the number of radio frequencies used by transmitters at different locations while avoiding interference. The problem was closely related to graph coloring where vertices represented transmitters and edges represented possible interferences.

Graph Partitioning is the problem of dividing a graph into a given number of subgraphs such that the number of edges connecting these sub-graphs is minimized. It has been widely used in many real life applications such as problems involving load balancing in distributed computing, parallel processing, and clustering in data mining. In [START_REF] Khalajzadeh | Cost-effective social network data placement and replication using graph-partitioning[END_REF], the authors addressed the problem of social network data placement and replication in Cloud datacentres with a minimum monetary cost while satisfying the latency requirement for users to access their own data and their friends' data in an acceptable time. They introduced a mathematical formulation to solve this optimization problem and proposed a graph-partitioning based algorithm that would divide a social graph of users into different connected partitions where the vertices represented social network users and the edges represented the list of friends for these users. The algorithm started with users with the biggest number of friends. These users and their friends were assigned to random partitions. Then for all unassigned users, it started with user's neighbours, and all their friends were assigned to the dominant partition between their neighbours. After that, for each partition, data items related to all users were placed in the nearest datacenter to the user who had the most number of friends in this partition. Data were replicated on multiple datacenters until the required latency was satisfied.

In [START_REF] Verbelen | Graph partitioning algorithms for optimizing software deployment in mobile cloud computing[END_REF], the authors addressed the problem of optimal deployment of software applications in the Cloud. They introduced an ILP formulation to define the problem and proposed a heuristic approach that was based on a graph partitioning algorithm. The algorithm would partition the components that composed a software application on a set of interconnected machines in the Cloud such that the communication cost between the components was minimized. The vertices of the graph represented components that made up a distributed software application, and the edges represented communication overhead between those components.

In [START_REF] Tanaka | Workflow scheduling to minimize data movement using multi-constraint graph partitioning[END_REF], the authors focused on the problem of workflows scheduling such that the communication cost was minimized. They proposed a graph partitioning approach to partition tasks that composed a workflow over a given number of computation nodes while minimizing inter-node communication.

Shortest and longest paths are the problems of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is, respectively, minimized and maximized. They are widely used in road navigation and network routing. In [START_REF] Abrishami | Cost-driven scheduling of grid workflows using partial critical paths[END_REF], the authors suggested an algorithm based on partial critical paths for workflow scheduling in utility grids. The objective of the proposed algorithm was to minimize the total workflow execution cost while satisfying a user-defined deadline. The algorithm consisted of two main phases: deadline distribution and planning. In the first phase, it tried to assign sub-deadlines to all tasks of the critical path of the workflow which was the longest execution path in the workflow [START_REF] Kwok | Static scheduling algorithms for allocating directed task graphs to multiprocessors[END_REF], such that it could complete before the user's deadline and its execution cost was minimized. Then it determined the partial critical path to each assigned task, and it recursively assigned sub-deadlines to the tasks of the partial critical paths. In the planning phase, the algorithm selected the cheapest service for each task while meeting its sub-deadline.

In [START_REF] Yu | Service selection algorithms for web services with end-to-end qos constraints[END_REF], the authors addressed the end-to-end QoS problem for composite complex BPs. The objective was to maximize the user benefits and minimize the cost while meeting the QoS needs. In fact, every service provider would offer many service levels for a service functionality. The authors put forward an approach that consisted in modeling the problem as a constrained shortest path problem, where vertices represented the service levels of services. If service i is connected to service j, then all service levels in i are connected to all service levels in j. The algorithm would connect all vertexes that had no incoming edges to a source node and all vertexes that had no outgoing edges to a destination node. For each edge, it added a cost, a benefit, and a delay. Then it determined the path with the highest utility between source and destination nodes based on the shortest path technique to select the most suitable services and service levels for clients and construct optimal BPs.

There are many other approaches to solve optimization problems based on graph theory techniques [START_REF] Mahmoudi | Modified cuckoo optimization algorithm (mcoa) to solve graph coloring problem[END_REF][START_REF] Likaj | Application of graph theory to find optimal paths for the transportation problem[END_REF][START_REF] Sun | Scheduling algorithm for workflow-based applications in optical grid[END_REF][START_REF] Jayasinghe | Improving performance and availability of services hosted on iaas clouds with structural constraint-aware virtual machine placement[END_REF][START_REF] Golab | Distributed data placement to minimize communication costs via graph partitioning[END_REF]. To the best of our knowledge, all the existing proposals have not dealt with the semantics of the nodes of a graph (e.g. XOR-Split, XOR-Join) in the optimization method. Moreover, unlike these studies, the number of AMs and the dependency relationship between AMs and services are not known in advance. However, in this manuscript we propose solutions that deal with the semantics of the different BP patterns.

Conclusion

In the first part of this chapter, we presented the basic concepts related to the thesis. We introduced Cloud Computing as the environment of our research. Afterwards, we defined the SOA and specified the type of applications that we target, namely SBPs. Next, we presented the autonomic computing concept as well as a brief background about optimization problems. In the second part of this chapter, we gave an overview of the existing works on autonomic computing, optimal Cloud resource allocation to SBPs and optimization based on graph theory, and we presented the difference between existing approaches and our approach.

We start presenting in detail our approaches in the next chapters. We will propose an approach for determining an appropriate number of AMs in SBPs (Chapter 3). In Chapter 4, we will propose an approach for determining an appropriate number of AMs components in timed SBPs. Thereafter, we will propose an approach that aims to optimally allocate Cloud resources to AMs for the management of SBPs in Chapter 5.

Chapter 3 Autonomic Managers Optimization in SBPs

Introduction

Executing SBPs in the Cloud requires autonomic management to cope with the dynamism and scalability of Cloud environments. It is obvious that using one centralized Autonomic Manager (AM) for the monitoring and adaptation of a large number of distributed services may cause a performance degradation and/or bottlenecks in the SBP management. It is also obvious that using one AM per service may result in a high management cost. Therefore, we aim in this chapter to find the optimal number of AMs for the management of SBPs in order to reduce the management cost while avoiding management bottlenecks. This chapter is organized as follows: First, we describe the problem of finding the minimum number of AMs for the management of SBPs while avoiding management bottlenecks, and we formulate it as an optimization model in Section 3.2. Then we present our defined algorithms, where SBPs can be represented as graphs with cycles (respectively without cycles) in Section 3.3 (respectively 3.4). Illustrative examples as well as experiments results are provided for both cases. Finally, we conclude the chapter in Section 3.5.

Problem Description and Formulation

In this section, we first show how to map an SBP to a directed graph, and we present some preliminary notions on business processes. Then we define the problem that we tackle in this chapter, followed by an Integer Linear Programming (ILP) formulation to solve it. Finally, we introduce the need for an approximate approach.

SBP Modeling

An SBP is a collection of related services, gateways and possibly events that accomplish a specific goal. Many graphical notations are available to model SBPs such as EPC [START_REF] Van Der Aalst | Yawl: yet another workflow language[END_REF], UML Activity Diagram [START_REF] Booch | Unified Modeling Language User Guide, The (2Nd Edition) (Addison-Wesley Object Technology Series[END_REF], and BPMN [START_REF] White | Introduction to bpmn[END_REF]. In this thesis, we try to abstract as much as possible from these specific notations. Therefore, as an SBP model can be mapped to a graph, we use graph theory to represent it as a directed graph called SBP graph according to the following definition, which is inspired from the BP graph definition given in [START_REF] Dijkman | Graph matching algorithms for business process model similarity search[END_REF].

Definition 3.2.1 (SBP graph). An SBP graph G = (V, E, I, τ, ID) is a directed graph where:

• V is the set of nodes. It represents the set of services, events, and gateways;

• E ⊆ V × V

is the set of edges that represents the data dependencies between

nodes, such that (v i , v j ) ∈ E if the output data of the node i is required for the execution of the node j;

• I ⊂ V is the set of initial nodes;

• τ : V ← T is a function that assigns, for each node v ∈ V , a type t ∈ T . T={service, start event, end event, gateway}, where gateway={AND, OR, XOR};

• ID : V ← N is a function that assigns, for each node v ∈ V , a unique identifier id ∈ N.
An SBP can be represented as a structured SBP that consists of a set of nodes and transitions between them. A node can be a service, AND-split, AND-join, OR-split, ORjoin, XOR-split, or XOR-join. In the following, we introduce the definition of a structured SBP. [START_REF] Kiepuszewski | On structured workflow modelling[END_REF] as follows:

Definition 3.2.2 (Structured SBP). A structured SBP is inductively defined in

• An SBP that consists of a single service is a structured SBP. This service is both initial and final.

• Let P 1 and P 2 be structured SBPs. Their concatenation is also a structured SBP, where the final node of P 1 has a transition to the initial node of P 2 . The initial and final nodes of this SBP are the initial and final nodes of P 1 and P 2 , respectively.

• Let P 1 ,...,P n be structured SBPs, s an AND-split (respectively OR-split, XOR-split), and f an AND-join (respectively OR-join, XOR-join). An SBP that has s as an initial node and f as a final node as well as transitions between s and the initial node of P i (i ∈ {1, 2, ..., n}) and between the final node of P i and f is also a structured SBP. The initial and final nodes of this structured SBP are s and f, respectively.

Problem Statement

Determining the optimal number of AMs for the management of a given SBP is a crucial issue. Figures 3.1a and 3.1b illustrate two naive approaches that represent two different extremes to this problem. In the first approach, a centralized AM is used to manage all the services that make up SBP [START_REF] De Oliveira | A framework for the coordination of multiple autonomic managers in cloud environments[END_REF]. This can lead to management bottlenecks and performance problems due to the large amount of data that can be periodically generated by multiple services at the same time and will be processed by a single AM. In the second approach, each SBP service is managed by its own AM [START_REF] Belhaj | Collaborative autonomic management of distributed component-based applications[END_REF]. Although this approach avoids management bottlenecks, it incurs high management costs in terms of number of used AMs. Therefore, it is interesting to minimize the number of AMs that will be used to manage SBPs while avoiding management bottlenecks.

The main question we ask is: How to reach a trade-off between these two extremes?

Problem Formulation

We start this section by introducing some assumptions and notations in order to facilitate the formulation. Possible management bottlenecks can be caused by the number of AMs, their placement, the communications between them either directly or through a common knowledge base, and other properties such as security and privacy mechanisms. We tackle in this chapter the optimization of the number of AMs to address bottlenecks of the management of SBPs. Without loss of generality, we assume that all AMs have the same requirements in terms of hardware resources (RAM, CPU, etc.), so that the optimization of their hosting cost is reduced to the optimization of their number.

Given an SBP graph, we denote by:

• S the set of services;

• M the set of candidate AMs that may be assigned to S (|M | = |S|, where |M | and |S| are, respectively, the cardinality of M and S). In fact, in the worst case, different AMs will be assigned to S;

• P the set of sets of services where an element of P is a pair of services that are at the same level in the SBP graph and their parent node is an AND/OR -Split. In order to determine P, we implement an algorithm with a polynomial time complexity that first determines the sets of services that belong to the same level in the graph, and then it checks for each pair of services that are at the same set whether their parent node is an AND/OR -Split. If it is the case, this pair is added to P.

Consider the example illustrated in Figure 3.1b, P={(Compute initial price, Choose shipper),(Compute retouch price, Compute shipper price)}.

Towards this end, the following decision variables are defined:

• x s m takes 1 if AM m ∈ M is assigned to service s ∈ S, and 0 otherwise;

• y m takes 1 if AM m ∈ M is used by at least one service, and 0 otherwise.

Given the above assumption and notations, our problem can be formulated in equations [3.1-3.6] where objective function 3.1 aims to minimize the number of AMs for the management of an SBP. Constraint 3.2 makes sure that each service is managed by only one AM all along the SBP life cycle. The authors in [75,[START_REF] Florio | Gru: An approach to introduce decentralized autonomic behavior in microservices architectures[END_REF] adopted the principle of using multiple AMs for the management of applications in order to avoid management bottlenecks, but they did not provide any means to optimize their number. In our work, an AM is able to manage a set of sequential services to reduce the amount of monitoring data that will be processed by each AM to prevent bottlenecks. Therefore, constraint 3.3 ensures that parallel services are managed by different AMs. Constraint 3.4 guarantees that if an AM is assigned to at least one service, then it is considered as used. Constraints 3.5 and 3.6 are the binary restrictions of the decision variables.

x i m + x j m <= 1 ∀m ∈ M, ∀(i, j) ∈ P (3.3) x s m <= y m ∀s ∈ S, ∀m ∈ M (3.4)
x s m ∈ {0, 1} ∀s ∈ S, ∀m ∈ M (3.5)

y m ∈ {0, 1} ∀m ∈ M (3.6)

Need for Approximate Approach

To realize whether it is reasonable or not to solve the above-mentioned optimization model and come up with an optimal solution every time we have a new application to deploy in a public Cloud, let us consider how many deployments of applications in a public Cloud there are and how long it takes to resolve this optimization problem.

In a public Cloud such as OpenShift [START_REF] Balakrishnan | 2.5m applications created, 1 billion requests per day, and more -new openshift online milestones[END_REF], there is a deployment of a new application every minute. In addition, according to new principles of application development, delivery, operation such as DevOps, and continuous delivery, for each application, there are multiple deployments per day. Furthermore, as we will show in the evaluation section (Section 3.4.3), the time needed to solve the optimization model using the CPLEX solver [START_REF] Ibm | IBM ILOG CPLEX Optimization Studio[END_REF] is not acceptable. It can exceed two hours, and whenever the number of services goes beyond 250, the solver will not find the optimal solution. In fact, a large SBP may comprise hundreds or thousands of services [START_REF] Reichert | Visualizing large business process models: Challenges, techniques, applications[END_REF][START_REF] Hipp | Enabling a user-friendly visualization of business process models[END_REF], so finding the optimal solution, in this context, is not possible. Consequently, to tackle this NP-hard problem [START_REF] Sahni | Computationally related problems[END_REF], we introduce in the following section our first approach that aims to find a near-optimal number of AMs for the management of SBPs in a polynomial time.

AMs Optimization in SBP Graphs with Cycles

In this section, we present our first proposal for determining the appropriate number of AMs that will be used by SBP services for their management (Section 3.3.1). An illustrative example of our approach is then provided (Section 3.3.2). Afterwards, we present the experiments that we perform to evaluate it (Section 3.3.3).

Proposed Approach

The approach is based on three algorithms called LowerBound, ServiceRelated-ParallelSets and AMsAssignement. Firstly, the LowerBound algorithm (cf. Algorithm 3.1) takes as inputs an SBP graph, and it aims at determining all the sets of services that can run in parallel. Secondly, the ServiceRelatedParallelSets algorithm (cf. Algorithm 3.2) takes as inputs the sets of parallel services, and it consists in determining, for each service, the set of services that can run in parallel with it. Thirdly, the AMsAssignement algorithm (cf. Algorithm 3.3) takes as inputs the set of services that can run in parallel with each service. It aims at assigning AMs to the SBP services while fulfilling the constraints given in equations 3.2 and 3.3.

To sum up, the proposed approach operates in three successive steps:

1. Determination of all sets of parallel services, 2. Construction of all sets of related services, 3. Assignment of AMs to the SBP services.

Determination of all sets of parallel services

Step 1 is implemented using the LowerBound algorithm. It starts by initializing the current set of parallel services with the initial services of the SBP graph and the lower bound number with the number of elements of the current set (cf. lines 1-2). The current set is added to the resulting sets of parallel services (cf. line 3). The algorithm iterates until determining all the sets of parallel services (cf. line 4 and line 15). To do so, the elements of the current set are assigned to the previous set, and the current set is initialized to the empty set (cf. lines 5-6). Next, it iterates over the set of immediate successors of the previous parallel services (cf. lines 7-8). For each node, whether its type is either an AND/OR -Join and all its predecessors have completed their execution or not an AND/OR -Join, LowerBound continues to explore the successors of the candidate node seeking a node of service type, and then the latter is added to the new set of services that can run in parallel (cf. lines 9-10). The algorithm checks whether the current set has not been determined in a previous iteration yet (cf. line 11). If it is the case, this set is added to the resulting sets of parallel services (cf. line 12), and the lower bound number of AMs is possibly updated (cf. lines [START_REF] Papazoglou | Blueprinting the cloud[END_REF][START_REF] White | Introduction to bpmn[END_REF]. This number is equal to the maximum number of services that can run in parallel. LowerBound terminates when either the current set of services is empty or it is a subset of an existing set (cf. line 15).

(v i ,v j ) ∈ E do 9 if (τ (v j ) / ∈ {AND-Join, OR-Join}) or (τ (v j ) ∈ {AND-

Construction of all sets of related services

Step 2 is implemented using the ServiceRelatedParallelSets algorithm. It starts by determining the nodes of service type in the SBP graph (cf. line 2). After that, for each service (cf. lines 3-4), its corresponding set is initialized to the empty set (cf. line 5). The algorithm iterates over the sets of parallel services (cf. line 6), and if the current service belongs to the current set (cf. line 7), that is it can be run in parallel with the services belonging to the current set, then these services are added to its set of related services (cf. line 8).

Assignment of AMs to SBP services

Step 3 is implemented using the AMsAssignement algorithm. The algorithm starts by initializing the AM number that will be assigned to each service and the number of AMs to 0 (cf. lines 1-2). After that, the elements of ServiceRelatedParallelSets are sorted in decreasing order according to their cardinality to promote services with maximal number of services that can run in parallel with them (cf. line 3). Then for each service s (cf. line 5), the algorithm tries to assign an AM to it that fulfills the constraints given in equations 3.2 and 3.3 (cf. lines 6-12). To do so, it starts with the first AM (cf. line 6) and checks whether this AM might be assigned to s (cf. line 8); i.e., this AM has not been assigned to any service that can run in parallel with s yet. If it is the case, the current AM is assigned to s (cf. line 9). Otherwise, the algorithm just updates the current AM (cf. lines [START_REF] Mell | Sp 800-145. the nist definition of cloud computing[END_REF][START_REF] Wu | Sla-based resource provisioning for hosted software-as-a-service applications in cloud computing environments[END_REF]. This step is repeated until an AM is assigned to the current service (cf. According to the constraint given in equation 3.3, we assume that if the number of AMs provided by the AMsAssignement algorithm is equal to the lower bound number of AMs provided by the LowerBound algorithm, then the former number is optimal.

Theoretical complexity

Our proposed approach consists of three main steps: The first one consists in determining all the sets of parallel services (Algorithm 3.1). The worst case time complexity of this step is bounded by O(n 4 × 2 n ), where n is the number of services that compose a given SBP. Thus, the number of iterations of the while loop is bounded by O(2 n ), and the time complexity of an iteration is bounded by O(n 4 ). In fact, the number of sets of services that can run in parallel is not large. Therefore, we do not face the problem of determining all the possible combinations of services, where its time complexity is

O(n 4 × 2 n ).
The second step is to determine all the sets of related services (Algorithm 3.2). The worst case time complexity of this step is bounded by O(n × m), where n is the number of services, and m is the number of sets of parallel services.

The third step aims to assign AMs to the SBP services (Algorithm 3.3). The worst case time complexity of this step is bounded by O(n × log(n) + n 2 ) O(n 2 ), where n is the number of services. We choose the QuickSort algorithm to sort ServiceRelated-ParallelSets. This algorithm has a complexity of O(n × log(n)).

Hence, the overall time complexity of the approach is: O(n 4 × 2 n ).

Illustrative Example

Herein, we present an example illustrating how the proposed algorithms work. Let us consider the example depicted in Figure 3.2 that represents an SBP graph with a cycle. The LowerBound algorithm comes to an end after five iterations and checking that all the sets of parallel services are determined. Thus, it yields the following output:

• ParallelSets = {{S1, S2}, {S3, S4}, {S5, S3}, {S1, S5}, {S3, S1}} • lbn = 2
After that, ServiceRelatedParallelSets starts by determining the set of services that can run in parallel with S1. This set is the union of the sets of parallel services that contain S1, and it is equal to {S2, S5, S3}. In the second iteration, the set of services that can run in parallel with S2 is determined, which is {S1}. During iteration 3, iteration 4 and iteration 5, respectively, the set of services that can run in parallel with S3, S4 and S5 is determined: {S4, S5, S1}, {S3} and {S3, S1}. The ServiceRelat-edParallelSets algorithm yields the following output:

< 1, {S2, S5, S3} > < 2, {S1} > < 3, {S4, S5, S1} > < 4, {S3} > < 5, {S3, S1} >
Next, AMsAssignement sorts the elements of the above array in a decreasing order according to their cardinality: < 1, {S2, S5, S3} >, < 3, {S4, S5, S1} >, < 5, {S3, S1} >, < 2, {S1} >, < 4, {S3} >. In the first iteration, AM number 1, i.e. AM1, is assigned to S1. In the second iteration, since the service S3 can run in parallel with S1 as shown in the above table, AM1 can not be assigned to S3. In this case, AM2 is dedicated to S3. In the third iteration, the algorithm tries to assign AM1 and then AM2 to S5. These AMs can not be assigned to S5 because S5 can run in parallel with S1 and S3, and AM 1 and AM 2 have been already assigned to these services. Thus, AM3 is assigned to S5. AMsAssignement proceeds in the same manner to determine the AM that will be assigned to services S2 and S4. After 3 iterations, the algorithm comes to the end and returns the following results:

Services S1 S3 S5 S2 S4 AM number 1 2 3 2 1
nbAM s = 3

Performance Evaluation

In this section, we present a series of performance evaluations of our proposed approach in terms of execution time and quality of the provided solutions based on the closeness between these solutions and the lower bound numbers of AMs outputted by the LowerBound algorithm. The first part is the experimental results conducted on two real datasets, and the second part is the performance results of experiments conducted on a dataset based on randomly generated graphs to push further experiments in order to generalize the performance results. All experiments are carried out on an Intel Core i5 PC with 2.53 GHz and 4GB of RAM. All the results are average values across 10 independent runs.

To the best of our knowledge, none of the existing works has explicitly focused on the determination of the optimal number of AMs for the management of SBPs in the Cloud (see Chapter 2 for more details). Therefore, we do not make comparisons with existing work here.

Experiments on public real datasets

We present in the following the performance results of experiments conducted on two public datasets of real business processes which are presented in an XML format. Each XML file stores the data of an SBP including services names and gateways (parallel, inclusive, and exclusive gateways), and the sequence flows between SBP elements.

• Dataset 1 consists of 560 BPMN process models shared by the IBM Business Integration Technologies (BIT) team [START_REF] Fahland | Analysis on demand: Instantaneous soundness checking of industrial business process models[END_REF]. At most, there are 195 services, 139 gateways, and 326 edges in a process (Table 3 At this level, we recall our assumption that considers that if the number of AMs provided by the AMsAssignement algorithm is equal to the lower bound number of AMs provided by the LowerBound algorithm, the latter number is optimal. According to this assumption, our approach provides optimal solutions for all the considered real SBPs (Figure 3.3) in a reasonable time that does not exceed 0.1 second (Figure 3.10a).

Experiments on randomly generated dataset

SBPs are generally modeled as sparse graphs where nodes indicate services to invoke and gateways and directed edges represent dependencies between nodes. In order to consider a realistic dataset, we generate different connected SBP graphs with 10-100 services, in increments of 10, and a number of edges ranging from n -1 to 3.2 × (n -1) (i.e. 320% of (n -1)), in increments of 0.2, where n is the order of the graph. Indeed, we do not generate graphs with more edges since whenever the number of edges goes beyond 2.4 × (n -1), the lower bound number of AMs is equal to n. Thus, the number of AMs that will be used by n SBP services is equal to n. Therefore, in our experiment, for each graph of order n, we consider 12 densities (from 100% of (n -1) to 320% of (n -1)).

As shown in Figure 3.4, when the number of edges of an SBP graph of order n goes beyond 2.4 * (n -1), the lower bound number of AMs is equal to n. For this reason, we limit our evaluation of the quality of the results provided by the AMsAssignement algorithm to graphs with n -1 -2.4 × (n -1) edges. Although the time complexity of the proposed approach is exponential (in fact, it is equal to O(|P arallelSets|) that is bounded by O(2 n )), where n is the number of SBP services, the approach is useful in practice because the number of sets of services that can run in parallel (|P arallelSets|) is usually far less than the number of sets under consideration. The results depicted in Figure 3.5 show that the experimental variations of |P arallelSets| versus the number of services are linear with a low slope. For example, for SBP graphs with 50 services, the number of sets of parallel services does not exceed 23. We note that the execution time of the approach is very small and does not exceed 0.24 second. Based on our assumption, our algorithm outputs optimal solutions for 94% instances of the randomly generated graphs and near-optimal solutions for the remaining instances (6% of the considered graphs). As depicted in Figure 3.6, the difference between the optimal solution and the solution provided by our algorithm does not exceed 6 AMs, where for 49% of them, the difference is equal to one AM. It is interesting to note, as it is shown in Figure 3.2, that the optimal number of AMs for the management of an SBP may be greater than the lower bound number of AMs, which means that our approach solves more than 94% of the considered graphs to optimality.

Services Number Parallel sets Number

AMs Optimization in SBP Graphs Without Cycles

In this section, we present our second attempt that aims to determine the appropriate number of AMs for the management of large SBPs. In this proposal we focus on large SBPs that can be modeled as Directed Acyclic Graphs (DAGs), since a large percentage of SBPs are usually expressed as DAGs. Our first proposal introduced in the above section deals with the different types of gateways (e.g. AND, OR, XOR) in the same way; i.e., the outgoing services of each gateway are always considered as parallel services even for alternative services, which are the outgoing services of a XOR-split gateway. This proposal is not effective when the given SBP graph contains XOR-split gateways. Because of this, we suggest a second proposal that attempts to further reduce the number of AMs by focusing on XOR-split gateways. We first introduce our proposed approach (Section 3.4.1). We then present an illustrative example of how it works (Section 3.4.2). Thereafter, we introduce the experiments that we perform to evaluate our second proposal (Section 3.4.3).

Proposed Approach

Our second approach is based on two algorithms called Compaction and AMsAssignement. The Compaction algorithm, whose pseudo-code is given in Algorithm 3.4 takes as input an SBP graph and outputs a compact graph. It mainly aims to (i) merge the outgoing paths of each XOR-Split gateway into a single path in order to assign only one AM to alternative services, and (ii) remove all gateways, regardless of their types, to avoid assigning AMs to them. The AMsAssignement algorithm, whose pseudo-code is given in Algorithm 3.5, has as an input a compact graph and outputs the AM assigned to each service. It aims to assign AMs to the SBP services while fulfilling the constraints given in equations 3.2 and 3.3.

Compaction Algorithm

The Compaction algorithm operates in two successive steps: Step 1 is to determine the set of nodes of the compact graph (cf. lines 1-31).

Step 2 is to discover the dependency relationships between these nodes (cf. lines 32-39).

It starts by initializing the nodes, the initial nodes, and the edges sets of the output graph G 1 denoted, respectively, by V 1 , I 1 , and E 1 to the empty set and the current set CurrSet to the set of initial nodes of the input graph G (cf. lines 1-2). CurrSet is a set of meta-nodes where each meta-node consists of a set of alternative services; i.e., only one of these services will be executed all along the SBP life cycle. In the first step, Compaction iterates until all the nodes of G 1 are determined (cf. line 3). To do so, it checks whether all the candidate meta-nodes that belong to CurrSet consist of only nodes of service type in order to remove all gateways, regardless of their types (cf. lines 4-6). If it is the case, these meta-nodes are added to V 1 (cf. lines 28-30), and the successors of each one are merged into a single meta-node which is added to the new CurrSet (cf. line 31). Otherwise, there is at least one candidate meta-node that contains gateways (cf. lines 6-27). In this case, the algorithm goes through the set of nodes that composes the candidate meta-node in order to remove gateways from it (cf. line 7). If the current node is an AND/OR -Split (cf. lines [START_REF] De Oliveira | A framework for the coordination of multiple autonomic managers in cloud environments[END_REF][START_REF] Adler | Four steps to achieving high availability in the cloud[END_REF][START_REF] Mell | Sp 800-145. the nist definition of cloud computing[END_REF][START_REF] Wu | Sla-based resource provisioning for hosted software-as-a-service applications in cloud computing environments[END_REF][START_REF] Enterprise | Cloud Computing Survey[END_REF][START_REF] Papazoglou | Blueprinting the cloud[END_REF][START_REF] White | Introduction to bpmn[END_REF][START_REF] Booch | Unified Modeling Language User Guide, The (2Nd Edition) (Addison-Wesley Object Technology Series[END_REF][START_REF] Florio | Gru: An approach to introduce decentralized autonomic behavior in microservices architectures[END_REF][START_REF] Hoenisch | Cost-efficient scheduling of elastic processes in hybrid clouds[END_REF], in fulfillment of the constraint given in equation 3.3, different AMs should be assigned to the successors of this node. To do so, these nodes are added to different meta-nodes in CurrSet (cf. lines 11-15), and, if necessary, a new meta-node is added to CurrSet to make sure that parallel services belong to different meta-nodes (cf. lines [START_REF] Florio | Gru: An approach to introduce decentralized autonomic behavior in microservices architectures[END_REF][START_REF] Hoenisch | Cost-efficient scheduling of elastic processes in hybrid clouds[END_REF]. Otherwise, the type of the gateway is not an And/Or -Split (cf. lines 18-27), so only one of its successors will be executed, and then one AM is sufficient to manage them. The algorithm checks whether all its predecessors have completed their execution (cf. line 21). If it is the case, it merges all the successors of the current gateway into the current meta-node (cf. line 22). Otherwise, since the gateway will be removed (cf. line 20), it looks to merge the current meta-node with another one (cf. lines 24-27).

After determining the set of meta-nodes V 1 of the compact graph, Compaction looks for determining the dependency relationships between these meta-nodes (cf. lines 32-39). For each meta-node u (cf. line 32), it checks whether all the nodes constituting this meta-node belong to the set of initial nodes of G. If so, u is added to the set of initial nodes I 1 (cf. lines [START_REF] Belhaj | Self-adaptive decision making for the management of component-based applications[END_REF][START_REF] Mola | Collaborative policy-based autonomic management: In a hierarchical model[END_REF]. Otherwise, the algorithm determines the predecessors of the nodes constituting u (cf. lines [START_REF] Ionescu | A Robust Autonomic Computing Architecture for Server Virtualization[END_REF][START_REF] Baker | Towards Autonomic Cloud Services Engineering via Intention Workflow Model[END_REF][START_REF] Frey | Towards a generic architecture and methodology for multi-goal, highly-distributed and dynamic autonomic systems[END_REF] and the edge connecting u, and each meta-node consisting of at least one of these predecessors is added to E 1 (cf. line 39).

AMsAssignement Algorithm

At first, the AMsAssignement algorithm initializes the AM number that will be assigned to each service and the number of AMs to 0 (cf. lines 1-2). After that, it tries to assign AMs to the SBP services that fulfill the constraints given in equations 3.2 and 3.3 (cf. lines 3-20). It starts with the initial nodes of the compact graph where different AMs are assigned to these nodes (cf. lines 3-5). Then the current set of parallel services is initialized to the graph's initial nodes (cf. line 6). The algorithm iterates until all the services have AMs assigned to them (cf. line 7). To do so, it looks for the successors of the current parallel services, and for each service, it checks whether all its predecessors have completed their execution (cf. lines [START_REF] De Oliveira | A framework for the coordination of multiple autonomic managers in cloud environments[END_REF][START_REF] Adler | Four steps to achieving high availability in the cloud[END_REF][START_REF] Mell | Sp 800-145. the nist definition of cloud computing[END_REF][START_REF] Wu | Sla-based resource provisioning for hosted software-as-a-service applications in cloud computing environments[END_REF]. If it is the case, this service is added to the set of next parallel services (cf. line 12), and if the AM assigned to its predecessor service is not used by another services that can run in parallel with it (cf. line 13), then this AM is assigned to it in order to assign the same AM to sequential services (cf. line 14). Otherwise, the algorithm updates the current AM with an AM that is not already assigned to any service that can run in parallel with the current service. This AM is then assigned to it (cf. lines [START_REF] Booch | Unified Modeling Language User Guide, The (2Nd Edition) (Addison-Wesley Object Technology Series[END_REF][START_REF] Florio | Gru: An approach to introduce decentralized autonomic behavior in microservices architectures[END_REF][START_REF] Hoenisch | Cost-efficient scheduling of elastic processes in hybrid clouds[END_REF]. The total number of AMs needed to manage the SBP is possibly updated (cf. lines 18-19).

Theoretical complexity

Our proposed approach consists of two algorithms. The first one aims to compact an SBP graph by merging the outgoing paths of each XOR-Split gateway into a single path and removing all gateways, regardless of their types (Algorithm 3.4). It consists of two main steps. The first step is to determine the set of nodes of the compact graph. The worst case time complexity of this step is bounded by O(m 6 ), where m is the number of nodes in the graph. The second step is to determine the dependency relationships between the resulting nodes. The worst case time complexity of this step is bounded by O(n 3 ), where n is the number of services. The second algorithm aims to assign AMs to the SBP services (Algorithm 3.5). Its worst case time complexity is bounded by O(n 4 ), where n is the number of services.

Therefore, the overall time complexity of the approach is: O(m 6 + n 3 + n 4 ) O(m 6 ).

Illustrative Example

Herein, we present an example illustrating how the proposed algorithms work. Let us consider the example depicted in Figure 3.7 that represents an SBP composed of ten services (see Figure 3.7 (left)).

Based on the characteristics of SBPs, we assume that an SBP is split into levels that can be executed sequentially, and services belonging to a level are independent from each other. The compact graph is in fact an intermediary graph, which is used only to determine the appropriate number of AMs. It consists of a set of meta-nodes where a meta-node is a group of alternative services. The relationship between levels of services

] = AM s[ID of s i ]) then AM s[ID of s j ] ← AM s[ID of s i ]; else currentAM ← GetAM(s j ); AM s[ID of s j ] ← currentAM ; if nbAM s < currentAM then nbAM s ← currentAM ; CurrentP arallelSet ← N extP arallelSet;
is kept in this graph. Level 1 contains the initial nodes of the input graph G. Level L + 1 contains the successors of the services of level L. Hence, the dependencies in this graph do not reflect the execution dependencies between individual services, but rather the dependencies between levels. In the first step, Compaction initializes CurrSet to the set of the initial nodes of the input graph CurrSet={{XOR-split1}}. The while loop iterates over CurrSet until the latter is empty. The first iteration considers the meta-node {XOR-split1 }. This metanode does not consist only of nodes of service type. In this case, the algorithm goes through these nodes; and for each one, in case it is not a service, this node is replaced by its successors if and only if, the predecessors of these nodes have been processed earlier. XOR-split1 is replaced by its successors, i.e. CurrSet={{AND-split1, AND-split2}}.

AND-Split2

S1

The second iteration considers the meta-node {{AND-split1, AND-split2 }}. The node AND-split1 is replaced by its successors S1 and S2 because S1 and S2 can run in parallel. These nodes are added to two different meta-nodes, i.e. CurrSet={{S1, AND-split2},{S2}}.

The third iteration considers the meta-node {S1, AND-split2 }. The node AND-split2 is replaced by its successors: S3, S4, and S5, which are added to different meta-nodes, i.e. CurrSet={{S1,S3},{S2,S4},{S5}}. All the meta-nodes in CurrSet consist of only nodes of service type. These meta-nodes are added to the set of nodes of the compact graph, i.e. V 1 ={{S1,S3},{S2,S4},{S5}}; and the successors of each meta-node are merged into a meta-node that is added to the new CurrSet: CurrSet={{AND-join1,S7},{S6,S8},{S9}}.

The fourth iteration considers the meta-node {AND-join1, S7 }. The node AND-join1 is removed form this meta-node because its predecessor S10 has not been processed yet, CurrSet={{S7},{S6,S8},{S9}}. All the meta-nodes in CurrSet consist of only nodes of service type. These meta-nodes are added to V 1 and the successors of each one are merged into a meta-node that is added to the new CurrSet: CurrSet={{AND-join2},{S10,AND-join2}}.

The same process is applied to the current set {{AND-join2 },{S10,AND-join2 }}. The meta-node {S10} is added to V 1 , and the algorithm comes to an end as CurrSet = ∅ To conclude the first step, the resulting set of the nodes of the compact graph is V 1 ={{S1,S3},{S2,S4},{S5},{S7},{S6,S8},{S9},{S10}}.

In the second step, Compaction iterates over the set of resulting meta-nodes V 1 to determine the dependency relationships between them. The first iteration considers the meta-node {S1,S3 }. Since S1 and S3 are initial nodes in the input graph (Figure 3.7 (left)), this meta-node is added to the set of initial nodes of the compact graph I 1 . The same process is applied to the meta-nodes {S2,S4 } and {S5 } that are then added to I 1 .

The next iteration considers the meta-node {S7 }. S3 is a predecessor of it, then an edge connecting the meta-node {S7 } and the meta-node that contains S3 is added to the set of the edges of the compact graph E 1 , i.e. E 1 ={({S1,S3 },{S7 })}. Similarly, the rest of the edges are determined. Therefore, we get the following set of results: E 1 ={({S1,S3},{S7}),({S2,S4},{S6,S8}),({S5},{S9}), ({S6,S8},{S10})}. I 1 ={{S1,S3},{S2,S4},{S5}}.

Applying the AMsAssignement algorithm on the compact graph, three AMs are needed for the management of the given SBP. The first AM is assigned to the services S1, S3, and S7. The second AM is assigned to the services S2, S4, S6, S8, and S10, while the third one is assigned to the services S5 and S9.

Applying our approach on the SBP graph example depicted in Figure 3.8 (left), two AMs are enough for managing SBP. The first AM is dedicated to managing the services S1, S2, S6, and S10, while the second AM is assigned to the services S3, S4, S5, S7, S8, and S9.

Performance Evaluation

This section presents a series of performance evaluations of our second proposed approach in terms of execution time and quality of the provided solutions. In order to show the efficiency of this approach, we compare it to our first approach presented in Section 3.3 to verify how it enhances the AMs optimization process for the management of large SBPs. We also compare the solution provided by this approach to the solution obtained by solving the optimization model presented in Section 3.2.3 using the CPLEX solver [START_REF] Ibm | IBM ILOG CPLEX Optimization Studio[END_REF] when such a solution is possible. Let us denote by:

• S a the solution provided by our second proposed approach;

• S * the optimal solution provided by CPLEX;

• G the gap between S a and S * (in %). Note that if G = 0%, it means that S a is optimal. G is defined as follows:

G = S a -S * S * × 100
The first part of the series of performance evaluations is the experimental results conducted on two real datasets (Section 3.4.3.1), and the second part is the performance results of experiments conducted on a realistic dataset based on randomly generated graphs (Section 3.4.3.2). It is worth mentioning that, to the extent of our knowledge, there is no available public dataset of large business process models. Thus, to perform experiments on large SBPs, we generate a dataset of random large SBPs. All the results are average values across 10 independent runs.

The different experiments are carried out on an Intel Core i7 PC with 2.70 GHz and 8GB of RAM. We use the commercial CPLEX solver 12.6 to solve the ILP formulation (Section 3.2.3).

Experiments on public real datasets

Herein, we present the performance results of experiments conducted on IBM and SAP datasets (see Section 3.3.3.1 for more datasets details). In this proposal we focus on SBPs that can be modeled as DAGs. In fact, 85% of the IBM dataset and 94% of the SAP dataset are SBPs that can be represented as DAGs.

Experiment results on real datasets, depicted in Figure 3.9 show, our second proposal compared to the first one. It can be seen that the second proposal outperforms our first one in terms of reducing the number of AMs for the management of SBPs. It reduces this number by 18% and 7% for for IBM and SAP datasets, respectively. On the other hand, it can always find the optimal solution for the SBP models in IBM and SAP datasets in a short time, which does not generally exceed 0.06 second, as depicted in Figure 3.10. The results on real datasets show that our second proposal has good performance in terms of both quality and execution time. It provides the optimal solution for all the considered SBPs in few milliseconds. In the following, we perform experiments on randomly generated small and large graphs. On the one hand, we highlight that our generated dataset behaves the same way as real datasets. On the other hand, we evaluate our approach on large SBPs, which is our main goal here.

Experiments on randomly generated dataset

In order to evaluate the performance of the proposed approach on large SBPs, we implement a generator of random structured SBPs. The generation of these SBP graphs is based on Definition 3.2.2. Note that structured processes represent a class of business processes widely used in industry and academia [START_REF] Kiepuszewski | On structured workflow modelling[END_REF]. We generate SBP graphs with two different sizes (small, large), with a number of services varying, respectively, from 10 to 100, in increments of 10, and from 150 to 600, in increments of 50. These graphs are sparse because SBP graphs are generally sparse (see IBM and SAP dataset details in Tables 3.1 and 3.2). The characteristics of the considered SBP graphs are reported in Table 3.3, where the nodes include both services and gateways (AND-split, AND-join, OR-split, OR-join, XOR-split, and XOR-join).

Experiment results on the randomly generated dataset are illustrated in Figure 3.11. Compared to the first approach, it can be seen that our second proposal outperforms the first one in terms of reducing the number of AMs. It decreases this number by 41%. On the other hand, it is able to find the optimal solution for 99% of the considered SBPs. We note that the gap between our approximate solution provided by the second proposal and the optimal solution is very small and does not exceed 0.75%. It means that our solution is very close to the optimal solution. As for the execution time of our second proposal, the results presented in Figure 3.12 show that its execution time remains reasonable even for large SBPs. In fact, it does not exceed 12 seconds, whereas the CPLEX solver takes more than 2 hours to solve the problem; and whenever the number of services goes beyond 250, the solver can not find the optimal solution due to a problem of memory. Experiment results on the randomly generated dataset show that our second proposal has good performance in terms of both quality and execution time. It returns an optimal solution for more than 99% of the considered small and large SBPs in a reasonable time. Although these series of experiments are performed on a randomly generated dataset, we advocate that this dataset is realistic. For small SBP graphs, it behaves the same way as IBM and SAP real datasets, as shown in Figures 3.10 and 3.12a. Therefore, based on the generated dataset, we can conclude that the computational time of CPLEX increases quickly with the number of SBP services (Figure 3.12c). In fact, considering the example of the public Cloud OpenShift where there are few deployments of a new application every minute, we cannot use the CPLEX solver to determine the optimal number of AMs because it can take more than two hours to solve the model. However, we can apply our approaches that come up with near-optimal solutions in an acceptable time, which is of the order of a few milliseconds for small SBP graphs, and it does not exceed 12 seconds for large graphs.

The First Proposal The Second Proposal

To sum up, our two proposals are complementary; and based on them, we cover all types of SBPs, i.e. small and large SBPs that are represented as graphs with or without cycles. The second proposal is better than the first one for both small and large SBPs expressed as DAGs. Thus, if the given SBP graph contains cycles, we use our first proposal for determining the appropriate number of AMs that will be used by services for their management; otherwise, the second proposal will be the most appropriate and effective method to solve the problem.

Conclusion

In this chapter, we focused on the optimization of the number of AMs in SBPs while avoiding management bottlenecks. We formally represented SBPs as graphs that allow us to preserve the semantics of business processes. Then we proposed an ILP formulation to solve this problem. Since solving the ILP formulation is time-consuming for large SBPs, we also proposed two different approaches for SBPs that are represented as graphs, respectively with and without cycles. Their main idea is to manage parallel services with different AMs in order to reduce the number of allocated AMs and avoid management bottlenecks. An illustrative example of how each approach works was given. Experiment results showed that our proposals obtain very encouraging results.

After facing the challenges of optimizing the number of AMs for the management of SBPs, since an AM consists of four basic components (monitor, analyzer, planner, and executor), we were motivated to extend our work to break down the AM into its main components. We are interested in optimizing the number of monitors, analyzers, planners, and executors separately. Hence, in the next chapter, we will focus on how to formulate this problem and solve it in a polynomial time.

Introduction

Executing SBPs in the Cloud requires autonomic management to cope with the dynamism and scalability of Cloud environments. In the previous chapter, we proposed an approach that aims to determine the appropriate number of AMs for the management of SBPs 51 such that this number is minimized while avoiding management bottlenecks. Since an AM consists of four basic components: a monitor, an analyzer, a planner, and an executor, which are not used with the same frequency. Thus, to go beyond the boundaries of an AM that is seen as a single resource, we propose in this chapter a new approach that consists in determining the appropriate number of monitors, analyzers, planners, and executors for the management of timed SBPs to further reduce the management costs.

This chapter is organized as follows: Preliminaries on the four basic components of an AM are firstly introduced in Section 4.2. Then we describe the problem that we tackle in this chapter, and we suggest an ILP formulation to solve it in Section 4.3. Our proposed approach as well as an illustrative example of how it works are presented, respectively, in Sections 4.4 and 4.5. Finally, the experimental results are detailed in Section 4.6. Autonomic management resource for Cloud resources is depicted in Figure 4.1. In this autonomic loop, the managed element represents any hardware or software Cloud resource for which we want to endow an autonomous behavior. A shared knowledge is essential to maintain data of the managed resource, adaptation goals, and other information needed by the AM components. The different components of an AM are defined as:

Preliminaries: Monitor, Analyzer, Planner, Executor

1. The Monitor is used to periodically gather monitoring data from the managed resource;

2. The Analyzer is in charge of periodically analyzing monitoring data and checking whether an adaptation is required. If so, it sends an alert (as an event) to the planner;

3. The Planner is responsible for producing adaptation plans. An adaptation plan represents a workflow of elementary adaptation actions described in the knowledge base, which are needed to achieve the resource goals;

4. The Executor is responsible for carrying out the adaptation actions provided by the planner over the managed resource.

Problem Description and Formulation

In this section, we first show how to map a timed SBP to a directed graph. After that, we define the research problem that we tackle in this chapter. We then introduce the notations that are used throughout the problem formulation as well as the assumptions.

Finally, we give an ILP formulation to solve the problem.

Problem Description

Managing SBPs in the Cloud involves using AMs to cope with the dynamism of Cloud environments. In fact, an AM consists of four basic components which are the monitor, the analyzer, the planner, and the executor that are not used with the same frequency. For example, the monitor is used much more frequently than the executor. Then we can imagine that assigning the same monitor to services that can run in parallel may lead to management bottlenecks, but this is not necessarily the case for the executor. Thus, we can share a component between different parallel services in order to further reduce the management costs while ensuring that each component is assigned to only one SBP service at a time. Consequently, to go beyond the boundaries of an AM that is seen as a single resource, it is interesting to minimize the number of monitors, analyzers, planners and executors separately while avoiding management bottlenecks.

In fact, the authors in [75,[START_REF] Florio | Gru: An approach to introduce decentralized autonomic behavior in microservices architectures[END_REF] adopted the principle of using multiple AMs for the management of applications to avoid management bottlenecks, but they did not provide any means to optimize their number. In our work, an AM component is able to manage a set of services, while it is assigned to only one service at a time to reduce the amount of monitoring data that will be processed by each AM to prevent bottlenecks. To this end, it is essential to determine all sets of services that can run in parallel.

In order to determine the optimal number of monitors that will be used by the SBP services for their management, we are required to know the monitoring time and frequency for each service to figure out the set of time stamps at which we can monitor each service in an attempt to share a monitor between different parallel services while ensuring that this monitor is used by only one service at a time. While the determination of the optimal number of analyzers requires us to know the set of time stamps at which we can analyze each service by means of the analysis time for each event that will happen for a service and the analysis frequency for each service as well as the probability that a problem will happen for a service. Moreover, in order to find the optimal number of planners, it is essential to know the probability that an action will be chosen for a service and the planning time for each action for a service. Furthermore, we need to know the execution time that is taken by an executor to carry out each adaptation action over each service in order to determine the optimal number of executors.

In order to do all of that, it is essential to know an estimate of the execution time of each service as well as an estimate of the data transfer time between services. For that, we opt for timed SBPs. In this work, we assume that there is maximum Quality of Service (QoS) degradation time that a timed SBP can not exceed.

Timed SBP Modeling

As the structure of a timed SBP can be mapped to a graph, we choose graph theory to represent such SBP as a directed graph called the timed SBP graph according to the following definition. G = (V,E,I,τ,ε,δ,ι) is a directed graph where:

Definition 4.3.1 (Timed SBP graph). A timed SBP graph

• V is the set of nodes;

• E ⊆ V ×V is the set of edges that represents the data dependencies between nodes, such that (v i , v j ) ∈ E if the output data of node i is required for the execution of node j;

• I ⊂ V is the set of initial nodes;

• τ : V ← Γ is a function that maps nodes to their types;

• ε : V ← N is a function that assigns, for each service v ∈ V , where τ (v) = service, an estimated execution time;

• δ : V × V ← N is a function that assigns, for each pair of services, an estimated data transfer time between them;

• ι : V ← N is a function that maps each node v ∈ V to a unique identifier id ∈ N.

Notations and Assumptions

Let S be the set of services that make up a timed SBP and P S the sets of parallel services. Let M , A, P and E respectively represent the set of candidate monitors, analyzers, planners and executors that may be assigned to S. Each set has as cardinality the number of services, i.e. |S|, since in the worst case different monitors, analyzers, planners and executors will be assigned to the autonomic management of services. Let mt s be the monitoring time for service s ∈ S. It is equal to the sum of the time taken by a monitor to collect monitoring data from s and the time needed to save data in the knowledge base and the time needed to send an event to an analyzer component. Let mf s be the monitoring frequency for service s (e.g. monitor each 5 ms) and I s the set of time stamps at which we can monitor it, where the step size between each element in I s and the next element is equal to mf s .

We define Ev s as the set of events that could result from the analysis of the monitoring data collected from service s. It contains the event 'no problem found' in addition to all the predefined problems that could happen. Let at evs be the analysis time for event ev ∈ Ev s when it happens for service s. It is equal to the sum of the time taken by an analyzer to identify that event ev happened for s and the time needed to send an alert to a planner component when an adaptation is required. Let af s be the analysis frequency for service s (e.g. analyze each 10 ms) and J s the set of time stamps at which we can analyze it, where the step size between each element in J s and the next element is equal to af s . We denote by p evs the probability that problem ev will happen for service s. Thus, ∀s ∈ S, evs∈Evs p evs = 1.

We also define Ac s as the set of adaptation actions that can be produced by a planner component in order to process problems that may happen for service s. Let pt acs be the planning time for action ac ∈ Ac s for service s. It is equal to the sum of the time taken by a planner to generate the adaptation plan ac ∈ Ac s for s and the time needed to send management actions to an executor component. We denote by p acs the probability that action ac will be chosen for service s. Hence, ∀s ∈ S, acs∈Acs p acs = 1. Let et acs be the execution time that is taken by an executor to carry out the adaptation action ac over service s. Note that a degradation of QoS lasts the time taken to produce and carry out adaptation plans over SBP services. We define mdt as the maximum allowed QoS degradation time for a timed SBP. It keeps the QoS degradation below a certain upper limit.

Without loss of generality, we assume that all the monitors, analyzers, planners and executors have the same requirements in terms of hardware resources (RAM, CPU, etc.), so that the optimization of their hosting cost will be reduced to the optimization of their number.

Problem Formulation

In this formulation, we consider the following decision variables: Given the aforementioned assumptions and notations, our problem can be formulated in equations [4.1-4.14] where objective function 4.1 aims to minimize the number of monitors, analyzers, planners and executors for the management of a timed SBP. Constraint 4.2 makes sure that only one monitor is assigned to each service all along the SBP life cycle. Constraint 4.4 (respectively 4.6, 4.8) makes sure that if a monitor is used (respectively analyzer, planner), then it is linked to only one analyzer (respectively planner, executor). Constraint 4.3 ensures that if a monitor is assigned to at least one service, then it is considered as used. Constraint 4.5 (respectively 4.7, 4.9) ensures that if an analyzer (respectively planner, executor) has at least one monitor (respectively analyzer, planner) linked to it, then it is considered as used. Constraints [4.10-4.14] guarantee that each component is assigned to at most one service at a time. The maximum allowed QoS degradation time for a given SBP is met according to constraint 4. Considering the number of deployments of applications in a public Cloud (see the previous chapter, Section 3.2.4 for more details), and as we will show in the evaluation section (Section 4.6), the time needed to solve the optimization model using the CPLEX solver is not acceptable. It can exceed two hours; and whenever the number of services goes beyond 26, the solver can not find the optimal solution. Consequently, finding the optimal solution, in this context, is not possible. Therefore, to tackle this NP-hard problem [START_REF] Sahni | Computationally related problems[END_REF], we propose in the following section an approach that provides near-optimal solutions in a polynomial time.

α m indicates if monitor m ∈ M is

Proposed Approach

Approach Overview

In this section, we introduce an approach based on two algorithms called ParalelServices and M-A-P-E_Assignment, for the determination of the appropriate number of monitors, analyzers, planners and executors that will be used by SBP services for their management such that this number is minimized while avoiding management bottlenecks.

The ParalelServices algorithm, whose pseudo-code is given in Algorithm 4.1, takes as input a timed SBP graph. It aims to determine all sets of services that can run in parallel.

The M-A-P-E_Assignment algorithm, whose pseudo-code is given in Algorithm 4.2, takes as input the sets of parallel services as well as the data needed for managing each service. It consists in assigning AM components to services while fulfilling the constraints given by equations [4.1-4.14].

ParallelServices Algorithm

First of all, CurrentParallelSet and CurrentPendingSet are initialized to the initial services of the timed SBP graph and the empty set, respectively (cf. lines 1-2). They are respectively used to store the current set of services that can run in parallel and the current set of pending services that will be executed after receiving the data required for their execution. After that, the current set of parallel services is added to the resulting sets (cf. line 3), and an array is initialized with the estimated execution times of services (cf. lines 4-5). ParalelServices iterates until determining all the sets of parallel services (cf. line 6 and line 28). To do so, the elements of the current sets are assigned to the previous sets, and the current sets are initialized to the empty set (cf. lines 7-9). Then the algorithm determines the minimum time from the times required by the current services to complete or start execution in order to determine the new sets of parallel and pending services (cf. line 10). First, it iterates over the previous set of parallel services; and for each service v i , the algorithm checks whether this service has completed its execution; i.e., the remaining time to complete its execution is equal to zero (cf. lines 11-13). As a result, for each successor, whether the type of this candidate node is either an AND/OR -Join and all its predecessors have completed their execution or not an AND/OR -Join, if the current node is of type service, then it is added to the current set of pending services; otherwise, ParalelServices continues to explore the successors of the candidate node seeking a node of service type (cf. lines [START_REF] Papazoglou | Blueprinting the cloud[END_REF][START_REF] White | Introduction to bpmn[END_REF][START_REF] Booch | Unified Modeling Language User Guide, The (2Nd Edition) (Addison-Wesley Object Technology Series[END_REF][START_REF] Florio | Gru: An approach to introduce decentralized autonomic behavior in microservices architectures[END_REF][START_REF] Hoenisch | Cost-efficient scheduling of elastic processes in hybrid clouds[END_REF]. If, the current has not completed its execution, it is added to the current set of parallel services (cf. lines [START_REF] Mastelic | Predicting resource allocation and costs for business processes in the cloud[END_REF][START_REF] Rekik | A linear program for optimal configurable business processes deployment into cloud federation[END_REF]. Second, the algorithm iterates over the previous set of pending services; and for each service v i , it checks whether the data transfer time to it has been completed (cf. lines [START_REF] Hadded | An efficient optimization algorithm of autonomic managers in service-based applications[END_REF][21]. If it is the case, v i is added to the current set of parallel services (cf. lines [22][START_REF] Hadded | Optimization of autonomic manager components in service-based applications[END_REF], otherwise it is added to the current set of pending services (cf. lines [START_REF] Hadded | Efficient resource allocation for autonomic service-based applications in the cloud[END_REF][25]. Afterwards, if the current set of parallel services has not been already determined in a previous iteration, it is added Algorithm 4.3, tries to assign a minimum number of planners and executors to the services such that the maximum allowed QoS degradation time for the SBP is not exceeded. To avoid management bottlenecks, our algorithms ensure the assignment of different monitors (respectively analyzers, planners, and executors) to parallel services.

Since each monitor must be linked to only one analyzer and multiple monitors can be linked to the same analyzer, the number of monitors that will be used to manage a timed SBP must be greater than or equal to the number of analyzers, i.e. M ≥ A. In addition, each analyzer (respectively planner) must be linked to only one planner (respectively executor), and multiple analyzers (respectively planners) can be linked to the same planner (respectively executor). The number of analyzers (respectively planners) must be greater than or equal to the number of planners (respectively executors), i.e. A ≥ P (respectively P ≥ E). Therefore, we must have M ≥ A ≥ P ≥ E, so P + E ≤ 2 × A.

As P + E ≤ 2 × A, if we start by determining the number of monitors and analyzers, the number of planners and executors may be less than the minimum required number of planners and executors that maintain the QoS degradation time for SBP below a certain upper limit. Consequently, M-A-P-E_Assignment starts by determining the number of planners and executors by invoking the P-E_Assignment procedure (cf. line 1). After that, it determines the number of analyzers and monitors by applying the M/A_Assignment procedure twice (cf. lines 2-3).

Algorithm 4.2: M-A-P-E_Assignment

Data: -ParallelSets: Set of sets of parallel services -T: Array containing the required execution time of each service -MT, MF: Arrays containing, respectively, the monitoring time and the monitoring frequency for each service -AT, AF: Arrays containing, respectively, the analysis time and the analysis frequency for each service -PT: Array containing the maximum planning time for each service -ET: Array containing the maximum adaptation time for each service -mdt: Maximum allowed QoS degradation time for the SBP Result: -M, A, P, E: Arrays containing, respectively, the monitor, analyzer, planner, and executor assigned to each service -n m , n a , n p , n e : Number of, respectively, monitors, analyzers, planners, and executors begin 1 P , n p , E, n e ← P-E_Assignment(P T , ET , mdt);

P-E_Assignment procedure

Initially, the P-E_Assignment procedure dedicates a planner and an executor for the management of the given SBP (cf. lines 2-5). The total QoS degradation time for SBP is then calculated, which is equal to the sum of time required to generate and execute adaptation plans over the services that make up SBP (cf. line 5 P_Assignment procedure The main objective of the P_Assignment procedure, whose pseudo-code is given in Algorithm 4.4, is to find the appropriate assignment of a given number of planners, i.e. n p , to the SBP services such that the total QoS degradation time for SBP is minimized. It goes through the sets of parallel services set by set; and for each one, their elements are sorted in a decreasing order to promote services with maximum planning time (cf. lines 1-2). After that, different planners are assigned to the first n p services in the current set; and for each planner assigned to a service, its working time is set to the planning time of the latter service (cf. lines 3-8). Then the total time required to generate adaptation plans for services belonging to the current set is calculated, and the latter is evenly shared between the n p planners to further reduce the total QoS degradation time for SBP (cf. line 9). The total QoS degradation time is equal to the sum of the maximum time from the times taken by the planners to generate adaptation plans for each set of parallel services and the the sum of the maximum time from the times taken by the executors to carry out adaptation plans for each set of parallel services (it is given in equation 4.9 (left)). Afterwards, the algorithm iterates over the set of services to which no planner has been assigned (cf. line 10); and for each one, it starts with the first planner (cf. line 11), and it checks whether the latter might be assigned to the current service, that is whether if the sum of the working time of this planner and the planning time required for the current service is less than or equal to the estimated time that a planner is expected to take to generate adaptation plans for the current set of parallel services (cf. line 16). If it is the case, this planner is assigned to the current service and its working time is updated (cf. lines [START_REF] Hoenisch | Cost-efficient scheduling of elastic processes in hybrid clouds[END_REF][START_REF] Mastelic | Predicting resource allocation and costs for business processes in the cloud[END_REF][START_REF] Rekik | A linear program for optimal configurable business processes deployment into cloud federation[END_REF]. Otherwise, the algorithm just updates the current planner (cf. line 20). In the case where the current planner number is greater than n p , P_Assignment looks for the appropriate planner that has the minimum working time to assign it to the current service (cf. lines 14-15). This step is repeated until a planner is assigned to the service (cf. lines 12-13). Finally, the total QoS degradation time for SBP is calculated (cf. line 21). E_Assignment procedure The main purpose of the E_Assignment procedure, whose pseudo-code is given in Algorithm 4.5, is to find the appropriate assignment of a new executor to the SBP services such that the total QoS degradation time for SBP is minimized. It starts by initializing the set of services to which the new executor will be assigned to the empty set (cf. line 1). Next, it goes through the sets of services, where the services belonging to a set are managed by the same planner, set by set, to ensure that each planner is linked to only one executor (cf. line 6). The set of services that further reduces the total QoS degradation time for SBP when the new executor is assigned to them is determined through the invocation of the QoSDegradationTime function (cf. lines 7-18). After that, the algorithm looks for other services to which it assigns the executor, and it comes to an end when it can not further reduce the total QoS degradation time

M/A_Assignment procedure

The M/A_Assignment procedure, whose pseudo-code is given in Algorithm 4.6, aims to assign a minimum number of analyzers (respectively monitors) to the SBP services. It goes through the sets of services, where the services belonging to a set are managed by the same planner (respectively analyzer), set by set, to ensure that each analyzer (respectively monitor) is linked to only one planner (respectively analyzer) (cf. line 2). Then for each service, the algorithm looks for an analyzer (respectively monitor) which is not used by any service during any time period when the current service uses it to guarantee that each analyzer (respectively monitor) is assigned to only one service at a time (cf. lines 4-12). The latter analyzer (respectively monitor) is then assigned to the service (cf. line 13), and it is considered as used at these time periods (cf. lines [START_REF] White | Introduction to bpmn[END_REF][START_REF] Booch | Unified Modeling Language User Guide, The (2Nd Edition) (Addison-Wesley Object Technology Series[END_REF][START_REF] Florio | Gru: An approach to introduce decentralized autonomic behavior in microservices architectures[END_REF]. The number of analyzers (respectively monitors) that will be used by services is possibly updated (cf. lines 17-18).

Theoretical Complexity

Our approach consists of two main algorithms called ParalelServices and M-A-P-E_Assignment. The first one consists in determining all the sets of parallel services (Algorithm 4.1). The worst case time complexity of this algorithm is bounded by O(n 4 ), where n is the number of services that compose the given SBP.

The second algorithm aims to assign a minimum number of monitors, analyzers, planners, and executors to the SBP services such that the total QoS degradation time for SBP is maintained below a certain upper limit while avoiding management bottlenecks (Algorithm 4.2). It consists of two procedures, called P-E_Assignment (Algorithm 4.3) and M/A_Assignment (Algorithm 4.6):

• The complexity of the P-E_Assignment procedure depends on those of the two invoked procedures, namely P_Assignment and E_Assignment, which have, respectively, a complexity of O(n 4 ) and O(n 4 ), where n is the number of services.

The number of iterations of the while loop of P-E_Assignment is equal to 2 × n. Hence, its overall complexity is O(2 × n × n 4 ) O(n 5 );

• The complexity of the M/A_Assignment procedure is O(n 3 × m 2 ), where n is the number of services and m is the maximum execution time from the estimated execution times of the SBP services. The number of iterations of the repeat loop is equal to n.

The worst case time complexity of the M-A-P-E_Assignment algorithm is O(n 5 + n 3 ×m 2 ). In summary, we can say that the theoretical complexity of the proposed approach is bounded by O(n 5 + n 3 × m 2 ).

Illustrative Example

Herein, we present an example illustrating how the approach works. Let us consider the example depicted in Figure 4.3 that represents a timed SBP graph. Applying the ParallelServices algorithm, as shown in Figure 4.4, the first iteration considers the initial sets: ParallelSet={S1,S2,S3,S4,S5} and PendingSet=∅. The number within the blue rectangle represents the estimated remaining time required by a service to complete its execution, while the number within the yellow rectangle represents the estimated remaining time required by a service to start its execution. The minimum time is equal to 10, so the estimated remaining time required by the service S1, S2, S3, S4 and S5 to complete their execution is 18, 0, 0, 5 and 5, respectively. It is equal to 0 for services S2 and S3, then their successors are added to the current pending set, i.e. PendingSet={S7} and ParallelSet={S1, S4, S5}. In the second iteration, the minimum time is equal to 5. Thus, the estimated remaining time required by service S1, S4 and S5 to complete their execution is 13, 0 and 0, respectively; and the estimated remaining time required by service S7 to start its execution is 0. It is equal to 0 for services S4, S5 and S7. The successors of services S4 and S5 (S8 and S9) are added to the current set of pending services, where the estimated time required by each one to start its execution is mentioned within the yellow rectangle; and service S7 is added to the current set of parallel services since the time required to transfer data from S3 to S7 is completed, where the time required by S7 to complete its execution is mentioned within the blue rectangle. The same process is applied until reaching the 7 th iteration with PendingSet=∅ and ParallelSet=∅. The ParallelServices algorithm comes to an end after seven iterations and checking that all the sets of parallel services are determined. Thus, it yields the following output:

AND-Split

AND-Join

S1 S2

XOR-Split

XOR-Join

ParallelSets={{(S1, S2), S3, S4, S5}, {S1, S7}, {S6, S8, S9}}

Then the P-E_Assignment algorithm is applied to determine the appropriate number of planners and executors for the management of the given timed SBP using the following inputs:

• ParallelSets={{(S1, S2), S3, S4, S5}, {S1, S7}, {S6, S8, S9}};

• PT=[3, 2, 4, 3, 2, 1, 2, 2, 3]; • ET=[3, 2, 2, 3, 3, 1, 2, 3, 2]; • mdt=26.
As shown in Figure 4.5, the first iteration considers a planner and an executor for the management of the given SBP. The time taken by the planner (respectively executor) to manage the services that belong to the first set of parallel services {(S1,S2),S3,S4,S5} is equal to max(3, 2) + 4 + 3 + 2 = 12 (respectively max(3, 2) + 2 + 3 + 3 = 11). In fact, services S1 and S2 are two alternative services, then we take the maximum time between the times needed to generate adaptation plans for these services (i.e. max(3, 2)); and as a planner (respectively executor) must be assigned to only one service at a time, it sequentially produces adaptation plans for the current services. As a result, we have done the sum for the planning times (respectively carry out times). However, the time taken by the planner (respectively executor) to manage the services that belong, respectively, to the second and the third set of parallel services is equal to 3 + 2 (respectively 3 + 2) and 1 + 2 + 3 (respectively 1 + 3 + 2). Using one planner and one executor, the total QoS degradation time for SBP is equal to 45. It is greater than the maximal allowed QoS degradation time that is equal to 26, so a new planner is added. In the second iteration, for each set of parallel services, the total time required for generating adaptation plans for the current services is calculated, and it is evenly shared between the two planners. The first set of parallel services consists of services S1, S2, S4, S3 and S5, so planner number 1 is assigned to services S1, S2 and S4, and planner number 2 is assigned to the services S3 and S5. The same process is applied to the second and third sets: planner number 1 is assigned to services S6 and S8, and planner number 2 is assigned to services S7 and S9. Using tow planners and one executor, tdt is equal to 34. It is still greater than the maximal allowed QoS degradation time. In this case, we calculate the new tdt whether we add (i) a new planner, or (ii) a new executor. It is respectively equal to 33 and 25. A new executor is then added for the management of SBP because it further reduces tdt and the algorithm comes to an end (25 26). The P-E_Assignment algorithm comes to an end after three iterations. It yields the following outputs:

P 1 1 2 1 2 1 2 1 2
After that, the M/A_Assignment algorithm is applied to determine the appropriate number of analyzers using the following inputs:

E 1 1 2 1 2 1 2 1 2
• PSets={{S1, S2, S4, S6, S8}, {S3, S5, S7, S9}};

• AT=[3, 1, 1, 2, 2, 1, 3, 2, 2]
;

• AF=[7, 4,

As shown in Figure 4.6 (right), the algorithm goes through the sets of services PSets, set by set, where the services belonging to a set are managed by the same planner; and for each service in the current set, it looks for an unoccupied analyzer. At first, analyzer number 1, i.e. A1, is assigned to service S1. Since S1 or S2 will be executed, A1 is also assigned to service S2. A1 is not occupied during any time period when service S4 will use it, i.e. [5,[START_REF] Ruz | Component-based generic approach for reconfigurable management of component-based SOA applications[END_REF](left), the latter is assigned to S4. The same process is applied to services S6 and S8. To ensure that each analyzer is linked to only one planner, different analyzers from the analyzers linked to planner number 1 must be used to manage the services to which planner number 2 is assigned, that is we can not use A1 to manage service S3, S5, S7 or S9. At first, analyzer number 2, i.e. A2, is assigned to service S3. We try then to assign A2 to service S5. In fact A2 is not occupied during any time period when service S5 will use it, i.e. [5,[START_REF] Ruz | Component-based generic approach for reconfigurable management of component-based SOA applications[END_REF], [START_REF] Mell | Sp 800-145. the nist definition of cloud computing[END_REF][START_REF] Enterprise | Cloud Computing Survey[END_REF], it is assigned to S5. The same process is repeated for services S7 and S9, and A2 is assigned to them. Finally, the M/A_Assignment algorithm is applied in order to determine the appropriate number of monitors using the following inputs:

• ASets={{S1, S2, S4, S6, S8}, {S3, S5, S7, S9}};

• MT=[3, 2, 1, 3, 2, 2, 4, 2, 3];

• MF= [5,3,4,3,5,3,4,3,3].

As shown in Figure 4.7 (right), the algorithm goes through the sets of services, set by set, where the services belonging to a set are managed by the same analyzer; and for each service in the current set, it looks for an unoccupied monitor. At first, monitor number 1, i.e. M 1, is assigned to service S1. Since S1 or S2 will be executed, M 1 is also assigned to service S2. M 1 is occupied when service S4 will use it (it is already used by service S2 at the time periods [3,5] and [START_REF] Asadollahi | StarMX: A framework for developing self-managing Java-based systems[END_REF][START_REF] De Oliveira | A framework for the coordination of multiple autonomic managers in cloud environments[END_REF]), then monitor number 2, i.e. M 2, is assigned to S4. M 1 is not occupied during any time period when service S6 will use it, i.e. [START_REF] Ionescu | A Robust Autonomic Computing Architecture for Server Virtualization[END_REF][START_REF] Frey | Towards a generic architecture and methodology for multi-goal, highly-distributed and dynamic autonomic systems[END_REF], [START_REF] Kurian | An autonomic computing architecture for business applications[END_REF][START_REF] Martinovic | E-health Framework Based on Autonomic Cloud Computing[END_REF], [START_REF] Mohamed | An autonomic approach to manage elasticity of business processes in the cloud[END_REF][START_REF] Hoenisch | Optimization of complex elastic processes[END_REF], [START_REF] Bessai | Resources allocation and scheduling approaches for business process applications in cloud contexts[END_REF][START_REF] Jiajie | Incorporating structural improvement into resource allocation for business process execution planning[END_REF] (left), M 1 is assigned to S6. We can not assign M 1 to service S8 because it is occupied during the time period [START_REF] Baker | Towards Autonomic Cloud Services Engineering via Intention Workflow Model[END_REF][START_REF] Frey | Towards a generic architecture and methodology for multi-goal, highly-distributed and dynamic autonomic systems[END_REF] when S8 will use it, but M 2 is not occupied at these time periods: M 2 is assigned to S8. To ensure that each monitor is linked to only one analyzer, different monitors from the monitors linked to analyzer number 1 must be used to manage the services to which analyzer number 2 is assigned. At first, monitor number 3, i.e. M 3, is assigned to service S3. We try then to assign M 3 to service S5. M 3 is not occupied by any service when S5 will use it. It is also assigned to S5. The same process is repeated for services S7 and S9, and M 3 is also assigned to them.

Performance Evaluation

In this section, we present a series of performance evaluations of our approach in terms of execution time and quality of provided solutions. In order to show the efficiency of this approach, we compare it to our solution presented in the previous chapter, Section 3.3.1, to verify how the approach enhances the AM components optimization process for the management of timed SBPs. We also compare the solution provided by this approach with the solution obtained by solving the formal model presented in Section 4.3.4 using the CPLEX solver, when such a solution is possible (see the previous chapter, Section 3.4.3 for more details).

The different experiments are carried out on an Intel Core i7 PC with 2.70 GHz and

In order to evaluate the performance of the proposed approach, we implement a generator of random timed SBPs. To the best of our knowledge, there is no available public dataset of timed business process models. Thus, to perform the experiments, we generate different connected timed SBP graphs with a number of services varying from 10 to 100, in increments of 10, and a number of edges ranging from n -1 to 3.2 × (n -1) (i.e. 320% of (n -1)), in increments of 0.2, where n is the order of the graph. Indeed, we do not generate graphs with more edges, since whenever the number of edges goes beyond 2.4 × (n -1), the lower bound number of AMs is equal to n (see the previous chapter for more details). All the results are average values across 10 independent runs. All data inputs are randomly generated and detailed in Table 4 The experimental results on the randomly generated dataset are illustrated in Figures 4.8 and 4.9. Compared to our previous approach, it can be seen that the proposed approach outperforms the previous approach in terms of reducing the number of monitors, analyzers, planners and executors for the management of timed SBPs. It decreases the number of AMs by about 54%. On the other hand, the gap between our approximate solution and the optimal solution is very small and does not exceed 10.34%. It means that our solution is very close to the optimal solution. As for the execution time, the results presented in Figure 4.10 show that our proposed approach takes a very short time to provide a near-optimal solution (less than 0.07 second). However, the exact method, solved by the ILP solver, takes more than two hours for 26 services. Note that the solver can not to find the optimal solution for the SBP graphs with more than 26 services due to a problem of memory. The experimental results demonstrate that our approach outperforms the previous one significantly in terms of both quality and execution time.

Conclusion

In this chapter, we broke down AM into its main components (monitor, analyzer, planner, executor) to minimize the number of each one separately for the management of timed SBPs while avoiding management bottlenecks. We formally defined the problem as ILP. Since solving the ILP formulation is time-consuming even for small timed SBPs, we proposed a near-optimal approach to solve this problem in a polynomial time, and an illustrative example of how it works was given. The experimental results show the efficiency of our approach.

The performance of the management SBPs depend highly on the autonomic resources allocated to them and the placement decisions of these latter in the Cloud. One of the key challenges faced by Cloud providers is to optimize the placement cost of the autonomic resources that will be used for the management of SBPs while fulfilling SBP QoS requirements. Hence, in the next chapter, we will focus on how to formulate this problem and solve it in a polynomial time.

Introduction

The performance of SBPs depend highly on the Cloud resources allocated to them includes: (i) the allocation of the adequate number of autonomic resources for their management, which is the subject of our two previous chapters, and (ii) the allocation of the adequate Cloud resources to host and execute these AMs and the services that make up SBPs. Since several research works (such as [START_REF] Hoenisch | Optimization of complex elastic processes[END_REF][START_REF] Bessai | Resources allocation and scheduling approaches for business process applications in cloud contexts[END_REF][START_REF] Goettelmann | Partitioning and cloud deployment of composite web services under security constraints[END_REF][START_REF] Malawski | Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds[END_REF]) have treated the problem of the allocation of the adequate Cloud resources to SBP services, in this chapter, we focus on the allocation of Cloud resources to host and execute autonomic resources that will be used by services for their management such that the management cost is minimized while meeting the QoS requirements.

This chapter is organized as follows: Preliminaries on IaaS Cloud providers and deployed SBPs are firstly introduced in Section 5.2. Then we describe the problem of determining the best placement decisions of AMs for the management of SBPs in the Cloud, and we formulate it as an optimization model in the case where the number of AMs is known or not known in advance. We also present two different approaches for these two cases in Sections 5.4 and 5.5. Illustrative examples as well as experimental results are provided for both cases. Finally, we conclude the chapter in Section 5.6.

Preliminaries: IaaS Cloud provider, Deployed SBP

In this section, we present some definitions and basic concepts related to an IaaS Cloud provider and deployed SBPs.

IaaS Cloud Provider

An IaaS Cloud provider is hosted in multiple geographically distributed regions. Each region has multiple Availability Zones (AZs), i.e. multiple data centers in simple terms, and each one may offer different VM types. Furthermore, multiple instances of each VM type can be offered by a zone. Definition 5.2.1 (IaaS Cloud provider). An IaaS Cloud provider is defined as a 3-tuple Z, cinter, cintra which is inspired from a real Cloud provider 1 where:

• Z is the set of AZs. Each AZ offers several types of VMs (V z = {vm}), vm = (cu, ram, cpu, bw, avail, v max ) such that cu is the compute price ($/h), ram is the RAM capacity (GB), cpu is the quantity of CPU cores, bw is the bandwidth capacity (M b/s), avail is the availability capacity (%), and v max is the maximum number of instances that can be deployed;

• cinter is the inter-AZ data transfer price ($/GB);

• cintra is the intra-AZ data transfer price ($/GB).

Deployed SBP

A deployed SBP in the Cloud is represented by a graph, where services are deployed on different instances of VMs into different AZs.

Definition 5.2.2 (Deployed SBP).

A deployed SBP is defined as a 6-tuple S, E, I, l, ε, δ where:

• S is the set of services;

• E ⊆ S × S is the set of edges that represents the data dependencies between services, such that (s i , s j ) ∈ E if the output data of service i is required for the execution of service j;

• I ⊂ S is the set of initial services;

• l : S → Z × V × I is a function that assigns, for each service s ∈ S, an instance i ∈ I of VM v ∈ V z in AZ z ∈ Z,
where s is deployed. I = {1, ..., v maxzv };

• ε : S ← N is a function that assigns, for each service s ∈ S, an estimated execution time;

• δ : S × S ← N is a function that assigns, for each pair of services (s i , s j ) ∈ E, an estimated quantity of data to be transferred from s i to s j .

Problem Description

Managing SBPs in the Cloud involves using autonomic resources to dynamically adapt services to changes. A key challenge faced by Cloud providers is to efficiently allocate Cloud resources to the services that make up these SBPs, which results in lower computing and communication costs while the required QoS is met. In fact, due to the diversity of services and autonomic resource QoS requirements as well as the heterogeneity of Cloud resources, and to ensure the performance of execution and other QoS aspects of SBPs, the computing resources allocated to them must satisfy the requirements of SBP services and autonomic resources that will be used by these services for their management in terms of hardware resources (CPU, RAM). Furthermore, these applications are characterized by their large data volume; which will result in a high amount of communication traffic between VMs. Consequently, it is also important to consider the placement decisions of services and autonomic resources in the Cloud. Since several research works (such as [START_REF] Hoenisch | Optimization of complex elastic processes[END_REF][START_REF] Bessai | Resources allocation and scheduling approaches for business process applications in cloud contexts[END_REF][START_REF] Goettelmann | Partitioning and cloud deployment of composite web services under security constraints[END_REF][START_REF] Malawski | Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds[END_REF]) have treated the problem of placement of services in the Cloud, in this chapter, we focus on the placement of autonomic resources that will be used by services that make up SBPs in the Cloud. The placement decisions of services will be considered as inputs.

AZ=us-east-1b AZ=us-east-1a

AZ=us-east-1c

Placement of AMs in the Cloud for Efficient Management of SBPs

In this section, we present our first proposal for determining the best placement decisions of a given number of AMs that will be used by services that make up SBPs for their management in the Cloud (see the two previous chapters for more details). First, we present an ILP formulation to solve this problem such that the total placement cost is minimized (Section 5.4.1). Afterwards, we present a near-optimal algorithm that provides good solutions in a polynomial time (Section 5.4.2). An illustrative example of our algorithm is then provided (Section 5.4.3). Afterwards, we present the experiments that we perform to evaluate it (Section 5.4.4).

Problem Formulation

We start this section by introducing some assumptions and notations in order to facilitate the formulation. Without loss of generality, we assume that all AMs have the same requirements in terms of hardware resources (RAM, CPU, etc.). Furthermore, we assume that all VMs are homogeneous, that is all VMs are characterized by the same hardware configuration in terms of CPU, RAM, etc. and have the same compute price. Given a deployed SBP, we denote by:

• S the set of services that make up SBP;

• P S the sets of services that can run in parallel;

• Z the set of AZs;

• V z the set of VMs offered by AZ z ∈ Z;

• M the set of AMs that will be used by services;

• D v the set of services deployed on VM v ∈ V;

• data the estimated data transfer quantity between a service and an AM.

. Towards this end, the following decision variables are defined:

• x s m takes 1 if AM m ∈ M is assigned to service s ∈ S, and 0 otherwise;

• y s m takes 1 if AM m ∈ M and service s ∈ S are deployed on the same VM, and 0 otherwise;

• z s m takes 1 if AM m ∈ M and service s ∈ S are in the same AZ, and 0 otherwise;

• w v m takes 1 if AM m ∈ M is deployed on VM v ∈ V ,
and 0 otherwise.

Given the above assumptions and notations, our problem can be formulated in equations [5.1-5.8] where the objective function 5.1 aims to minimize the sum of intra-AZ communication costs (the data transfer cost in the same VM is null) and the sum of inter-AZ communication costs. Constraint 5.2 makes sure that only one AM is assigned to each service all along the SBP life cycle. The authors in [75,[START_REF] Florio | Gru: An approach to introduce decentralized autonomic behavior in microservices architectures[END_REF] adopted the principle of using multiple AMs for the management of applications to avoid management bottlenecks, but they did not provide any means to optimize their number. In our work, an AM is able to manage a set of sequential services to reduce the amount of monitoring data that will be processed by each AM to prevent bottlenecks. Therefore, constraint 5.3 ensures that parallel services are managed by different AMs. Constraint 5.4

w v m = 1 ∀m ∈ M (5.4)
Constraint 5.5 makes sure that δ v s takes 1 if service s ∈ S is deployed on VM v ∈ V . We add equations [5.6-5.8] which ensure the linear relationships among the decision variables.

δ v s = 1 ∀z ∈ Z, v ∈ V z , s ∈ D v (5.5) v∈Vz δ v s + w v m -2.z s m ≤ 1 ∀z ∈ Z, ∀s ∈ S, ∀m ∈ M (5.6) v∈Vz δ v s + w v m -2.z s m ≥ 0 ∀z ∈ Z, ∀s ∈ S, ∀m ∈ M (5.7) δ v s + w v m -2.y s m ≥ 0 ∀z ∈ Z, ∀v ∈ V z , ∀s ∈ S, ∀m ∈ M (5.8)
Considering the number of deployments of applications in a public Cloud (see Chapter 3, Section 3.2.4 for more details), and as we will show in the evaluation section (Section 5.4.4), the time needed to solve the optimization model using the CPLEX solver is not acceptable. It can exceed two hours, and whenever the number of services goes beyond 21, the solver can not find the optimal solution. Consequently, finding the optimal solution, in this context, is not possible. Therefore, to tackle this NP-hard problem [START_REF] Sahni | Computationally related problems[END_REF], we propose in the following section an algorithm that provides near-optimal solutions in a polynomial time.

Proposed Algorithm

In this section, we introduce our proposed algorithm, whose pseudo-code is given in Algorithm 5.1. It takes as inputs a deployed SBP and a number of AMs and outputs AM assigned to each service, VM in which this AM is placed, and the total placement cost of AMs. It aims to determine the best placement decisions of these AMs in the Cloud such that the total transfer cost is minimized while fulfilling the constraints given by equations [5.1-5.8].

The algorithm starts by initializing the total placement cost to 0 (cf. line 1). After that, it starts with the first AM, and it looks for the set of maximum cardinality that contains the services that are deployed on the same VM and can run sequentially (cf. lines 6-10). The current AM is assigned to each service in this set, and it is placed in the current VM (cf. lines [START_REF] Wu | Sla-based resource provisioning for hosted software-as-a-service applications in cloud computing environments[END_REF][START_REF] Enterprise | Cloud Computing Survey[END_REF][START_REF] Papazoglou | Blueprinting the cloud[END_REF][START_REF] White | Introduction to bpmn[END_REF]. This step is repeated until all the AMs are assigned to services (cf. line 15). Then for each service that does not have an AM assigned to it, the algorithm starts by AMs that are placed in the same AZ with this service in order to minimize the data transfer cost, and it checks whether there is an AM that can be assigned to it (cf. line 17). If it is the case, the latter AM is assigned to this service (cf. line 18). Otherwise, an AM that is placed into a different AZ is assigned to the current service (cf. line 21). The total placement cost is then updated (cf. line 19 and line 22).

Our Proposed algorithm consists in determining the best assignment decisions of a given number of AMs to the services that make an SBP as well as to VMs. The worst case time complexity of this algorithm is bounded by O(n 2 × m × p), where n is the number of AMs, m is the number of VMs on which the services are deployed, and p is the number of sets of parallel services.

Illustrative Example

Herein, we present an example illustrating how the algorithm works. Let us consider the example depicted in Figure 5.3 that represents an example of an SBP composed of six services that are deployed on three homogeneous VMs.

In our example, we assume that the quantity of data to be transmitted from a service to an AM is 30. In addition, and for simplicity purposes, we assume that the sets of parallel services are: {S1}, {S2, S3}, {S2, S5}, {S4, S6}. The number of AMs that will be used by services is equal to 2. First, the algorithm consists in grouping the services that are deployed on the same VM and can sequentially run in different groups to determine the set of sequential services with a maximum cardinality. In this example, it is {S2, S4}. As a consequence, AM number 1, i.e. AM 1, is assigned to services S2 and S4, and AM 1 is placed in VM2. The same process is applied to the rest of services, so AM number 2 is assigned to services S5 and S6, and AM 2 is placed in VM2. The total placement cost is equal to 0 because the data transfer cost in the same VM is null. After that, the next iteration considers service S1. AM 1 is assigned to S1 resulting in cost = 0.01 × 30 = 0.3$. For service S3, AM 1 can not be assigned to it because it is already assigned to service S2 that can run in parallel with it, then AM 2 is assigned to S3 resulting in cost = cost + 0.05 × 30 = 1.8$.

Experimental Results

In this section, we present a series of performance evaluations of our algorithm in terms of execution time and quality of provided solutions. In order to show the efficiency of this approach, we compare it to the solution obtained by solving the formal model presented in Section 5.4.1 using the CPLEX solver, when such a solution is possible (see Chapter 3, Section 3.4.3 for more details).

To the best of our knowledge, none of the existing works has explicitly focused on the determination of the optimal placement decisions of AMs for the management of SBPs (see Chapter 2 for more details). Therefore, we do not make comparisons with existing work here. The different experiments are carried out on an Intel Core i5 PC with 2.53 GHz and 4GB of RAM. We use the commercial CPLEX solver 12.6 to solve the ILP formulation (Section 5.4.1).

In order to evaluate the performance of the proposed algorithm, we implement a generator of random SBPs (see the previous chapter, Section 4.6 for more details). For the experimental study, we vary the number of services from 2 to 22, in increments of 2.

In addition, we vary the number of VMs form 2 to 10, in increments of 2. We consider that cinter is equal to 0.05$, cintra is equal to 0.01$, and the quantity of data exchange between a service and an AM is equal to 30.

The experimental results are depicted in Figure 5.4. We note that the gap between the objective function of our algorithm and the exact model is small and does not exceed 11.72%. It means that our solution is very close to the optimal solution.

In addition, the results show that our algorithm takes a very short time to provide the best placement decisions of AMs in the Cloud (less than 0.14 second). However, the exact method, solved by the ILP solver, takes more than two hours for 21 services, which are deployed on 10 different VMs. Note that the solver can not find the optimal solution even for small size problems (for more than 21 services) due to a problem of memory (Figure 5.5). In fact, the exact method is very time and resource-consuming due to the branch and bound algorithm that performs poorly.

Joint Optimization of the Number of AMs and their Placement in the Cloud for Efficient Management of SBPs

In this section, we present our second proposal for determining the best placement decisions of AMs components for the management of SBPs, which will be determined during the placement process. First, we present an ILP formulation to solve this problem such that the total placement cost is minimized while meeting the QoS requirements (Section 5.5.1). Afterwards, we present a near-optimal approach that provides good solutions in a polynomial time (Section 5.5.2). An illustrative example of our approach is then provided (Section 5.5.3). Afterwards, we present the experiments performed to evaluate it (Section 5.5.4).

Problem Formulation

We start this section by introducing the notations that are used throughout the chapter as well as the assumptions. Next, we give the formulation of determining the best placement decisions of AM components that will be used by SBP services for their management in the Cloud.

Notations and Assumptions

Let S be the set of services that compose an SBP and P S the sets of parallel services. Let Z be the set of AZs, V z be the set of VMs types offered by AZ z ∈ Z, and I zv be the set of instances of VM v ∈ V z . We define D i as the set of services deployed on instance i ∈ I of VM v ∈ V into AZ z ∈ Z, and tet as the estimated execution time of SBP. Let M , A, P and E respectively represent the set of candidate monitors, analyzers, planners and executors that may be assigned to |S|. Each set has as cardinality the number of services, i.e. |S|, since in the worst case different monitors, analyzers, planners and executors will be assigned to the services. Let rcpu i , rram i and ravail i respectively be the required quantity of CPU cores, RAM capacity and availability by AM component

i ∈ M ∪ A ∪ P ∪ E or service i ∈ S.
We denote by t cv the time taken by AM component c deployed on VM v ∈ V to achieve its task, and by d kh the quantity of data to be transmitted from service (respectively monitor, analyzer, planner, executor) k to monitor (respectively analyzer, planner, executor, service) h. Let mf s be the monitoring frequency for service s and I s the set of time stamps at which we can monitor it, where the step size between each element in I s and the next element is equal to mf s . We define Ev s as the set of events that can result from the analysis of the monitoring data collected from service s. It contains the event 'no problem found' in addition to all the predefined problems that could happen. Let af s be the analysis frequency for service s, and J s be the set of time stamps at which we can analyze it, where the step size between each element in J s and the next element is equal to af s . We denote by p evs the probability that problem ev will happen for service s. Thus, ∀s ∈ S, evs∈Evs p evs = 1. We also define Ac s as the set of adaptation actions that can be produced by a planner component in order to process problems that could happen by service s. We denote by p acs the probability that action ac will be chosen for service s. Hence, ∀s ∈ S, acs∈Acs p acs = 1. Moreover, alloc nt takes 1 if instance n ∈ I of VM v ∈ V into AZ z ∈ Z is allocated to at least one service at time t ∈ [0..tet], and 0 otherwise.

Without loss of generality, we assume that all monitors (respectively analyzers, planners, executors) have the same requirements in terms of hardware resources (RAM, CPU, etc.) and that resource requirements by services and AM components are static. We also assume that the time is divided into time slots of equal length t ∈ [0..tet] and that each service i has a start time s i and a termination time e i .

Intervals

Decision variables

In this formulation, we consider the following decision variables:

• x rjn takes 1 if the candidate AM component j ∈ C of type r ∈ T is placed in instance n ∈ I of VM v ∈ V into AZ z ∈ Z,
if service s ∈ S is placed in instance n ∈ I of VM v ∈ V into AZ z ∈ Z. z∈Z v∈Vz n∈Izv x rjn = α rj ∀r ∈ T, ∀j ∈ C (5.4) x sjn = 1 ∀z ∈ Z, ∀v ∈ V z , n ∈ I zv , ∀j ∈ D i (5.5) (d
) Assignment constraints: Constraint 5.6 makes sure that only one monitor is assigned to each service all along the SBP life cycle. Constraint 5.10 ensures that if a monitor is used, then it is linked to only one analyzer. Constraint 5.14 guarantees that the latter analyzer is linked to only one planner. Constraint 5.18 ensures that the latter planner is linked to only one executor. Constraint 5.7 makes sure that if a monitor is assigned to at least one service, then it is considered as used. Constraint 5.11 (respectively 5.15, 5.19) makes sure that if an analyzer (respectively planner, executor) has at least one monitor (respectively analyzer, planner) linked to it, then it is considered as used. Constraints (5.8), (5.9), (5.12), (5.13), (5.16), (5.17), (5.20) We then retrieve sol * the best solution found for cost, associated with the value cost * = cost(sol * ). Therefore, cost * = cost(sol * ) (5.39) becomes a constraint of the problem associated with componentsNumber.

ComponentsNumber objective function: It consists in finding the minimum number of AMs components (componentsNumber objective function and constraints [5.1-5.39]) while ensuring the minimum deployment cost (cost objective function and constraints [5.1-5.38]).

Min componentsNumber = k∈T i∈C α ki

Considering the number of deployments of applications in a public Cloud (see Chapter 3, Section 3.2.4 for more details), and as we will show in the evaluation section (Section 5.5.4), the time needed to solve the optimization model using the CPLEX solver is not acceptable. It can exceed two hours and whenever the number of services goes beyond 14, the solver can not find the optimal solution. Consequently, finding the optimal solution, in this context, is not possible. Therefore, to tackle this NP-hard problem [START_REF] Sahni | Computationally related problems[END_REF], we propose in the following section an approach that provides near-optimal solutions in a polynomial time.

Proposed Approach

In this section, we introduce our proposed approach that operates in two steps. Step 1 is implemented using the AMsComponentsPlacement algorithm, whose pseudo-code is given in Algorithm 5.2. It aims to determine the best placement decisions of monitors, analyzers, planners and executors, which will be used by services for their management in the Cloud such that the total placement cost of these components is minimized while meeting the QoS requirements. Step 2 is implemented using the AMsComponentsNumber algorithm, whose pseudo-code is illustrated in Algorithm 5.3. Its main target is to reduce the number of AMs components while ensuring the placement cost determined in step 1.

AMsComponentsPlacement algorithm

The AMsComponentsPlacement algorithm takes as inputs a deployed SBP graph, the IaaS capacity in the form of VMs, and services and components requirements in terms of VM capacities in RAM, CPU, and availability. It outputs the monitor, the analyzer, the planner, and the executor assigned to each SBP service, on which VMs as well as in which AZs these latter components are placed as well as their placement cost.

The algorithm starts by initializing the total placement cost to 0 (cf. line 1). After that, for each service, it dedicates an AM that is placed in the VM where this service is deployed in order to avoid the communication and computing costs (cf. lines 2-3). The list of services is sorted in a decreasing order according to the total amount of resources (CPU then RAM) required by the dedicated components (cf. line 4). Next, for each service, AMsComponentsPlacement checks if the capacities of VM (on which the current service is deployed) in terms of RAM and CPU satisfy the AM components (cf. lines 5-6). If it is not the case, then for each component assigned to it where this component is placed on VM in which the current service is deployed (cf. line 8), the list of candidate VMs which can host the current component is determined (cf. lines 9-10). For each candidate VM, the cost of the placement of the current AM in this VM is calculated which takes into account inter-AZ and intra-AZ communication costs as well as VMs compute costs (cf. lines [START_REF] Wu | Sla-based resource provisioning for hosted software-as-a-service applications in cloud computing environments[END_REF][START_REF] Enterprise | Cloud Computing Survey[END_REF]. The component to be chosen is the one with the minimum cost, and it is moved to VM on which it executes in minimum cost (cf. lines [START_REF] Papazoglou | Blueprinting the cloud[END_REF][START_REF] White | Introduction to bpmn[END_REF][START_REF] Booch | Unified Modeling Language User Guide, The (2Nd Edition) (Addison-Wesley Object Technology Series[END_REF][START_REF] Florio | Gru: An approach to introduce decentralized autonomic behavior in microservices architectures[END_REF][START_REF] Hoenisch | Cost-efficient scheduling of elastic processes in hybrid clouds[END_REF]. Then the total placement cost is updated (cf. line 18). These steps are repeated until the resource constraints on VM, on which the current service is deployed, is not violated (cf. line 6).

AMsComponentsNumber algorithm

AMsComponentsNumber starts by minimizing the number of executors, planners, analyzers and monitors, which will be used by the SBP services in order not to push any monitor (respectively analyzer, planner) to link to more than one analyzer (respectively planner, executor). To do so, it checks for each service whether there is an executor that is not used by any service during the execution period of this service, and the latter executor guarantees its requirements while it is placed on VM where the executor assigned to it is placed to ensure the placement cost provided by the AMsComponentsPlacement algorithm. If it is the case, this executor is assigned to the current service (cf. lines 1-3). After that, the algorithm goes through the sets of services, where the services belonging to a set are managed by the same executor, set by set, to ensure that each planner is linked to only one executor (cf. lines 4-5). For each set, it looks for minimizing the number of planners assigned to this set (cf. lines 6-9). In the same way, it determines the appropriate number of analyzers and monitors (cf. lines 10-11).

Theoretical Complexity

Our proposed approach consists of two algorithms. The first one aims to find the best placement decisions of AMs components for the management of an SBP (Algorithm 5.2). Its worst case time complexity is bounded by O(n 2 * m * p), where n is the number of services that compose SBP, m is the number of VMs, and p is the maximum time from the estimated execution times of the SBP services. The second algorithm aims to minimize the number of AMs components while ensuring the total placement cost provided by Algorithm 5.2 (Algorithm 5.3). The worst case time complexity of this algorithm is bounded by O(n 2 * p), where n is the number of services and p is the maximum time from the estimated execution times of the SBP services. In summary, we can say that the theoretical time complexity of our approach is bounded by O(n 2 * m * p).

Illustrative Example

Herein, we present an example illustrating how the approach works. Let us consider the example depicted in Figure 5.6 that represents an example of an SBP composed of five services that are deployed on three heterogeneous VMs.

In our example, we assume that the resources required for each AM component to complete its execution are 200MB of RAM and one CPU. In addition, we assume that each service requires 500 MB of RAM and services S1, S2, S3, S4 and S5 respectively require 2, 4, 2, 2 and 4 CPUs to complete their execution. Furthermore, we assume that the quantity of data to be transmitted from service (respectively monitor, analyzer, planner, executor) to monitor (respectively analyzer, planner, executor, service) is 30 (respectively 25,[START_REF] Hadded | An efficient optimization algorithm of autonomic managers in service-based applications[END_REF]25,[START_REF] Mastelic | Predicting resource allocation and costs for business processes in the cloud[END_REF]. For simplicity purposes, we also assume that the sets of parallel services are: {S1, S2, S3}, {S4, S6}. Initially, AMsComponentsPlacement assigns to each service an AM (monitor, analyzer, planner, and executor) which is placed in the same VM with it. Next, the services are sorted in a descending order according to the total amount of resources (CPU, RAM) required by their AMs: S2, S5, S1, S3, S4.

The first iteration of the while loop considers service S2. The capacity of V M 2 is violated. The component to be moved is the one with the minimum cost. In this case, monitor m2 is moved from V M 2 to V M 3 resulting in cost=0.01 × (30 + 25) × 1 = 0.55$ (intra × ic(m2) × az(VM3,VM2)). Then analyzer a2 is moved from V M 2 to V M 3 resulting in cost=0.55 + 0.01 × 20 × 1 -0.01 × 25 × 1 = 0.5$ (cost + intra × ic(a2) × az(VM3,VM2) -intra × oc(a2,VM3) × az(VM3,VM2)). V M 3 can not host component p2 since V M 3 has 8 CPUs which are used by S3, the AM components assigned to S3 and components m2 and a2 (2 + 4 + 1 + 1). Thus, p2 is moved from V M 2 to V M 1 resulting in cost=0.5 + 0.05 × 25 × 1 + 0.04 × 20 × 1 = 2.55$ (cost+ inter × ic(p2) × (1-az(VM1,VM2)+(inter-intra) × oc(p2, VM3) ×(1-az(VM1, VM2)). e2 is also moved from V M 2 to V M 1 resulting in cost=2.55 + 0.05 × 18 × 1 -0.05 × 25 × 1 = 2.2$ (cost+ inter × ic(e2) × (1-az(VM1,VM2)-inter × oc(e2, VM2) × (1-az(VM1, VM2)).

The second iteration of the while loop considers service S5. The capacity of V M 3 satisfies the requirements of the components assigned to S5, so there are no component to move. The same process is applied to services S1 and S3.

The fifth iteration considers service S4. The capacity of V M 2 is violated. Monitor m4 is moved from V M 2 to V M 1 resulting in cost=2.2 + 0.05 × (30 + 25) × 1 = 4.95$ (inter × ic(m4) × az(VM1,VM2)). Then analyzer a4 is moved from V M 2 to V M 1 resulting in cost=4.95 -0.05 × 25 × 1 + 0.05 × 20 × 1 = 4.7$ (cost -inter × oc(a4,VM1) × az(VM1,VM2) + inter × ic(a4) × (1-az(VM1,VM2)).

Experimental Results

In this section, we present a series of performance evaluations of our approach in terms of execution time and quality of the provided solutions. In order to show the efficiency of this approach, we compare it to the solution obtained by solving the formal model presented in Section 5.5.1 using the CPLEX solver, when such a solution is possible. The different experiments are carried out on an Intel Core i7 PC with 2.70 GHz and 8GB of RAM. We use the commercial CPLEX solver 12.6 to solve the ILP formulation (Section 5.5.1).

In order to evaluate the performance of the proposed approach, we implement a generator of random SBPs (see the previous chapter, Section 4.6 for more details). For the experimental study, we vary the number of services from 2 to 14, in increments of 1, and from 10 to 100, in increments of 10. In addition, we consider that VMs have different hardware capacities. In particular, the following capacities are considered for VMs where at least a service is deployed on each one: Each VM may host 100%, 75%, 50%, 25%, or 0% of the components assigned to the services deployed on it; i.e., CPU and RAM capacities of a VM depend on the RAM and CPU required by the components. All the results are average values across 10 independent runs. All data inputs are randomly generated and detailed in Table 5.12 .

The proposed algorithm is able to find the optimal solution for more than 33% of

Conclusion

In this chapter, we focused on the problem of the placement of autonomic resources for the management of timed SBPs in the Cloud. We first proposed an approach for determining the best placement decisions of a pre-determined number of AMs in the Cloud. Then we presented an approach that aims to combine the placement and determination of an appropriate number of AMs in the Cloud. An ILP formulation and an illustrative example of how the approach works were given for both cases. We presented the different experiments that we realized to show the efficiency of our proposals.

ferent experiments that we performed on public real and randomly generated datasets of SBPs show the added value of our contribution in managing SBPs.

After facing the challenge of allocating the appropriate number of AMs for the management of SBPs, we were interested in the components that make up an AM (monitor, analyzer, planner and executor) to integrate these latter separately in the optimization process. We proposed a deterministic optimization model to find the optimal number of monitors, analyzers, planners and executors, which will be used by SBPs. We also suggested an approach that provides good solutions. An illustrative example as well as experimental results are provided and show the effectiveness of the proposed approach.

In order to go further in our reasoning, we proposed to provide solutions for the placement of AMs that will be used to manage SBPs in the Cloud. To this end, we proposed two approaches for the placement of AMs while considering two different contexts: Placement of a given number of AMs and placement of AMs that will be determined progressively during the placement process. These approaches consist in determining the optimal placement decisions of AMs in the Cloud such that the overall management cost is minimized while ensuring the required quality of service of SBPs. We used a deterministic optimization model for smaller graphs to benchmark our approaches that exhibit better scaling behavior.

Future work

In this thesis, we faced different complex problems related to optimal Cloud resource allocation for the management of SBPs. We solved many of them and we included others in our future work.

Our suggested approaches allow for the optimization of the number of AMs that will be assigned to the SBP services for their management. Nonetheless, decisions taken in isolation by an AM may indirectly interfere with the decision taken by other AMs and globally affect the performance of the whole SBPs. Hence, the coordination of AMs is a key task for the effective management of the whole business process. Several research works have, by and large, tackled the problem either in hierarchical fashion by adding AMs in charge of coordination or in centralized fashion by using a shared public knowledge for coordinating AMs which are assigned to services [START_REF] Mola | Collaborative policy-based autonomic management: In a hierarchical model[END_REF][START_REF] Belhaj | Collaborative autonomic management of distributed component-based applications[END_REF][START_REF] De Oliveira | A framework for the coordination of multiple autonomic managers in cloud environments[END_REF]. As a first extension of our work, we propose to extend our approaches to optimize not only AMs that will be explicitly used to manage the SBP services but also additional AMs that will be in charge of coordinating AMs in order to guarantee the effective management of the whole SBP.

The second extension consists in proposing a management tool based on an autonomic system for optimal deployment of SBPs in the Cloud integrating our proposed algorithms as well as other optimization algorithms regarding the deployment of the SBP services and the coordination of AMs. In fact, it would be interesting to be able to make optimal decisions for these problems when a new SBP deployment request is triggered. To do this, we can investigate the use of a higher-level AM. The latter is responsible for (1) collecting information relative to the interdependency relationship among the SBP services, the assignment constraint, the resource consumption of different services and AMs, the Cloud resources capacities, etc., (2) analyzing the collected data, and (3) carrying out the assignment, placement and coordination decisions made by the planner component.

Evaluating the performance of allocation policies in real Cloud environments for different applications under critical conditions is a challenging task. Indeed, the use of a real Cloud environment is costly and makes the reproduction of some results an extremely difficult task due to the system size and configuration. Moreover, the evaluation of certain scenarios is not supported [START_REF] Buyya | Modeling and simulation of scalable cloud computing environments and the cloudsim toolkit: Challenges and opportunities[END_REF]. An alternative to that is the use of simulation tools that allow the reproduction of the tests and offer the possibility of evaluating the hypothesis and models under different conditions to cope with the possible performance degradation before deploying in a real Cloud. In addition, these simulation tools are free. In [START_REF] Ettikyala | A study on cloud simulation tools[END_REF], the authors presented a study and comparison of existing Cloud simulation tools. As an extension of our work, we aim to utilize the Cloud simulator CloudSim [START_REF] Buyya | Modeling and simulation of scalable cloud computing environments and the cloudsim toolkit: Challenges and opportunities[END_REF] which is widely used in the literature [START_REF] Beloglazov | Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[END_REF][START_REF] Fakhfakh | Dealing with structural changes on provisioning resources for deadline-constrained workflow[END_REF][START_REF] Humane | Simulation of cloud infrastructure using cloudsim simulator: A practical approach for researchers[END_REF] to allow the simulation of different Cloud and SBP configurations and come up with decisions regarding management resource amounts and their placement at low cost. To do this, we propose to implement an extension of the CloudSim simulator that enables the simulation of the autonomic management of SBPs. The extension will include an implementation of the dependency relationships between the SBP services and the implementation of our proposed algorithms.

Contents 1 . 1 1 . 2 1 . 3 1 . 4

 11121314 General Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Motivation and Problem Statement . . . . . . . . . . . . . . . . 2 Objectives and Contributions . . . . . . . . . . . . . . . . . . . . 3 1.3.1 AMs Optimization in SBPs . . . . . . . . . . . . . . . . . . . . . . 3 1.3.2 AMs Components Optimization in Timed SBPs . . . . . . . . . . . 4 1.3.3 Placement of AMs for the Management of SBPs in the Cloud . . . 4 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Figure 2 .

 2 Figure 2.1 gives an overview of the introduced Cloud computing concepts.

Figure 2 . 1 :

 21 Figure 2.1: Cloud computing models [1].

Figure 2 . 2 :

 22 Figure 2.2: SOA actors and roles.

Figure 2 . 3 :

 23 Figure 2.3: IBM architecture of autonomic resource [2].

Figure 2 .

 2 4 illustrates IBM's vision of the structure of the autonomic resources and their interactions.

Figure 2 . 4 :

 24 Figure 2.4: Structure of autonomic resources and their interactions [3].

Figure 2 . 5 :

 25 Figure 2.5: System architecture for autonomic Cloud management [4].

Figure 2 . 6 :

 26 Figure 2.6: Rainbow framework [5].

Figure 2 . 7 :

 27 Figure 2.7: StarMX high-level static architecture [6].

Figure 2 . 8 :

 28 Figure 2.8: Autonomic component "A" [7].

Figure 2 . 9 :

 29 Figure 2.9: Architecture overview of self-adaptation framework [8].

Contents 3 . 1 3 . 2

 3132 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Problem Description and Formulation . . . . . . . . . . . . . . . 25 3.2.1 SBP Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.4 Need for Approximate Approach . . . . . . . . . . . . . . . . . . . 29 3.3 AMs Optimization in SBP Graphs with Cycles . . . . . . . . . 29 3.3.1 Proposed Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.2 Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 34 3.4 AMs Optimization in SBP Graphs Without Cycles . . . . . . . 38 3.4.1 Proposed Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4.2 Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.4.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 44 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Figure 3 . 1 :

 31 Figure 3.1: First research problem: Finding appropriate number of AMs for management of SBP services.

Algorithm 3 . 1 : 5 P

 315 LowerBound Data: -G =(V,E,I,τ ,ID): SBP graph Result: -ParallelSets: Set of sets of parallel services -lbn: Lower bound number of AMs begin 1 CurrentP arallelSet ← Services(I); 2 lbn ← |CurrentP arallelSet|; 3 P arallelSets ← {CurrentP arallelSet}; 4 repeat reviousP arallelSet ← CurrentP arallelSet; 6 CurrentP arallelSet ← ∅; 7 for v i ∈ P reviousP arallelSet do 8 for

Algorithm 3 . 2 : 1 i ← 1 ; 2 S 3 for s ∈ S do 4 7 if s ∈ set then 8 9 i

 3211234789 ServiceRelatedParallelSets Data: -G =(V,E,I,τ ,ID): SBP graph -ParallelSets: Set of sets of parallel services Result: -ServiceRelatedParallelSets: Array of <serviceId,serviceSet> begin ← ServiceNodes(V ); ServiceRelatedP arallelSets[i].serviceId ← s; 5 ServiceRelatedP arallelSets[i].serviceSet ← ∅; 6 for set ∈ P arallelSets do ServiceRelatedP arallelSets[i].serviceSet ← ServiceRelatedP arallelSets[i].serviceSet ∪ (set \{s}); ← i + 1;

Figure 3 . 2 :

 32 Figure 3.2: Example of SBP graph with cycle.

Figure 3 . 3 :

 33 Figure 3.3: First proposal: Number of AMs versus number of services -Experiments on IBM and SAP datasets.

Figure 3 . 4 :

 34 Figure 3.4: First proposal: Lower bound number of AMs / services number (in %) versus SBP graph density -Experiments on randomly generated dataset.

Figure 3 . 5 :

 35 Figure 3.5: First proposal: Cardinality of ParallelSets versus number of services -Experiments on randomly generated dataset.

Figure 3 . 6 :

 36 Figure 3.6: First proposal: Difference between number of AMs provided by AMsAssignement algorithm and lower bound number of AMs (in %) -Experiments on randomly generated dataset.

Algorithm 3 . 5 : 6 CurrentP arallelSet ← I; 7 while 8 N

 35678 AMsAssignement Data: -G = (V,E,I,τ ,ID): SBP graph Result: -AMs: Array containing the AM assigned to each service -nbAMs: Number of AMs begin 1 AM s ← [vector of 0s]; 2 nbAM s ← 0; 3 for s ∈ I do 4 nbAM s ← nbAM s + 1; 5 AM s[ID of s] ← nbAM s; CurrentP arallelSet = ∅ do extP arallelSet ← ∅; 9 for s i ∈ CurrentP arallelSet do for (s i ,s j ) ∈ E do if s s.t.(s ∈ Predecessor({s j }) and AM s[ID of s]=0) then N extP arallelSet ← N extP arallelSet ∪ {s j }; if s s.t.(s ∈ Successor({s i }) and AM s[ID of s

Figure 3 . 7 :

 37 Figure 3.7: Example of SBP graph without cycles where XOR-Split preceding two AND-Splits (left) and result of applying Algorithms 3.4 and 3.5 on it.

Figure 3 . 8 :

 38 Figure 3.8: Example of SBP graph without cycles where AND-Split preceding two XOR-Splits (left) and result of applying Algorithms 3.4 and 3.5 on it.

Figure 3 . 9 :

 39 Figure 3.9: Second proposal: Number of AMs versus number of services -Experiments on IBM and SAP datasets.

Figure 3 . 10 :

 310 Figure 3.10: Second proposal: Execution time versus number of services -Experiments on IBM and SAP datasets.

Figure 3 . 11 :

 311 Figure 3.11: Second proposal: Number of AMs versus number of services -Experiments on randomly generated dataset.

Figure 3 . 12 :

 312 Figure 3.12: Second proposal: Execution time versus number of services -Experiments on randomly generated dataset.

Figure 4 . 1 :

 41 Figure 4.1: Autonomic control loop for Cloud resource.

Based on Definition 4 . 3 . 1 ,

 431 Figure 4.2 shows an example of a timed SBP graph. The number within the dash circle represents the estimated execution time of a service. The number next to an edge represents an inter-service estimated data transfer time. For example, the estimated execution time of Choose supplier is equal to 16, while the estimated data transfer time between the latter and Contact supplier 1 (respectively Contact supplier 2, Contact supplier 3) is equal to 11, and it is equal to 9 between Contact supplier 1 and Receive products.

Figure 4 . 2 :

 42 Figure 4.2: Example of timed SBP graph.

2 A 3 M

 23 , n a ← M/A_Assignment(P Sets, AT , AF ); /*PSets is a set of sets of services where services belonging to a set are managed by the same Planner*/ , n m ← M/A_Assignment(ASets, M T , M F ); /*ASets is a set of sets of services where services belonging to a set are managed by the same Analyzer*/

Algorithm 4 . 4 : 1 for set ∈ P arallelSets do 2 SortDecreasingOrderOfPlanningTimeOfServices

 4412 P_Assignment procedure Data: -n p Result: -P: Array containing the planner assigned to each service -tdt: Total QoS degradation time for the SBP begin

Figure 4 . 3 :

 43 Figure 4.3: Example of timed SBP graph.

Figure 4 . 4 :

 44 Figure 4.4: Execution trace of ParallelServices algorithm.

Figure 4 . 5 :

 45 Figure 4.5: Execution trace of P-E_Assignment algorithm.

Figure 4 . 6 :

 46 Figure 4.6: Execution trace of M/A_Assignment algorithm: Assignement of analyzers to SBP services.

Figure 4 . 7 :

 47 Figure 4.7: Execution trace of M/A_Assignment algorithm: Assignement of monitors to SBP services.

Figure 4 . 8 :

 48 Figure 4.8: Number of monitors, analyzers, planners, and executors versus number of services varying from 10 to 26.

Figure 4 . 9 :

 49 Figure 4.9: Number of monitors, analyzers, planners, and executors versus number of services varying from 30 to 100.

Figure 4 . 10 :

 410 Figure 4.10: Execution time versus number of services.

  Figure 5.1 depicts a simplified representation a Cloud infrastructure provider.

Figure 5 . 1 :

 51 Figure 5.1: Cloud infrastructure provider [9].

Figure 5 . 2 :

 52 Figure 5.2: Second research problem: Finding the best placement decisions of AMs to be used by SBP services in the Cloud.

Figure 5 . 3 :

 53 Figure 5.3: Example of SBP composed of six services deployed on three different homogeneous VMs.

Figure 5 . 4 :Figure 5 . 5 :

 5455 Figure 5.4: First proposal: AMs placement cost versus number of services and VMs.

  C = {1, 2, .., |S|} is the set of services or the set of candidate monitors (respectively analyzers, planners, or executors). I = {1, .., v maxzv }. T = {monitor, analyzer, planner, executor}. Constants m = 1, a = 2, p = 3, e = 4 and s = 5 are respectively the identifiers of monitor, analyzer, planner, executor and service types.

Figure 5 . 6 :

 56 Figure 5.6: Example of SBP composed of five services deployed on three different heterogeneous VMs.

Figure 5 . 8 :Figure 5 . 9 :

 5859 Figure 5.8: Second proposal: Execution time of CPLEX versus number of services.

  2

  It provides to consumers appropriate resources to develop, deploy and manage applications onto the Cloud infrastructure using libraries, programming languages and tools supported by the Cloud provider. Examples of PaaS platforms are Cloud Foundry 3 and Windows Azure 4 ; The consumer is able to use applications running on a Cloud infrastructure over the Internet. Examples of SaaS are Salesforce 5 and Netsuite 6 .

;

• Platform as a Service (PaaS):

• Software as a Service (SaaS):

  Join, OR-Join} and AllPredecessors(v j )) then

	11	if set s.t.(set ∈ P arallelSets and CurrentP arallelSet ⊆ set) then
	12	P arallelSets ← P arallelSets ∪ CurrentP arallelSet;
	13	if |CurrentP arallelSet| > lbn then
	14	lbn ← |CurrentP arallelSet|;

10 CurrentP arallelSet ← CurrentP arallelSet ∪ Services(v j ); 15 until (CurrentP arallelSet = ∅ or ∃ set s.t.(set ∈ P arallelSets and CurrentP arallelSet ⊆ set));

  line 12). The resulting number of AMs is possibly updated (cf. lines[START_REF] Papazoglou | Blueprinting the cloud[END_REF][START_REF] White | Introduction to bpmn[END_REF].

	Algorithm 3.3: AMsAssignement
		Data: -G =(V,E,I,τ ,ID): SBP graph
		-ServiceRelatedParallelSets: Array of <serviceId,serviceSet>
		Result: -AMs: Array containing the AM assigned to each service
		-nbAMs: Number of AMs
		begin
	1	AM s ← [vector of 0s];
	2	nbAM s ← 0;
	3	SortDecreasingOrderOfCardinalityOfSets(ServiceRelatedP arallelSets);
	4	S ← ServiceNodes(V );

5 for i ∈ {1, 2,. . . |S|} do 6 currentAM ← 1; 7 repeat 8 if s s.t.(s ∈ ServiceRelatedP arallelSets[i].serviceSet and AM s[s] = currentAM ) then 9 AM s[ServiceRelatedP arallelSets[i].serviceId] ← currentAM ; 10 else 11 currentAM ← currentAM + 1; 12 until s s.t.(s ∈ ServiceRelatedP arallelSets[i].serviceSet and AM s[s] = currentAM ); 13 if currentAM > nbAM s then 14 nbAM s ← currentAM ;

Table 3 .

 3 .1). 1: Details of the IBM dataset.

		Min.	Max.
	Number of start events	1	32
	Number of end events	1	32
	Number of services	1	195
	Number of gateways	1	139
	Number of edges	2	326
		Min.	Max.
	Number of events (start, end, intermediate)	2	67
	Number of services	1	43
	Number of gateways	0	39
	Number of edges	2	125

• Dataset 2 consists of 205 EPC process models from the SAP reference models represented in an EPC Markup Language (EPML) format

[START_REF] Keller | Sap R/3 Process Oriented Implementation[END_REF]

. At most, there are 43 services, 39 gateways, and 125 edges in a process (Table

3

.2).

Table 3 .

 3 2: Details of the SAP dataset.

Table 3 .

 3

	Graph Sizes	Services	Nodes	Edges
		10	16 -22	19 -30
		20	32 -46	42 -59
		30	48 -72	60 -100
		40	70 -100	85 -122
	Small	50 60	90 -124 114 -134	112 -152 130 -171
		70	126 -150	155 -214
		80	150 -182	184 -220
		90	164 -198	203 -260
		100	174 -210	227 -275
		150	286 -348	369 -432
		200	356 -424	458 -544
		250	474 -524	604 -673
		300	582 -636	754 -814
	Large	350 400	658 -748 760 -846	850 -950 967 -1084
		450	854 -966	1099 -1228
		500	972 -1036	1243 -1316
		550	1078 -1152	1384 -1486
		600	1178 -1258	1494 -1602

3: Characteristics of generated small and large SBP graphs.

  used by at least one service; β a indicates if analyzer a ∈ A is used by at least one monitor; σ p indicates if planner p ∈ P is used by at least one analyzer; ϕ e indicates if executor e ∈ E is used by at least one planner; y a

m specifies if monitor m ∈ M is linked to analyzer a ∈ A; z p a specifies if analyzer a ∈ A is linked to planner p ∈ P ; w e p specifies if planner p ∈ P is linked to executor e ∈ E; x s m expresses if monitor m ∈ M is assigned to service s ∈ S; γ t sm expresses if monitor m ∈ M is assigned to service s ∈ S at time t ∈ T ; λ t sa expresses if analyzer a ∈ A is assigned to service s ∈ S at time t ∈ T . These decision variables are equal to 1 if their indications are verified and 0 otherwise.

  14.

	Subject to: x s m = 1 S∈P S max p∈P ( s∈S acs∈Acs	p acs .pt acs .v s p ) + max e∈E	s∈S acs∈Acs (	∀s ∈ S e ) mdt (4.19) (4.2) p acs .et acs .k s
	m∈M
	x s m Then we must add the following logical constraints: α m	∀s ∈ S, ∀m ∈ M	(4.3)
	y a m = α m u s a + 1 β a m + z p m + y a x s m a∈A y a m x s m + y a a v s p + 2 z p a = β a x s m + y a m + z p a + w e p k s e + 3 ∀s ∈ S, ∀m ∈ M, ∀a ∈ A, ∀p ∈ P, ∀e ∈ E (4.22) ∀m ∈ M (4.4) ∀s ∈ S, ∀m ∈ M, ∀a ∈ A (4.20) ∀m ∈ M, ∀a ∈ A ∀s ∈ S, ∀m ∈ M, ∀a ∈ A, ∀p ∈ P (4.21) (4.5) ∀a ∈ A (4.6)
	p∈P
	z p a	σ p					∀a ∈ A, ∀p ∈ P	(4.7)
	w e p = σ p					∀p ∈ P	(4.8)
	e∈E
	w e p	ϕ e					∀p ∈ P, ∀e ∈ E	(4.9)
	x s m	γ t
		p evs .x s m .y a m	λ t
	m∈M evs∈Evs
	S∈P S m∈M a∈A	max p∈P	( s∈S acs∈Acs	p acs .pt acs .x s m .y a m .z p a ) + max e∈E	(	s∈S acs∈Acs
							p acs .et acs .x s m .y a m .z p a .w e p ) mdt (4.14)
	However, the above model is not linear due to constraints 4.12 and 4.14. In order to
	linearize it, we introduce new decision variables u s a , v s p , and k s e defined as follows:
	u s a = x s m .y a m					∀s ∈ S, ∀m ∈ M, ∀a ∈ A	(4.15)
	v s p = x s m .y a m .z p a				∀s ∈ S, ∀m ∈ M, ∀a ∈ A, ∀p ∈ P	(4.16)
	k s e = x s m .y a m .z p a .w e p		∀s ∈ S, ∀m ∈ M, ∀a ∈ A, ∀p ∈ P, ∀e ∈ E	(4.17)
	We substitute equation 4.15 in constraint 4.12 and equations 4.16 and 4.17 in con-
	straint 4.14. Constraints 4.12 and 4.14 respectively become as follows:
		min		α m +	ϕ e	(4.1)
				m∈M		e∈E

a∈A β a + p∈P σ p + sm ∀m ∈ M, ∀s ∈ S, ∀i ∈ I s , ∀t ∈ {i, ..., i + mt s -1} (4.10) s∈S γ t sm 1 ∀m ∈ M, ∀t ∈ T (4.11) sa ∀a ∈ A, ∀s ∈ S, ∀j ∈ J s , ∀t ∈ {j, ..., j + at evs -1} (4.12) s∈S λ t sa 1 ∀a ∈ A, ∀t ∈ T (4.13) evs∈Evs p evs .u s a λ t sa ∀a ∈ A, ∀s ∈ S, ∀j ∈ J s , ∀t ∈ {j, ..., j + at evs -1} (4.18)

  ). The algorithm iterates as long as the total QoS degradation time for SBP exceeds the maximum allowed QoS degradation time (cf. line 6). It operates in two steps: First, it adds a new planner by invoking the P_Assignment procedure (cf. lines 7-8). Second, if the maximum allowed QoS degradation time is still not respected (cf. line 9), it calculates the new QoS degradation time whether we add: (i) a new planner by invoking the P_Assignment procedure, and (ii) a new executor by invoking the E_Assignment procedure (cf. lines[START_REF] Mell | Sp 800-145. the nist definition of cloud computing[END_REF][START_REF] Wu | Sla-based resource provisioning for hosted software-as-a-service applications in cloud computing environments[END_REF]. Then the algorithm adds the component (planner or executor) that further reduces the total QoS degradation time for SBP (cf. lines[START_REF] Enterprise | Cloud Computing Survey[END_REF][START_REF] Papazoglou | Blueprinting the cloud[END_REF][START_REF] White | Introduction to bpmn[END_REF][START_REF] Booch | Unified Modeling Language User Guide, The (2Nd Edition) (Addison-Wesley Object Technology Series[END_REF][START_REF] Florio | Gru: An approach to introduce decentralized autonomic behavior in microservices architectures[END_REF][START_REF] Hoenisch | Cost-efficient scheduling of elastic processes in hybrid clouds[END_REF][START_REF] Mastelic | Predicting resource allocation and costs for business processes in the cloud[END_REF][START_REF] Rekik | A linear program for optimal configurable business processes deployment into cloud federation[END_REF][START_REF] Hadded | An efficient optimization algorithm of autonomic managers in service-based applications[END_REF]. The first step of the algorithm consists in ensuring that the number of planners is greater than or equal to the number of executors in order not to push any planner to link to more than one executor.

	16	else
	17	n e ← n e + 1;

Algorithm 4.3: P-E_Assignment procedure Data: mdt Result: P, n p , E, n e begin 1 tdt ← 0; /*tdt is the total QoS degradation time for the SBP*/ 2 n p , n e ← 1; 3 for s ∈ S do 4 P [s], E[s] ← 1; 5 tdt ← tdt + P T [s] + ET [s]; 6 while (tdt > mdt) do 7 n p ← n p + 1; 8 tdt, P ← P_Assignment(n p ); 9 if tdt > mdt then 10 tdt p , I ← P_Assignment(n p + 1); 11 tdt e , set ← E_Assignment(n e + 1, tdt); 12 if (tdt p < tdt e ) then 13 n p ← n p + 1; 14 tdt ← tdt p ; 15 P ← I; 18 tdt ← tdt e ; 19 for s ∈ set do 20 E[s] ← n e ;

  (cf. line 19).

	Algorithm 4.5: E_Assignment procedure
		Data: n e , tdt
		Result: tdt, Services
		begin
	1	Services ← ∅;
	2	mintdt ← tdt;
	3	repeat
	4	tdt ← mintdt;

5 mintdt ← +∞; 6 for set ∈ P Sets do 7 I ← E; 8 for s ∈ set do 9 E[s] ← n e ; /*n e is the new executor number*/ 10 tdt ← QoSDegradationTime(); 11 E ← I; 12 if tdt < mindt then 13 mintdt ← tdt; 14 BestSet ← set; 15 if mintdt < tdt then 16 for s ∈ BestSet do 17 E[s] ← n e ; 18 Services ← Services ∪ BestSet; 19 until mintdt tdt;

  .1.

	Information	Range
	Number of services	[10 -100]
	Number of edges	[(n -1) -3.2 × (n -1)]
	Execution time of a service	[5 -30]
	Data transfer time between services	[5 -30]
	Monitoring time	[2 -10]
	Monitoring frequency	[1 -5]
	Analysis time	[2 -10]
	Analysis frequency	[1 -5]
	Planning time	[2 -10]
	Adaptation time	[2 -10]
	Maximum allowed QoS degradation time	[0 -50]

Table 4 .

 4 1: Characteristics of data inputs of generated SBP graphs and AM components.

  guarantees that each AM is placed (deployed) on only one VM.

	min	cintra.data.x s m .z s m .(1 -y s m ) +	cinter.data.x s m .(1 -z s m ) (5.1)
	s∈S m∈M	s∈S m∈M
	Subject to:
	x s m = 1	∀s ∈ S	(5.2)
	m∈M
	x s m <= 1	∀m ∈ M, ∀P ∈ P S	(5.3)
	s∈P
	z∈Z v∈Vz

  w kjhi takes 1 if the candidate AM component j ∈ C of type k ∈ T (or service i ∈ C) is linked/assigned to the candidate AM component i ∈ C of type h ∈ T (or service i ∈ C), and 0 otherwise.• α ki takes 1 if the candidate AM component i ∈ C of type k ∈ T is used by at leastone AM component/service, and 0 otherwise. δ sihjv takes 1 if service i ∈ C is assigned to the candidate AM component j ∈ C of type h ∈ T and j is placed in VM v ∈ V into AZ z ∈ Z, and 0 otherwise.• γ nt takes 1 if instance n ∈ I of VM v ∈ V into AZ z ∈ Z is allocated to at leastone AM component at time t ∈ {0, ..., tet}, and 0 otherwise. The resource constraints impose that VM capacities in terms of RAM and CPU should satisfy the AM components and the services deployed on it:∀z ∈ Z, ∀v ∈ V z , n ∈ I zv , ∀S ∈ P S, ∀t ∈ [0..tet] The placement constraint (5.4) imposes that each AM component should be placed on one (and only one) VM. Constraint 5.5 ensures that x sjn takes 1

	Constraints
	The objective functions are subject to the following set of constraints:
	(a) Resource constraints: k∈S r∈T j∈C	rcpu kr .x rjn .β skrjt cpu v	(5.1)

and 0 otherwise.

• y kihj takes 1 if the candidate AM component i ∈ C of type k ∈ T (or service i ∈ C) and the candidate AM component j ∈ C of type h ∈ T (or service j ∈ C) are in the same AZ, and 0 otherwise.

• z kihj takes 1 if the candidate AM component i ∈ C of type k ∈ T (or service i ∈ C) and the candidate AM component j ∈ C of type h ∈ T (or service j ∈ C)

are placed in the same VM, and 0 otherwise. • • β sihjt takes 1 if service i ∈ C is assigned to the candidate AM component j ∈ C of type h ∈ T at time t ∈ {0, ..., tet}, and 0 otherwise. • k∈S rcpu k .x skn + k∈S rram k .x skn + k∈S r∈T j∈C rram kr .x rjn .β skrjt ram v (5.2) (b) QoS constraint: The QoS constraint imposes the minimum availability level required by an AM component: avail i .x rjn ≥ ravail r .x rjn ∀z ∈ Z, ∀v ∈ V z , ∀n ∈ I zv , ∀r ∈ T, ∀j ∈ C (5.3) (c) Placement constraints:

  , and (5.21) guarantee that each component is assigned to at most one service at a time.∀z ∈ Z, ∀v ∈ V z , ∀n ∈ I zv , ∀j, k, h, l, o ∈ C w shmk .x mkn β shmkt ∀j ∈ I h ,∀t ∈ {j, .., j + t mv -1} (5.8) ac j .w sjmo .w moal .w alph .w phek .x ekn β sjekt ∀t ∈ [s j ..e j ] (5.20) We add constraints (5.22-5.38) which ensure the linear relationships among the decision variables. ∀z ∈ Z, ∀v ∈ V z , ∀n ∈ I zv , ∀i, j, k, h, o ∈ C δ simjv = w simk .x mkn (5.22) δ siajv = w simk .w mkaj .x ajn (5.23) δ sipjv = w simk .w mkah .w ahpj .x pjn (5.24)δ siejv = w simk .w mkah .w ahpo .w poej .x ejn (5.25) It consists in finding the minimum deployment cost of AM components that will be used to manage the given SBP, which includes: (i) the sum of VM allocation costs in order to execute these components, (ii) the sum of intra-AZ communication costs (the data transfer cost in the same VM is null), and (iii) the sum of inter-AZ communication costs. .γ nt .(1 -alloc nt ) + k∈T ∪{s} i∈C h∈T ∪{s} j∈C cintra. d kihj .w kihj .y kihj .(1 -z kihi ) + k∈T ∪{s} i∈C h∈T ∪{s} j∈C cinter.d kihj .w kihj .(1 -y kihj )

	w shmk = 1		(5.6)
	k∈C
	w shmk α mk	tet	(5.7)
	Min cost =	cu
	h∈C equation (5.24) in constraint (5.16), and equation (5.25) in constraint (5.20). Thus, β shmkt 1 ∀t ∈ [0..tet] (5.9) We replace equation (5.22) in constraint (5.8), equation (5.23) in constraint (5.12), z∈Z v∈Vz n∈Izv t=0
	w mhak = α mh constraints (5.8), (5.12), (5.16) and (5.20) respectively become:	(5.10)
	k∈C
	w mhak α ak ∀k ∈ C, ∀h ∈ C		(5.11)
	w phek = α ph δ shmkv β shmkt	∀j ∈ I ejsi + 3	(5.18) (5.34)
	k∈C w phek α ek β sihjt + x hjn ≤ γ nt + 1	∀h ∈ T	(5.19) (5.35)
	∀z ∈ Z, ∀v ∈ V z , ∀n ∈ I zv , ∀k, h ∈ T ∪ {s}
	ac j ∈Ac j β sjekt 1 x kizvn + x hjzvn ≤ z kihj + 1	∀t ∈ t ∈ [0..tet]	(5.21) (5.36)
	j∈C
	x kin + x hjn -2y kihj ≥ 0	(5.37)
	v∈Vz n∈I

ev l ∈Ev l p ev l .w slmh .w mhak .x akn β slakt ∀j ∈ J l , ∀t ∈ {j, .., j + t av -1} (5.12) j∈C β sjakt 1 ∀t ∈ [0..tet] (5.13) k∈C w ahpk = α ah (5.14) w ahpk α pk (5.15) ac j ∈Ac j p ac j .w sjmo .w moah .w ahpk .x pkn β sjpkt ∀t ∈ [s j ..e j ] (5.16) j∈C β sjpkt 1 ∀t ∈ [0..tet] (5.17) p (e) Linearity constraints: h , ∀t ∈ {j, .., j + t mv -1} (5.26) ev h ∈Ev h p ev h .δ shakv β shakt ∀j ∈ J h , ∀t ∈ {j, .., j + t av -1} (5.27) ev h ∈Ev h p ev h .δ shpkv β shpkt ∀t ∈ [s h ..e h ] (5.28) ev h ∈Ev h p ev h .δ shekv β shekt ∀t ∈ [s h ..e h ] (5.29) Then we must add the following logical constraints: ∀z ∈ Z, ∀v ∈ V z , ∀n ∈ I zv , ∀i, j, k, h, o ∈ C w simk + x mkn ≤ δ simkv + 1 (5.30) w simh + w mhak + x akn ≤ δ siakv + 2 (5.31) w simj + w mjah + w ahpk + x pkn ≤ δ sipkv + 3 (5.32) w simo + w moaj + w ajph + w phek + x ekn ≤ δ siekv + 4 (5.33) w simk + w mkah + w ahpo + w poej ≤ w v∈Vz n∈I x kin + x hjn -2y kihj ≤ 1 (5.38) Cost objective function: v

aws.amazon.com/fr/

cloud.google.com/compute

www.cloudfoundry.org

azure.microsoft.com

www.salesforce.com

http://www.netsuite.com/portal/home.shtml

The IaaS Cloud is inspired from the Amazon EC2 https://aws.amazon.com/fr/ec2/pricing/ondemand/

The IaaS Cloud is inspired from the Amazon EC2 https://aws.amazon.com/fr/ec2/pricing/ondemand/

Acknowledgements

"

Chapter 4

Autonomic Managers Components Optimization in Timed SBPs

List of Publications

if InitialMeta-node(u) then

to the resulting sets of parallel services (cf. lines 26-27).

M-A-P-E_Assignment Algorithm

M-A-P-E_Assignment is mainly based on two procedures, called M/A_Assignment and P-E_Assignment. The M/A_Assignment procedure, whose pseudo-code is given in Algorithm 4.6, aims to assign a minimum number of monitors and analyzers to the SBP services. The P-E_Assignment procedure, whose pseudo-code is given in Chapter 5

Placement of Autonomic Managers for the management of SBPs in the Cloud Record in CandidateVMs the VMs that have a free capacity ≥ cap(c) during the execution period of c; the considered SBPs. We note that the gap between the two solutions does not exceed 18.20%. It means that our solution is very close to the optimal solution (Figure 5.7). As for the execution time, the results presented in Figures 5.8 and 5.9 show that its execution time is reasonable. Indeed, it does not exceed 0.15 second, whereas CPLEX takes more than two hours to solve the problem, and whenever the number of SBP services goes beyond 14, the solver can not find the optimal solution due to a problem of memory.

Pl

Deployment cost($)

VMs Capacities

The proposed Approach Optimal Chapter 6

Conclusion and Future Works

The research problem of this thesis is expressed by this interrogation: How to determine the optimal Cloud resource allocation for the management of SBPs? Previous chapters presented in details our solutions to answer this question. In this chapter, we summarize our contributions in Section 6.1 and present the future work in Section 6.2.

Contributions

Cloud Computing is an emerging paradigm in Information Technologies (IT). It refers to a model for the provision of every network-available resource "X" as a service "XaaS" based on the pay-per-use economic model. Cloud environments being increasingly used for hosting and executing applications that are described according to Service-Oriented Architecture (SOA) such as service-based business processes (SBPs) that we targeted in our work. Executing SBPs in dynamic environments requires autonomic management to cope with the dynamic evolution of Cloud environments with minimal human intervention. Autonomic management consists of a number of controlling devices known as Autonomic Managers (AMs).

Management of an SBP in Cloud environments has not received the needed attention in research work, particularly optimizing Cloud resource allocation for the management of SBPs that face many challenges : (1) allocating the adequate number of AMs to manage the process services and (2) allocating the required Cloud resource to host and execute these AMs.

In this regard, as a first contribution, we presented an approach that efficiently manages SBPs such that the number of used AMs is minimized while avoiding management bottlenecks. To do this, we modeled SBPs using directed graphs. We proposed a deterministic optimization model to solve this problem. We also suggested two main algorithms that provide a near-optimal solution for both SBPs that can be represented as graphs with and without cycles. An illustrative example of each algorithm is then provided. The dif-