<  Back to the Polytechnique Montréal portal

Optimisation de l'empreinte carbone dans un environnement intercloud : modèles et méthodes

Valérie Danielle Justafort

Ph.D. thesis (2015)

Open Access document in PolyPublie
Open Access to the full text of this document
Terms of Use: All rights reserved
Download (3MB)
Show abstract
Hide abstract


The last decade or so has seen a rapid rise in cloud computing usage, which has led to the dematerialization of data centers. The higher computing power and storage, combined with a greater usage flexibility, have promoted the outsourcing of data to remote servers, allowing users to overcome the burden of traditional IT tools, while having access to a wider range of online services that are charged on based on usage. Particularly, in the case of an infrastructure service model, the client is given access to a physical infrastructure where he can rent physical servers to run their applications, which are encapsulated in VMs. However, the emergence of cloud service and its wide adoption impose new challenges on infrastructure providers. They have to optimize the underlying existing infrastructure by identifying efficient mechanisms for assigning user requests to servers and data centers, while satisfying performance and security constraints, as imposed by the clients. Faced with an increasing demand, providers have to invest significant capital in order to increase their hosting offers in several geographic areas, to provide the required Quality of Service (QoS). The increased use of data centers also has a huge bearing on the operating costs and energy consumption, as operating expenses have quickly exceeded the investment. Therefore, several authors have been tackling the placement of loads in a cloud environment by developing tools to aid in the decision-making. Most of the proposed solutions are guided by financial aspects to increase profits by determining the best mapping between the basic needs of the client and the available infrastructure, in order to meet the QoS constraints while maximizing the efficiency and the use of resources. However, while cloud computing represents a great opportunity for both individuals and businesses, its widespread adoption is slowed by concerns regarding its global ecological impact. The excessive use of data centers, as well as their management and maintenance, require huge amounts of electric power, thus accelerating the global warming process. Therefore, before choosing a cloud solution, some users will take into consideration that environmental impact. This, in turn, forces cloud providers to consider the "green" aspect of their infrastructure by developing new ways of assigning loads that reduce the carbon footprint of their data centers in order for cloud computing to be both a technological and an ecological success. Several works have recently been published that aim to reduce the environmental impact of clouds. The first ones have focused on reducing the carbon footprint of a single data center by optimizing the consumed energy. However, in the context of an InterCloud environment composed of different data centers that are geographically distributed and powered by renewable energy sources or not, the total energy consumed cannot reflect the carbon footprint of that said environment. That's why subsequent research has been focusing on optimizing the environmental impact of an InterCloud where the heterogeneity of the infrastructure is taken into account. However, only the VM placement process has been optimized with no consideration to improving data center energy efficiency, network power consumption or customer requirements, as far as application performance and data security are concerned. To this end, this thesis proposes a framework for assigning applications to an InterCloud with the view of minimizing the carbon footprint of such a computing environment. In order to address this issue, the problem is treated holistically, jointly optimizing the VM placement process, the traffic routing and a cooling management technique that considers the dynamic behavior of the IT fans. Various aspects, such the processing power, the network resource consumption and the energy efficiency, will be simultaneously optimized, while satisfying customer requirements. The work is carried out in three phases. First, we propose an optimization model for placing standalone VMs, in order to reduce the environmental impact of a set of data centers. The carbon footprint of the proposed model improves the energy consumption of existing approaches by combining both the optimization of the VM placement process and the energy efficiency of data centers. This latter process determines, for each active data center, the optimal temperature to be provided by the cooling system so as to find a compromise between the energy gains associated with the cooling and the increased power consumption of the server fans, at high temperatures. In order to add some realism to the model, customer requirements are also considered, in terms of application performance, security and redundancy. An analysis of the monotony and the convexity of the resulting nonlinear model was conducted to highlight the importance surrounding the determination of the optimal temperature value. Subsequently, the problem is transformed into a linear model and solved optimally with a mathematical solver, using integer linear programming. To demonstrate the relevance of the proposed optimization model in terms of carbon footprint, an analysis of the cost structure and the impact of the load is carried out. In order to better highlight the results, a simplified version of the model, free from any client requirements, is also considered. This same simplified model is also compared with different other techniques that optimize the carbon footprint both within a single data center and across an InterCloud environment. The results demonstrate that the proposed model can yield savings of up to 65%, in terms of carbon footprint cost. In addition, to highlight the effectiveness of the proposed model when placing VMs while satisfying clients and performance constraints, the simplified model is compared with the global model that incorporates customer requirements. Although the model without constraints usually generates smaller carbon footprint costs, its result is not as interesting as it may seem, because these savings do not offset the cost of violating constraints. These results also demonstrate the good performance of the global model compared to its simplified variant, in the sense that the first sometimes provides configurations identical to the simplified cost model, while ensuring that user requirements are met. Placing VMs is a complex problem to solve. Due to its NP-complete nature, the computing time grows exponentially in the length of the inputs. Even with the simplified model, only small instances can be solved with the exact method. In order to overcome this problem, we propose, in the second stage of our work, a resolution method based on metaheuristics in order to obtain good solutions for large instances in a polynomial time. The method proposed in this article is based on the ILS heuristic that implements a descent as a local search mechanism and, following the early termination of the descent, performs jumps in the solution space to restart the algorithm from a new configuration. Furthermore, in order to speed up the evaluation of a configuration, gain functions that reflect the cost difference between the current solution and the considered neighbor, are determined. Various perturbation mechanisms are also implemented to avoid the trap of local optima. In general, the presented results are of two types: the parametrization of the method and the performance evaluation of the proposed algorithm. The parametrization phase helps determine the mechanisms to implement for each step of the algorithm as well as the ideal value of each key parameter. Thereafter, the algorithm performances are first compared with those obtained with the exact method defined in the first phase. The results demonstrate that the solutions generated by the proposed method are on average about 0.2% of the optimal solution, with a maximum deviation of 2.6% and an average running time of less than three seconds. To analyze the overall performance of the proposed method, the latter is run on instances of different sizes and the obtained results are compared with those resulting from the implementation of three resolution methods found in the literature. The results demonstrate that the proposed heuristic establishes a good compromise between the quality of the solution and execution time, with a carbon cost savings of up to 34%. Moreover, complex applications spanning multiple VMs are increasingly hosted in the cloud and introduce inter-VM traffic and network resources seeking to transit information from one VM to another. However, as the energy consumption of network resources represents about 25% of the total power of a data center, its impact cannot be ignored any longer, when we decide on location of VMs to reduce the environmental footprint of multiple data centers. In this context, the last phase of our work proposes an extension of the model developed in the first stage, where the optimization of the placement of VMs is combined with the mechanism of improving energy efficiency and the traffic routing. In addition, the process of routing traffic is also NP-complete and combining it with the problem of placing the VMs results in an even more difficult problem. Therefore, we also propose a resolution approach based on the hybridation of two metaheuristics, namely ILS and TS. In general, the developed method implements the ILS algorithm where the local search mechanism is an adaptation of the TS heuristic. This hybrid approach leverages the advantages of both methods, namely short and long term memory mechanisms in order to avoid cycles and local optima, as well as perturbation operators that boost exploration from a new starting configuration. In the experimental phase, both the proposed global model and resolution method are evaluated. The model is implemented in AMPL/CPLEX using integer linear programming and is evaluated by comparing it with other reference models with one goal being optimized at a time. As expected, the proposed model allows for better configurations in terms of carbon footprint cost, with a gain of up to 900% for the considered instances. However, this optimization is done at the cost of a computing time that is relatively higher because of the complexity of the proposed model. However, the carbon savings being substantially greater than the computing time differences, the results show the great efficiency of the proposed model when compared with models performing a single-objective optimization. The proposed resolution method has been implemented in C++ and preliminary experiments allow us to identify the optimal values of key parameters of that method, most of which depend on the problem size. The effectiveness of the method in terms of compromise between cost and carbon footprint runtime is first compared against the lower limit values of small instances. The results show that the developed algorithm is able to find solutions that are on average within less than 3% of the lower bound, and are computed in polynomial time, unlike exponential growth of the exact method. For larger instances, a comparison with different reference approaches demonstrates that the proposed approach is always able to find the minimum cost configurations in less time, highlighting the good performance of the proposed heuristic and accuracy in the choice of simulation parameters associated with it. All these experiments demonstrate, in light of the results obtained, that our work will provide to cloud suppliers effective tools for planning their applications across their data centers in order to better address the concerns regarding the environmental impact of Cloud Computing on the well-being of the planet.


