Understanding user and system behavior is most vital for designing efficient systems. Most systems are designed with certain user workload in mind. However, such workloads evolve over time, or the underlying hardware assumptions change. Further, most modern systems are not built or deployed in isolation, they interact with other systems whose behavior might not be exactly understood. Thus in order to understand the performance of a system, it must be inspected closely while user workloads are running. Such close inspection must be done with minimum disturbance to the user workload. Thus tracing or collection of all the user and system generated events becomes an important approach in gaining comprehensive insight in user behavior. As part of this work, we have three major contributions. We designed and implemented an in-depth block level I/O tracer, which would collect block level information like sector number, size of the I/O, actual contents of the I/O, along with certain file system information like filename, and offset in the file, for every I/O request. Next, to minimize the impact of the tracing to the running workload, we introduce and implement a sampling mechanism which traces fewer I/O requests. We validate that this sampling preserves certain I/O access patterns. Finally, as one of the application of our tracer, we use it as a crucial component of a system designed to do VM placements according to user workload. / Master of Science

The need for high computing resources is on the rise, despite the exponential increase of the computing capacity of workstations, the proliferation of mobile devices, and the omnipresence of data centers with massive server farms that housed tens (if not hundreds) of thousands of powerful servers. This is mainly due to the unprecedented increase in the number of Internet users worldwide and the Internet of Things (IoTs). So far, Cloud Computing has been providing the necessary computing infrastructures for applications, including IoT applications. However, the current cloud infrastructures that are based on dedicated datacenters are expensive to set-up; running the infrastructure needs expertise, a lot of electrical power for cooling the facilities, and redundant supply of everything in a data center to provide the desired resilience. Moreover, the current centralized cloud infrastructures will not suffice for IoT's network intensive applications with very fast response requirements. Alternative cloud computing models that depend on spare resources of volunteer computers are emerging, including volunteer cloud computing, in addition to the conventional data center based clouds. These alternative cloud models have one characteristic in common -- they do not rely on dedicated data centers to provide the cloud services. Volunteer clouds are opportunistic cloud systems that run over donated spare resources of volunteer computers. On the one hand, volunteer clouds claim numerous outstanding advantages: affordability, on-premise, self-provision, greener computing (owing to consolidate use of existent computers), etc. On the other hand, full-fledged implementation of volunteer cloud computing raises unique technical and research challenges: management of highly dynamic and heterogeneous compute resources, Quality of Service (QoS) assurance, meeting Service Level Agreement (SLA), reliability, security/trust, which are all made more difficult due to the high dynamics and heterogeneity of the non-dedicated cloud hosts. This dissertation investigates the resource management aspect of volunteer cloud computing. Due to the intermittent availability and heterogeneity of computing resource involved, resource management is one of the challenging tasks in volunteer cloud computing. The dissertation, specifically, focuses on the Resource Discovery and VM Placement tasks of resource management. The resource base over which volunteer cloud computing depends on is a scavenged, sporadically available, aggregate computing power of individual volunteer computers. Delivering reliable cloud services over these unreliable nodes is a big challenge in volunteer cloud computing. The fault tolerance of the whole system rests on the reliability and availability of the infrastructure base. This dissertation discusses the modelling of a fault tolerant prediction based resource discovery in volunteer cloud computing. It presents a multi-state semi-Markov process based model to predict the future availability and reliability of nodes in volunteer cloud systems. A volunteer node is modelled as a semi-Markov process, whose future state depends only on its current state. This exactly matches with a key observation made in analyzing the traces of personal computers in enterprises that the daily patterns of resource availability are comparable to those in the most recent days. The dissertation illustrates how prediction based resource discovery enables volunteer cloud systems to provide reliable cloud services over the unreliable and non-dedicated volunteer hosts with empirical evidences. VM placement algorithms play crucial role in Cloud Computing in fulfilling its characteristics and achieving its objectives. In general, VM placement is a challenging problem that has been extensively studied in conventional Cloud Computing context. Due to its divergent characteristics, volunteer cloud computing needs a novel and unique way of solving the existing Cloud Computing problems, including VM placement. Intermittent availability of nodes, unreliable infrastructure, and resource constrained nodes are some of the characteristics of volunteer cloud computing that make VM placement problem more complicated. In this dissertation, we model the VM placement problem as a \textit{Bounded 0-1 Multi-Dimensional Knapsack Problem}. As a known NP-hard problem, the dissertation discusses heuristic based algorithms that takes the typical characteristics of volunteer cloud computing into consideration, to solve the VM placement problem formulated as a knapsack problem. Three algorithms are developed to meet the objectives and constraints specific to volunteer cloud computing. The algorithms are tested on a real volunteer cloud computing test-bed and showed a good performance results based on their optimization objectives. The dissertation also presents the design and implementation of a real volunteer cloud computing system, cuCloud, that bases its resource infrastructure on donated computing resource of computers. The need for the development of cuCloud stems from the lack of experimentation platform, real or simulation, that specifically works for volunteer cloud computing. The cuCloud is a system that can be called a genuine volunteer cloud computing system, which manifests the concept of ``Volunteer Computing as a Service'' (VCaaS), with a particular significance in edge computing and related applications. In the course of this dissertation, empirical evaluations show that volunteer clouds can be used to execute range of applications reliably and efficiently. Moreover, the physical proximity of volunteer nodes to where applications originate, edge of the network, helps them in reducing the round trip time latency of applications. However, the overall computing capability of volunteer clouds will not suffice to handle highly resource intensive applications by itself. Based on these observations, the dissertation also proposes the use of volunteer clouds as a resource fabric in the emerging Edge Computing paradigm as a future work.

