<  Back to the Polytechnique Montréal portal

Migrations en temps réel des machines virtuelles interdépendantes

Salah-Eddine Benbrahim

PhD thesis (2016)

[img]
Preview
Download (2MB)
Cite this document: Benbrahim, S.-E. (2016). Migrations en temps réel des machines virtuelles interdépendantes (PhD thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/2093/
Show abstract Hide abstract

Abstract

RÉSUMÉ Actuellement, les bonnes circulations et traitements des données sont devenus des clefs de succès dans tous les domaines techniques. Il est donc indispensable que les réseaux, véhiculant ces données, garantissent la qualité de leur transmission et réception. Cela est aussi applicable quand ces données sont échangées en continu par des hôtes virtuels distribués et interdépendants. La consolidation et répartition des charges (Load Balancing) devient un élément important pour améliorer les capacités et les services des réseaux. Cette répartition est possible par des réseaux infonuagiques utilisant des machines virtuelles. Comme ces machines peuvent être déployées et migrées en temps réel et à grande échelle, elles peuvent offrir de très bonnes possibilités de répartition des charges par leurs migrations en temps réel. Ainsi, il est important pour les décideurs de ces répartitions de charges de disposer des techniques efficaces permettant de minimiser les coûts de maintenance et de qualité de ces migrations en temps réel et de maximiser les retours sur investissement de leurs déploiements. Le problème de planification, de consolidation et de migration en temps réel des machines virtuelles (VMs) consiste à identifier les bons choix à effectuer pour placer les ressources d’un réseau de machines virtuelles et à déterminer les bonnes techniques pour les consolider par le déplacement de ces VMs entre des hôtes physiques. Ces déplacements des VMs doivent se faire sans interruption de service et dans des délais très réduits afin de respecter les contrats de niveaux de service et la qualité globale des services virtuels. Depuis quelques années, plusieurs recherches scientifiques se sont attardées sur l’étude de planification et de migration en temps réel des machines virtuelles. Cependant, ces études scientifiques se sont focalisées sur des VMs prises individuellement et non sur l’ensemble des VMs interdépendantes; cette démarche ne permet pas d’obtenir des solutions optimales prenant en considération les interdépendances entre ces VMs. D’autres études scientifiques se sont intéressées aux redéploiements dynamiques des charges d’un réseau en utilisant des migrations en temps réel des VMs et elles ont réussi à présenter des modélisations pour les résoudre. Cependant, elles n’ont pas considéré l’interdépendance entre des services applicatifs installés sur ces VMs; ces services ont besoin parfois d’échanger leurs informations afin d’effectuer leurs exécutions correctement. Cette thèse présente des techniques traitant de la planification, la consolidation, et la migration en temps réel de plusieurs machines virtuelles. L’interdépendance entre les VMs est considérée lors des développements de ces techniques. Notre travail est divisé en trois parties où chacune correspond à un de nos objectifs de recherche. Lors de la première partie, nous développons un modèle mathématique et son heuristique d’approximation pour solutionner le problème d’optimisation de la planification des emplacements des VMs prenant en considération leurs contraintes d’interdépendance; cette heuristique, efficace pour des grands ensembles de machines virtuelles, peut être ensuite exécutée par un logiciel installé sur une machine physique. Nous résolvons ce modèle grâce au solveur mathématique CPLEX en utilisant la méthode de programmation en nombres entiers mixte (MIP). L’objectif de ce modèle est de minimiser les coûts d’un réseau de VMs tout en respectant ses contraintes d’interdépendance. Afin de valider la performance de notre modélisation, nous résolvons avec CPLEX des petits ensembles de tests; ensuite, nous les vérifions et validons. Notre modèle est plus pertinent que celui de la modélisation sans les contraintes d’interdépendance qui donne des solutions dans des délais plus courts, mais qui demeurent non efficaces pour le bon fonctionnement des VMs interdépendantes. Comme le problème NP-difficile de « bin-packing » peut être réduit à notre problème de planification des VMs, ce dernier est aussi NP-difficile; pour cela, nous approximons sa modélisation avec une heuristique de recherche taboue qui est capable de traiter des grands ensembles en peu de temps. Cette heuristique trouve de bonnes solutions dans des délais acceptables pour des problèmes avec des grands ensembles. Cette heuristique visite une zone de solutions potentielles afin d’y trouver l’optimum local, puis elle refait cette même démarche dans des régions avoisinantes. Ainsi, notre heuristique réalise une exploration pertinente de l’espace des solutions possibles. Les performances de notre heuristique sont comparables à celles de notre modèle mathématique approximé dans le cas des problèmes avec des petits ensembles. De plus, cette heuristique est plus performante en ce qui concerne des temps de calcul puisqu’elle réussit à trouver de bonnes solutions dans des délais moindres que ceux des solutions exactes de CPLEX pour des grands ensembles de VMs. Lors de la deuxième partie de notre recherche, nous développons un modèle mathématique « multi-objectifs » (relaxé à un modèle « mono-objectif » par la méthode agrégée de la somme pondérée) et son heuristique d’approximation pour trouver une solution optimale pour le problème de migration en temps réel des VMs interdépendantes; cette modélisation obtient des solutions exactes et optimales pour un nombre réduit de VMs; cette heuristique, permettant de trouver des solutions quasi-optimales en peu de temps, peut être exécutée par un logiciel contrôleur installé sur une machine physique. Cette exécution peut être effectuée à intervalle régulier ou bien quand la qualité de service de certains services virtuels commence à se dégrader. En effet, avec cette modélisation « multi-objectifs » relaxé à « mono-objectif » via la méthode agrégée de la somme pondérée de chacun de nos objectifs, nous trouvons des solutions quasi-optimales pour nos quatre objectifs qui sont le délai de migration des VMs, leur délai d’arrêt, les pénalités dues aux non-respects des contrats de service, et leur qualité de service globale. La modélisation proposée permet plus de flexibilité en assignant un niveau relatif d’importance pour chacun des objectifs via leur facteur de pondération. Concernant la qualité globale de service et les pénalités des non-respects des contrats de niveaux de service (SLAs), les résultats obtenus grâce à notre modèle et son heuristique d’approximation sont meilleurs que la technique « pré-copie » utilisée et conçue pour les migrations en temps réel des VMs. Lors de la troisième partie de notre recherche, nous développons un modèle mathématique et son heuristique d’approximation visant à maximiser le profit net total tout en minimisant les pénalités des services virtuels aux contrats SLAs. Cette optimisation est une tâche complexe en raison de la difficulté de parvenir à un compromis réussi entre les pénalités sur les contrats de niveaux de service et le placement en temps réel des machines virtuelles (VM) interdépendantes. Cette troisième partie étudie donc ce problème de maximisation du profit net total tout en diminuant les pénalités de service et en réalisant des migrations en temps réel de machines virtuelles interdépendantes. Ce problème d’optimisation de placement en temps réel de machines virtuelles est NP-difficile puisque le problème NP-difficile « bin-packing » peut être réduit à ce problème, et son temps de calcul croit exponentiellement avec la taille des ensembles de machines virtuelles et de leurs machines physiques hôtes; pour cette raison, nous approximons notre modèle mathématique avec une heuristique de recherche taboue efficace. Nous testons notre formulation et heuristique pour des services virtuels, où le profit net total doit être maximisé, où les pénalités des services doivent être minimisées, et où des migrations efficaces en temps réel des VMs sont des sujets de préoccupation. Nos résultats de simulations montrent que notre heuristique d’approximation de notre modèle mathématique : (i) trouve de meilleures solutions que la configuration existante des milliers de machines utilisées dans des traces de Google; (ii) est adaptée pour de grandes ensembles des services virtuels avec des dizaines de milliers de machines virtuelles et machines physiques; et (iii) performe mieux en termes de pénalités et profits globaux que notre référence de comparaison c.-à-d. la configuration existante des machines utilisées dans des traces de Google.----------ABSTRACT Currently, data transmission and processing have become keys to success in many technology areas. Therefore, it is essential that networks guarantee the transmission and reception qualities of these data; also, this guarantee is important for data exchanged continuously by distributed and interconnected hosts. Also, “Load Balancing” techniques becomes an interesting key to improve network services and capacities. This load balancing technique is feasible with cloud networks based on virtual machines (VMs). Since these virtual machines can be deployed and live migrated on a large scale, they can offer very good possibilities of load balancing. Thus, it is important that decision makers dispose of effective techniques, such as load balancing, to minimize costs of these live migrations and to maximize their return on investment. Planning and live migration problems of virtual machines aim to identify right choices to place resources of virtual machine networks and to determine right techniques to move VMs between their physical hosts. These VMs’ moves should be done without service interruption and within very short delay. In recent years, several scientific researchers have studied planning and live migration of virtual machines; however, these scientific studies have focused on VMs individually without considering their interdependency constraints. Other scientific studies have investigated dynamic load balancing of a network using VM live migrations and they have succeeded to solve it using mathematical models; however, they did not consider the VMs’ interdependency. This thesis presents some techniques dealing with planning, consolidation, and live migrations of multiple virtual machines. These techniques take into account the VM interdependencies, the network service level contracts (SLAs) and overall quality. Our thesis is divided into three parts corresponding to our three research objectives. In the first part, we develop a mathematical model for VMs planning problem including the interdependency constraints. We solve this model using CPLEX as a mathematical solver with the mixed integer programming (MIP) method. The goal of this model is to minimize the overall cost of a VMs’ network while respecting its interdependent VMs constraints. To validate our modeling performance, we solved, with CPLEX, some small sets; then, we verified and validated our solutions. Our model is more relevant than other models ignoring interdependency constraints and which give solutions in a shorter time but remain ineffective for a proper functioning of interdependent VMs. Since VMs’ placement planning problem is an NP-hard problem (as the NP-hard “bin-packing” problem can be reduced to it), we approximate our model with a tabu search heuristic which is capable to handle large-sized sets. This heuristic finds good solutions in an acceptable delay by visiting areas of potential solutions in order to find local optimums, and then it repeats this process with other surrounding areas; thus, our heuristic performs relevant space explorations for possible solutions. Our heuristic has comparable performance to our approximated mathematical model in the case of small size sets; moreover, this heuristic is more efficient since its running time is lower than CPLEX to find near-enough exact solutions for large-sized sets. In the second part of our research, we have developed a "multi-objective" mathematical model to solve the problem of live migrations of interdependent VMs; this model is solved by relaxing it to a "mono-objective" model using the method of weighted sum of each of its objectives; thanks to this relaxation, we optimize four objectives simultaneously by dealing with live VM migrations, especially, their stop delays, their penalties on service level agreements and the overall quality of service. Our proposed model allows more flexibility by assigning a relative importance level for each objective. Results, of the overall quality of service and overall penalty on SLAs, obtained with our model are better than those of "pre-copy" VM live migrations ignoring VMs’ interdependency constraints. In the third part of this research, we develop a mathematical model to maximize the overall net profits of virtual services while minimizing the penalties on their SLAs. This optimization is a complex task because it is difficult to reach a successful compromise between decreasing the penalties on service level agreements and the live placement of interdependent virtual machines. This third part is therefore exploring this problem optimization of net profit and service penalties while performing live migrations of interdependent virtual machines. This live placement optimization problem of virtual machines is NP-hard and its calculation time grows exponentially with the size of virtual machine sets and their physical machines hosts; for this reason, we approximate our mathematical model with effective tabu search heuristic. We test our formulation and heuristic with virtual services which the overall net profit should be maximized, the penalty on SLAs should be minimized and live migrations should be effective. Our simulation results show that our heuristic: (i) finds better solutions than the existing configuration of machines used in Google traces; (ii) is adapted to large-sized virtual service sets with tens of thousands of virtual and physical machines; and (iii) performs better in terms of penalties and overall net profits when they are compared to those of the existing machines’ configuration of Google.

Open Access document in PolyPublie
Department: Département de génie informatique et génie logiciel
Dissertation/thesis director: Alejandro Quintero and Martine Bellaïche
Date Deposited: 13 Jul 2016 11:59
Last Modified: 24 Oct 2018 16:12
PolyPublie URL: https://publications.polymtl.ca/2093/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only