Depuis une dizaine d'années, la dématérialisation de l'information connaît un essor particulier avec l'ascension du Cloud Computing. La puissance de calcul et de stockage offerte, ainsi que la flexibilité d'utilisation ont favorisé une externalisation accrue des données vers des serveurs distants. Ces derniers affranchissent les utilisateurs du fardeau de l'outil informatique traditionnel et leur donnent accès à un large éventail de services en ligne, qui sont des charges modulables, facturées selon l'utilisation. Particulièrement, dans le cas du modèle d'Infrastructure-service, le client dispose d'une infrastructure physique hébergée et peut ainsi louer des serveurs physiques, sur lesquels tourneront ses applications encapsulées dans des machines virtuelles ou Virtual Machines (VMs). Toutefois l'émergence du Cloud et son adoption à grande échelle constituent des défis pour les fournisseurs d'infrastructure. En effet, au-delà de l'implantation et de la configuration des réseaux physiques, il faut conjuguer avec l'infrastructure sous-jacente déjà existante, et déterminer des mécanismes efficaces d'assignation des requêtes des usagers aux serveurs et data centers, contraint par le respect des performances des applications hébergées et des exigences de sécurité imposées par les clients. La demande sans cesse croissante et le souci de fournir une certaine qualité de service, obligent les fournisseurs à investir d'importants capitaux afin de multiplier leurs offres d'hébergement dans plusieurs zones géographiques. Avec ce déploiement à grande échelle d'énormes data centers, leur utilisation à outrance, l'augmentation des coûts d'opération et de l'énergie électrique, les dépenses d'exploitation ont rapidement dépassé les investissements. De ce fait, plusieurs auteurs se sont penchés sur le problème de placement des charges dans un environnement Cloud et ont développé des outils d'aide aux prises de décision, basés concomitamment sur l'accroissement des profits, une meilleure correspondance entre les besoins essentiels du client et l'infrastructure disponible, et la maximisation de l'efficacité et de l'utilisation des ressources. Bien que le Cloud Computing offre une réponse favorable au problème de calcul et de stockage des informations, son adoption à grande échelle est freinée par les inquiétudes soulevées par sa signature écologique. En effet, l'utilisation excessive des data centers, de même que leur gestion et leur entretien, requièrent une énergie électrique accrue se traduisant par une empreinte carbone de plus en plus importante, accélérant ainsi le réchauffement climatique. Ainsi, au moment d'opter pour une solution Cloud, certains usagers questionnent l'impact environnemental d'un tel choix. Dans ce contexte, afin de favoriser l'expansion du Cloud, les géants de l'informatique n'ont d'autre choix que de conférer une dimension “vert” à leur infrastructure physique. Ceci se traduit par des techniques d'assignation des charges visant à réduire l'empreinte carbone des data centers afin de faire du Cloud Computing un succès tant technologique qu'écologique. Plusieurs études portant sur la réduction de l'empreinte carbone d'un unique data center, ont été récemment effectuées en considérant les techniques d'optimisation de l'énergie consommée. Toutefois, dans le contexte d'un Intercloud, où différents data centers sont géographiquement distribués et alimentés par des sources d'énergie renouvelables ou non, la consommation énergétique totale ne saurait refléter l'empreinte carbone dudit environnement. En ce sens, des recherches plus poussées ont porté sur l'optimisation de l'impact environnemental d'un InterCloud où l'hétérogénéité de l'infrastructure a été prise en compte. Cependant, seul le processus de placement des charges a été optimisé sans aucune considération pour l'amélioration de l'efficacité énergétique des data centers, pour la réduction de la consommation des ressources réseau, ou encore pour les exigences des clients en matière de performance des applications et de sécurité des données. À cet effet, cette thèse propose un cadre de planification des applications visant à minimiser l'empreinte carbone dans un environnement InterCloud. Généralement, le problème est traité de manière globale, en combinant le choix de l'emplacement des applications et le routage du trafic associé au problème de gestion du système de refroidissement dans les différents data centers. Divers aspects, comme la puissance des équipements de calcul, la consommation des ressources réseau et l'efficacité énergétique seront simultanément optimisés, sous la contrainte des exigences des clients. Le travail a été réalisé en trois phases. Dans le premier volet du travail, un modèle d'optimisation du placement des applications simples, à VM unique, a été développé afin de réduire l'impact écologique d'un ensemble de data centers. Le modèle d'empreinte carbone proposé améliore les approches de consommation énergétique déjà existantes en combinant l'optimisation du placement des VMs au mécanisme d'accroissement de l'efficacité énergétique des data centers. Ce dernier processus consiste à déterminer, pour chaque data center actif, la valeur optimale de température à fournir par le système de refroidissement, de manière à trouver un compromis entre les gains énergétiques, associés au cooling, et l'augmentation de la puissance des ventilateurs des serveurs, face à un accroissement de la température ambiante. Afin d'ajouter un certain réalisme au modèle, les exigences des clients, en termes de performances des applications hébergées, ou encore en rapport avec les notions de sécurité et de redondance, ont également été considérées. Une analyse de la monotonie et de la convexité du modèle non linéaire résultant a été effectuée afin de souligner l'importance entourant la détermination d'une valeur optimale de température. Par la suite, le problème a été transformé en un modèle linéaire et résolu de manière optimale avec un solveur mathématique, à l'aide des techniques de programmation linéaire en nombres entiers. Afin de mettre en évidence la pertinence du modèle d'optimisation proposé en termes de coût d'empreinte carbone, une analyse de la structure du coût et de l'impact de la charge a été réalisée. Dans le but de mieux apprécier les résultats, une version simplifiée du modèle, exempte de toute exigence du client, a alors été considérée. Ce même modèle simplifié a également été comparé à différentes techniques visant à optimiser l'empreinte carbone autant au sein d'un unique data center qu'à l'échelle d'un environnement InterCloud. Les résultats ont démontré que le modèle proposé permet de réduire jusqu'à 65% le coût d'empreinte carbone. De plus, afin de souligner l'efficacité du modèle proposé à réaliser un placement des VMs tout en respectant les contraintes de sécurité et de performances, le modèle simplifié a été comparé au modèle intégrant les exigences des clients. Bien que le modèle sans contraintes génère, en général des coûts d'empreinte carbone inférieurs à celui du modèle complet, il demeure moins intéressant à considérer, car le gain d'empreinte carbone résultant du processus de consolidation aveugle ne permet pas de contrebalancer le pourcentage de violation des contraintes. Ces résultats ont également permis de démontrer les bonnes performances du modèle complet comparé à sa variante simplifiée, dans le sens que le premier permet parfois d'obtenir des configurations de coût identique au modèle simplifié, en s'assurant, de surcroît, du respect des exigences des utilisateurs. Le mécanisme de placement des VMs est un problème complexe à résoudre. En raison de la nature NP-complet du problème, le temps de calcul croît de manière exponentielle en fonction des entrées et seules les instances de petite taille, même dans le cas du modèle simplifié, ont pu être résolues avec la méthode exacte. Afin de pallier ce problème, nous proposons, dans la seconde étape de notre travail, une méthode de résolution, basée sur les métaheuristiques, dans le but d'obtenir des solutions de qualité en un temps polynomial pour des instances de grande taille. La méthode de résolution proposée dans cet article est basée sur l'heuristique de Recherche Locale Itérée ou Iterated Local Search (ILS), qui implémente une descente comme mécanisme de recherche locale et, suite à l'arrêt prématuré du processus de descente, effectue des sauts dans l'espace des solutions afin de relancer l'exploration à partir d'une nouvelle configuration. Aussi, afin d'accélérer le processus d'évaluation d'une configuration, des fonctions de gains, traduisant la différence entre le coût de la solution actuelle et celui du voisin considéré, ont été déterminées. Divers mécanismes de perturbations ont également été implémentés afin d'éviter le piège des optima locaux. De manière générale, les résultats présentés sont de deux types : la paramétrisation de la méthode et l'évaluation des performances de l'algorithme. La phase de paramétrisation a permis de déterminer les mécanismes à implémenter à chaque étape de l'algorithme ainsi que la valeur idéale des paramètres clés. Par la suite, les performances de l'algorithme ont d'abord été comparées à celles obtenues avec la méthode exacte définie au premier volet. Les résultats démontrent que les solutions générées par la méthode proposée sont en moyenne à environ 0.2% de la solution optimale, avec un écart maximal de 2.6% et un temps d'exécution moyen inférieur à 3 secondes. Afin d'analyser les performances générales de la méthode proposée, cette dernière a été exécutée sur différentes tailles d'instances du modèle et les résultats obtenus ont été évalués par rapport à ceux découlant de l'implémentation de trois méthodes approchées retrouvées dans la littérature. Les résultats ont pu démontrer que l'heuristique proposée permet d'établir un bon compromis entre la qualité de la solution et le temps d'exécution, et peut engendrer une économie de coût de carbone pouvant s'élever jusqu'à 34%. Par ailleurs, des applications de plus en plus complexes, s'étendant sur plusieurs VMs, se font de plus en plus héberger dans le Cloud. Elles introduisent des trafics inter-VMs, sollicitant ainsi les ressources réseau afin de faire transiter l'information d'une machine virtuelle ou Virtual Machine (VM) à une autre. Or, comme la consommation énergétique des ressources réseau représente environ le quart de la puissance totale d'un data center, il en résulte alors que l'impact énergétique de ces équipements ne saurait être négligé plus longtemps, lorsque vient le temps de décider de l'emplacement des VMs afin de réduire l'empreinte écologique de plusieurs data centers. Dans ce contexte, la dernière phase de notre travail propose une extension du modèle développé à la première étape, où l'optimisation du placement des VMs est combinée au mécanisme d'amélioration de l'efficacité énergétique et au routage du trafic. De plus, le processus de routage du trafic étant également NP-complet, la combinaison de ce dernier au mécanisme de placement des VMs résulte en un problème encore plus difficile. En ce sens, nous avons également proposé une approche de résolution basée sur la combinaison de deux métaheuristiques, soit la Recherche Locale Itérée (ILS) et la Recherche Tabou (Tabu Search (TS)). De manière générale, la méthode développée implémente l'algorithme ILS où le mécanisme de recherche locale est une adaptation de l'heuristique TS. Cette hybridation permet de tirer profit des avantages des deux méthodes : d'une part, des mécanismes de mémoire à court et long terme afin d'éviter les cycles et les optima locaux, et d'autre part, des opérateurs de perturbation qui relancent l'exploration à partir d'une nouvelle configuration de départ. Dans la phase d'expérimentation, autant le modèle global que la méthode de résolution proposés ont été évalués. Le modèle global a été implémenté en AMPL/CPLEX en utilisant les techniques de programmation linéaire en nombres entiers et a été évalué par rapport à d'autres modèles de référence optimisant un unique objectif à la fois. Comme nous nous y attendions, le modèle proposé permet d'obtenir de meilleures configurations en termes de coût d'empreinte carbone, avec un gain pouvant s'élever jusqu'à environ 900% pour les instances considérées. Toutefois, cette optimisation se fait au prix d'un temps de calcul, en moyenne, relativement plus élevé, en raison de la complexité du modèle proposé. Cependant, l'économie en carbone réalisée étant substantiellement plus importante comparée aux écarts en temps de calcul observés, les résultats ont pu démontrer la grande efficacité du modèle proposé par rapport aux modèles réalisant une optimisation mono-objectif. La méthode de résolution approchée proposée a été implémentée en C++ et des expériences préliminaires nous ont permis de dégager les valeurs optimales des paramètres clés de la méthode, dont la plupart sont liées à la taille du problème. L'efficacité de la méthode, en termes de compromis entre coût d'empreinte carbone et temps d'exécution, a d'abord été comparée par rapport aux valeurs de borne inférieure, pour les instances de petite taille. Les résultats montrent que l'algorithme développé est en mesure de trouver des solutions, en moyenne, à moins de 3% de la borne inférieure en un temps polynomial, contrairement à une croissance exponentielle du temps de calcul pour la méthode exacte. Pour les plus grandes instances, une comparaison avec différentes méthodes de référence a pu démontrer que l'approche proposée est toujours en mesure de trouver les configurations de coût minimal en un temps réduit, soulignant ainsi les bonnes performances de l'heuristique développée et la justesse au niveau du choix des paramètres de simulation qui y sont associés. Ces expériences ont démontré, au regard des résultats obtenus, que le travail réalisé permettra d'offrir, aux fournisseurs de Cloud, des outils efficaces de planification des applications à l'échelle de leurs data centers, afin de mieux faire face aux inquiétudes soulevées quant à l'impact écologique du Cloud Computing sur le bien-être de la planète.

Department: Department of Computer Engineering and Software Engineering
Program: Génie informatique
Academic/Research Directors: Samuel Pierre and Ronald Beaubrun
PolyPublie URL: https://publications.polymtl.ca/2029/
Institution: École Polytechnique de Montréal
Date Deposited: 01 Apr 2016 15:34
Last Modified: 19 Apr 2023 16:27
Cite in APA 7: Justafort, V. D. (2015). Optimisation de l'empreinte carbone dans un environnement intercloud : modèles et méthodes [Ph.D. thesis, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/2029/


Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item