This dissertation focuses on developing algorithms and systems to improve the efficiency of operating mega datacenters with hundreds of thousands of servers. In particular, it seeks to address two challenges: First, how to distribute the workload among the set of datacenters geographically deployed across the wide area? Second, how to manage the server resources of datacenters using virtualization technology? In the first part, we consider the workload management problem in geo-distributed datacenters. We first present a novel distributed workload management algorithm that jointly considers request mapping, which determines how to direct user requests to an appropriate datacenter for processing, and response routing, which decides how to select a path among the set of ISP links of a datacenter to route the response packets back to a user. In the next chapter, we study some key aspects of cost and workload in geo-distributed datacenters that have not been fully understood before. Through extensive empirical studies of climate data and cooling systems, we make a case for temperature aware workload management, where the geographical diversity of temperature and its impact on cooling energy efficiency can be used to reduce the overall cooling energy. Moreover, we advocate for holistic workload management for both interactive and batch jobs, where the delay-tolerant elastic nature of batch jobs can be exploited to further reduce the energy cost. A consistent 15% to 20% cooling energy reduction, and a 5% to 20% overall cost reduction are observed from extensive trace-driven simulations. In the second part of the thesis, we consider the resource management problem in virtualized datacenters. We design Anchor, a scalable and flexible architecture that efficiently supports a variety of resource management policies. We implement a prototype of Anchor on a small-scale in-house datacenter with 20 servers. Experimental results and trace-driven simulations show that Anchor is effective in realizing various resource management policies, and its simple algorithms are practical to solve virtual machine allocation with thousands of VMs and servers in just ten seconds.

This dissertation focuses on developing algorithms and systems to improve the efficiency of operating mega datacenters with hundreds of thousands of servers. In particular, it seeks to address two challenges: First, how to distribute the workload among the set of datacenters geographically deployed across the wide area? Second, how to manage the server resources of datacenters using virtualization technology? In the first part, we consider the workload management problem in geo-distributed datacenters. We first present a novel distributed workload management algorithm that jointly considers request mapping, which determines how to direct user requests to an appropriate datacenter for processing, and response routing, which decides how to select a path among the set of ISP links of a datacenter to route the response packets back to a user. In the next chapter, we study some key aspects of cost and workload in geo-distributed datacenters that have not been fully understood before. Through extensive empirical studies of climate data and cooling systems, we make a case for temperature aware workload management, where the geographical diversity of temperature and its impact on cooling energy efficiency can be used to reduce the overall cooling energy. Moreover, we advocate for holistic workload management for both interactive and batch jobs, where the delay-tolerant elastic nature of batch jobs can be exploited to further reduce the energy cost. A consistent 15% to 20% cooling energy reduction, and a 5% to 20% overall cost reduction are observed from extensive trace-driven simulations. In the second part of the thesis, we consider the resource management problem in virtualized datacenters. We design Anchor, a scalable and flexible architecture that efficiently supports a variety of resource management policies. We implement a prototype of Anchor on a small-scale in-house datacenter with 20 servers. Experimental results and trace-driven simulations show that Anchor is effective in realizing various resource management policies, and its simple algorithms are practical to solve virtual machine allocation with thousands of VMs and servers in just ten seconds.

L'objectif de cette thèse est de présenter de nouveaux algorithmes de placement de machines virtuelles (VMs) à fin d’optimiser le coût et les émissions de carbone dans les Clouds distribués. La thèse se concentre d’abord sur la rentabilité des Clouds distribués, et développe ensuite les raisons d’optimiser les coûts ainsi que les émissions de carbone. La thèse comprend deux principales parties: la première propose, développe et évalue les algorithmes de placement statiques de VMs (où un premier placement d'une VM détient pendant toute la durée de vie de la VM). La deuxième partie propose des algorithmes de placement dynamiques de VMs où le placement initial de VM peut changer dynamiquement (par exemple, grâce à la migration de VMs et à leur consolidation). Cette thèse comprend cinq contributions. La première contribution est une étude de l'état de l'art sur la répartition des coûts et des émissions de carbone dans les environnements de clouds distribués. La deuxième contribution propose une méthode d'allocation des ressources, appelée NACER, pour les clouds distribués. L'objectif est de minimiser le coût de communication du réseau pour exécuter une tâche dans un cloud distribué. La troisième contribution propose une méthode de placement VM (appelée NACEV) pour les clouds distribués. NACEV est une version étendue de NACER. Tandis que NACER considère seulement le coût de communication parmi les DCs, NACEV optimise en même temps les coûts de communication et de calcul. Il propose également un algorithme de cartographie pour placer des machines virtuelles sur des machines physiques (PM). La quatrième contribution présente une méthode de placement VM efficace en termes de coûts et de carbone (appelée CACEV) pour les clouds distribués verts. CACEV est une version étendue de NACEV. En plus de la rentabilité, CACEV considère l'efficacité des émissions de carbone pour les clouds distribués. Pour obtenir une meilleure performance, la cinquième contribution propose une méthode dynamique de placement VM (D-CACEV) pour les clouds distribués. D-CACEV est une version étendue de notre travail précédent, CACEV, avec des chiffres supplémentaires, une description et également des mécanismes de migration de VM en direct. Nous montrons que notre mécanisme conjoint de réallocation-placement de VM peut constamment optimiser à la fois le coût et l'émission de carbone dans un cloud distribué / Virtual machine (VM) placement (i.e., resource allocation) method has a direct effect on both cost and carbon emission. Considering the geographic distribution of data centers (DCs), there are a variety of resources, energy prices and carbon emission rates to consider in a distributed cloud, which makes the placement of VMs for cost and carbon efficiency even more critical and complex than in centralized clouds. The goal of this thesis is to present new VM placement algorithms to optimize cost and carbon emission in a distributed cloud. It first focuses on cost efficiency in distributed clouds and, then, extends the goal to optimization of both cost and carbon emission at the same time. Thesis includes two main parts. The first part of thesis proposes, develops and evaluates static VM placement algorithms to reach the mentioned goal where an initial placement of a VM holds throughout the lifetime of the VM. The second part proposes dynamic VM placement algorithms where the initial placement of VMs is allowed to change (e.g., through VM migration and consolidation). The first contribution is a survey of the state of the art on cost and carbon emission resource allocation in distributed cloud environments. The second contribution targets the challenge of optimizing inter-DC communication cost for large-scale tasks and proposes a Network-Aware Cost-Efficient Resource allocation method, called NACER, for distributed clouds. The goal is to minimize the network communication cost of running a task in a distributed cloud by selecting the DCs to provision the VMs in such a way that the total network distance (hop count or any reasonable measure) among the selected DCs is minimized. The third contribution proposes a Network-Aware Cost Efficient VM Placement method (called NACEV) for Distributed Clouds. NACEV is an extended version of NACER. While NACER only considers inter-DC communication cost, NACEV optimizes both communication and computing cost at the same time and also proposes a mapping algorithm to place VMs on Physical Machines (PMs) inside of the selected DCs. NACEV also considers some aspects such as heterogeneity of VMs, PMs and switches, variety of energy prices, multiple paths between PMs, effects of workload on cost (energy consumption) of cloud devices (i.e., switches and PMs) and also heterogeneity of energy model of cloud elements. The forth contribution presents a Cost and Carbon Emission-Efficient VM Placement Method (called CACEV) for green distributed clouds. CACEV is an extended version of NACEV. In addition to cost efficiency, CACEV considers carbon emission efficiency and green distributed clouds. It is a VM placement algorithm for joint optimization of computing and network resources, which also considers price, location and carbon emission rate of resources. It also, unlike previous contributions of thesis, considers IaaS Service Level Agreement (SLA) violation in the system model. To get a better performance, the fifth contribution proposes a dynamic Cost and Carbon Emission-Efficient VM Placement method (D-CACEV) for green distributed clouds. D-CACEV is an extended version of our previous work, CACEV, with additional figures, description and also live VM migration mechanisms. We show that our joint VM placement-reallocation mechanism can constantly optimize both cost and carbon emission at the same time in a distributed cloud

L’objectif de cette thèse est de présenter de nouveaux algorithmes de répartition des ressources sous la forme de machines virtuelles (VMs) et fonction de réseau virtuel (VNFs) dans les Clouds et réseaux de diffusion de contenu (CDNs). La thèse comprend deux principales parties: la première se concentre sur la rentabilité des Clouds distribués, et développe ensuite les raisons d’optimiser les coûts ainsi que les émissions de carbone. Cette partie comprend quatre contributions. La première contribution est une étude de l’état de l’art sur la répartition des coûts et des émissions de carbone dans les environnements de clouds distribués. La deuxième contribution propose une méthode d’allocation des ressources, appelée NACER, pour les clouds distribués. La troisième contribution présente une méthode de placement VM efficace en termes de coûts et de carbone (appelée CACEV) pour les clouds distribués verts. Pour obtenir une meilleure performance, la quatrième contribution propose une méthode dynamique de placement VM (D-CACEV) pour les clouds distribués. La deuxième partie propose des algorithmes de placement de VNFs dans les Clouds et réseaux de CDNs pour optimiser les coûts. Cette partie comprend cinq contributions. Une étude de l’état de l’art sur les solutions proposées est le but de la première contribition. La deuxième contribution propose une méthode d’allocation des ressources, appelée CCVP, pour le provisionnement de service réseau dans les clouds et réseaux de ISP. La troisième contribution implémente le résultat de l’algorithme CCVP dans une plateforme réelle. La quatrième contribution considère l’effet de la permutation de VNFs dans les chaîne de services et la cinquième contribution explique le placement de VNFs pour les services à valeur ajoutée dans les CDNs / High energy costs and carbon emissions are two significant problems in distributed computing domain, such as distributed clouds and Content Delivery Networks (CDNs). Resource allocation methods (e.g., in form of Virtual Machine (VM) or Virtual Network Function (VNF) placement algorithms) have a direct effect on cost, carbon emission and Quality of Service (QoS). This thesis includes three related parts. First, it targets the problem of resource allocation (i.e., in the form of network aware VM placement algorithms) for distributed clouds and proposes cost and carbon emission efficient resource allocation algorithms for green distributed clouds. Due to the similarity of the network-aware VM placement problem in distributed clouds with a VNF placement problem, the second part of the thesis, getting experience from the first part, proposes a new cost efficient resource allocation algorithm (i.e., VNF placement) for network service provision in data centers and Internet Service Provider (ISP) network. Finally, the last part of the thesis presents new cost efficient resource allocation algorithms (i.e., VNF placement) for value-added service provisioning in NFV-based CDNs

Les opérateurs de cloud IaaS (Infrastructure as a Service) proposent à leurs clients des ressources virtualisées (CPU, stockage et réseau) sous forme de machines virtuelles (VM). L’explosion du marché du cloud les a contraints à optimiser très finement l’utilisation de leurs centres de données afin de proposer des services attractifs à moindre coût. En plus des investissements liés à l’achat des infrastructures et de leur coût d’utilisation, la consommation énergétique apparaît comme un point de dépense important (2% de la consommation mondiale) et en constante augmentation. Sa maîtrise représente pour ces opérateurs un levier très intéressant à exploiter. D’un point de vue technique, le contrôle de la consommation énergétique s’appuie essentiellement sur les méthodes de consolidation. Or la plupart d'entre elles ne prennent en compte que l’utilisation CPU des machines physiques (PM) pour le placement de VM. En effet, des études récentes ont montré que les systèmes de stockage et les E/S disque constituent une part considérable de la consommation énergétique d’un centre de données (entre 14% et 40%). Dans cette thèse nous introduisons un nouveau modèle autonomique d’optimisation de placement de VM inspiré de MAPE-K (Monitor, Analyze, Plan, Execute, Knowledge), et prenant en compte en plus du CPU, les E/S des VM ainsi que les systèmes de stockage associés. Ainsi, notre première contribution est relative au développement d’un outil de trace des E/S de VM multi-niveaux. Les traces collectées alimentent, dans l’étape Analyze, un modèle de coût étendu dont l’originalité consiste à prendre en compte le profil d’accès des VM, les caractéristiques du système de stockage, ainsi que les contraintes économiques de l’environnement cloud. Nous analysons par ailleurs les caractéristiques des deux principales classes de stockage, pour aboutir à un modèle hybride exploitant au mieux les avantages de chacune. En effet, les disques durs magnétiques (HDD) sont des supports de stockage à la fois énergivores et peu performants comparés aux unités de calcul. Néanmoins, leur prix par gigaoctet et leur longévité peuvent jouer en leur faveur. Contrairement aux HDD, les disques SSD à base de mémoire flash sont plus performants et consomment peu d’énergie. Leur prix élevé par gigaoctet et leur courte durée de vie (comparés aux HDD) représentent leurs contraintes majeures. L’étape Plan a donné lieu, d’une part, à une extension de l'outil de simulation CloudSim pour la prise en compte des E/S des VM, du caractère hybride du système de stockage, ainsi que la mise en oeuvre du modèle de coût proposé dans l'étape Analyze. Nous avons proposé d’autre part, plusieurs heuristiques se basant sur notre modèle de coût et que nous avons intégrées dans CloudSim. Nous montrons finalement que notre approche permet d’améliorer d’un facteur trois le coût de placement de VM obtenu par les approches existantes. / IaaS cloud providers offer virtualized resources (CPU, storage, and network) as Virtual Machines(VM). The growth and highly competitive nature of this economy has compelled them to optimize the use of their data centers, in order to offer attractive services at a lower cost. In addition to investments related to infrastructure purchase and cost of use, energy efficiency is a major point of expenditure (2% of world consumption) and is constantly increasing. Its control represents a vital opportunity. From a technical point of view, the control of energy consumption is mainly based on consolidation approaches. These approaches, which exclusively take into account the CPU use of physical machines (PM) for the VM placement, present however many drawbacks. Indeed, recent studies have shown that storage systems and disk I/O represent a significant part of the data center energy consumption (between 14% and 40%).In this thesis we propose a new autonomic model for VM placement optimization based on MAPEK (Monitor, Analyze, Plan, Execute, Knowledge) whereby in addition to CPU, VM I/O and related storage systems are considered. Our first contribution proposes a multilevel VM I/O tracer which overcomes the limitations of existing I/O monitoring tools. In the Analyze step, the collected I/O traces are introduced in a cost model which takes into account the VM I/O profile, the storage system characteristics, and the cloud environment constraints. We also analyze the complementarity between the two main storage classes, resulting in a hybrid storage model exploiting the advantages of each. Indeed, Hard Disk Drives (HDD) represent energy-intensive and inefficient devices compared to compute units. However, their low cost per gigabyte and their long lifetime may constitute positive arguments. Unlike HDD, flash-based Solid-State Disks (SSD) are more efficient and consume less power, but their high cost per gigabyte and their short lifetime (compared to HDD) represent major constraints. The Plan phase has initially resulted in an extension of CloudSim to take into account VM I/O, the hybrid nature of the storage system, as well as the implementation of the previously proposed cost model. Secondly, we proposed several heuristics based on our cost model, integrated and evaluated using CloudSim. Finally, we showed that our contribution improves existing approaches of VM placement optimization by a factor of three.