Dans cette thèse, nous nous intéressons à la résolution de quelques problèmes d'optimisation combinatoires que nous avons choisi de traiter en deux volets. Dans un premier temps, nous étudions des problèmes d'optimisation issus de l'ordonnancement d'un ensemble de tâches sur des machines de calcul et où on cherche à minimiser l'énergie totale consommée par ces machines tout en préservant une qualité de service acceptable. Dans un deuxième temps, nous traitons deux problèmes d'optimisation classiques à savoir un problème d'ordonnancement dans une architecture de machines parallèles avec des temps de communication, et un problème de placement de données dans des graphes modélisant des réseaux pair-à-pair et visant à minimiser le coût total d'accès aux données. / In this thesis, we focus on solving some combinatorial optimization problems that we have chosen to study in two parts. Firstly, we study optimization problems issued from scheduling a set of tasks on computing machines where we seek to minimize the total energy consumed by these machines while maintaining acceptable quality of service. In a second step, we discuss two optimization problems, namely a classical scheduling problem in architecture of parallel machines with communication delays, and a problem of placing data in graphs that represent peer-to-peer networks and the goal is to minimize the total cost of data access.

Dans les prochaines années, l’Internet des objets (IoT) constituera l’une des applications générant le plus de données. Actuellement, les données de l’IoT sont stockées dans le Cloud. Avec l’augmentation du nombre d’objets connectés, la transmission de la grande quantité de données produite vers le Cloud génèrera des goulets d’étranglement. Par conséquent, les latences seront élevées. Afin de réduire ces latences, le Fog computing a été proposé comme un paradigme étendant les services du Cloud jusqu’aux périphéries du réseau. Il consiste à utiliser tout équipement localisé dans le réseau (ex. routeur) pour faire le stockage et le traitement des données. Cependant, le Fog présente une infrastructure hétérogène. En effet, ses équipements présentent des différences de performances de calcul, de capacités de stockage et d’interconnexions réseaux.Cette hétérogénéité peut davantage augmenter la latence du service. Cela pose un problème : le mauvais choix des emplacements de stockage des données peut augmenter la latence du service. Dans cette thèse, nous proposons une solution à ce problème sous la forme de quatre contributions : 1. Une formulation du problème de placement de données de l’IoT dans le Fog comme un programme linéaire. 2. Une solution exacte pour résoudre le problème de placement de données en utilisant CPLEX, un solveur de problème linéaire. 3. Deux heuristiques basées sur le principe de “diviser pour régner” afin de réduire le temps du calcul de placement. 4. Une plate-forme expérimentale pour évaluer des solutions de placement de données de l’IoT dans le Fog, en intégrant la gestion du placement de données à iFogSim, un simulateur d’environnement Fog et IoT. / In the coming years, Internet of Things (IoT) will be one of the applications generating the most data. Nowadays, IoT data is stored in the Cloud. As the number of connected objects increases, transmitting the large amount of produced data to the Cloud will create bottlenecks. As a result, latencies will be high and unpredictable. In order to reduce these latencies, Fog computing has been proposed as a paradigm extending Cloud services to the edge of the network. It consists of using any equipment located in the network (e.g. router) to store and process data. Therefore, the Fog presents a heterogeneous infrastructure. Indeed, its components have differences in computing performance, storage capacity and network interconnections. This heterogeneity can further increase the latency of the service. This raises a problem: the wrong choice of data storage locations can increase the latency of the service. In this thesis, we propose a solution to this problem in the form of four contributions: 1. A formulation of the IoT data placement problem in the Fog as a linear program. 2. An exact solution to solve the data placement problem using the CPLEX, a mixed linear problem solver. 3. Two heuristics based on the principle of “divide and conquer” to reduce the time of placement computation. 4. An experimental platform for testing and evaluating solutions for IoT data placement in the Fog, integrating data placement management with iFogSim, a Fog and IoT environment simulator.

Afin de fournir toujours plus de puissance de calcul les architectes intègrent plusieurs dizaines de processeurs dans une même puce. Le but de nos travaux est d'améliorer l'efficacité des accès aux données à l'aide de solutions entièrement transparentes au logiciel. Notre contexte vise les machines multiprocesseurs à base de NoC qui possèdent des caches L1 et de la mémoire partagée et distribuée. Dans une première partie nous montrons que la redéfinition des contraintes dans les systèmes embarqués rend l'utilisation du protocole de cohérence write-through invalidate envisageable. Nous présentons également une solution innovante pour évaluer et comparer les protocoles de cohérence mémoire. Dans une deuxième partie nous présentons une solution innovante à la migration des données dans la puce. Celle-ci, gérée par le matériel, vise à placer dynamiquement et intelligemment les données afin de diminuer le coût d'accès moyen à la mémoire.

La quantité de données stockées dans le monde ne cesse de croître et cela pose des challenges aux fournisseurs de service de stockage qui doivent trouver des moyens de faire face à cette croissance de manière scalable, efficace, tout en optimisant les coûts. Nous nous sommes intéressés aux systèmes de stockage de données dans le nuage qui est une grande tendance dans les solutions de stockage de données. L'International Data Corporation (IDC) prédit notamment que d'ici 2020, environ 40% des données seront stockées et traitées dans le nuage. Cette thèse adresse les challenges liés aux performances d'accès aux données et à la sûreté de fonctionnement dans les systèmes de stockage dans le nuage. Nous avons proposé Mistore, un système de stockage distribué que nous avons conçu pour assurer la disponibilité des données, leur durabilité, ainsi que de faibles latences d'accès aux données en exploitant des zones de stockage dans les box, les Points de Présence (POP), et les centre de données dans une infrastructure Digital Subscriber Line (xDSL) d'un Fournisseur d'Accès à Internet (FAI). Dans Mistore, nous adressons aussi les problèmes de cohérence de données en fournissant plusieurs critères de cohérence des données ainsi qu'un système de versioning. Nous nous sommes aussi intéressés à la sécurité des données dans le contexte de systèmes de stockage appliquant une déduplication des données, qui est l'une des technologies les plus prometteuses pour réduire les coût de stockage et de bande passante réseau. Nous avons conçu une méthode de déduplication en deux phases qui est sécurisée contre des attaques d'utilisateurs malicieux tout en étant efficace en termes d'économie de bande passante réseau et d'espace de stockage. / The quantity of data in the world is steadily increasing bringing challenges to storage system providers to find ways to handle data efficiently in term of dependability and in a cost-effectively manner. We have been interested in cloud storage which is a growing trend in data storage solution. For instance, the International Data Corporation (IDC) predicts that by 2020, nearly 40% of the data in the world will be stored or processed in a cloud. This thesis addressed challenges around data access latency and dependability in cloud storage. We proposed Mistore, a distributed storage system that we designed to ensure data availability, durability, low access latency by leveraging the Digital Subscriber Line (xDSL) infrastructure of an Internet Service Provider (ISP). Mistore uses the available storage resources of a large number of home gateways and Points of Presence for content storage and caching facilities. Mistore also targets data consistency by providing multiple types of consistency criteria on content and a versioning system. We also considered the data security and confidentiality in the context of storage systems applying data deduplication which is becoming one of the most popular data technologies to reduce the storage cost and we design a two-phase data deduplication that is secure against malicious clients while remaining efficient in terms of network bandwidth and storage space savings.

Les workflows sont des systèmes typiques traitant le big data. Ces systèmes sont déployés sur des sites géo-distribués pour exploiter des infrastructures cloud existantes et réaliser des expériences à grande échelle. Les données générées par de telles expériences sont considérables et stockées à plusieurs endroits pour être réutilisées. En effet, les systèmes workflow sont composés de tâches collaboratives, présentant de nouveaux besoins en terme de dépendance et d'échange de données intermédiaires pour leur traitement. Cela entraîne de nouveaux problèmes lors de la sélection de données distribuées et de ressources de stockage, de sorte que l'exécution des tâches ou du job s'effectue à temps et que l'utilisation des ressources soit rentable. Par conséquent, cette thèse aborde le problème de gestion des données hébergées dans des centres de données cloud en considérant les exigences des systèmes workflow qui les génèrent. Pour ce faire, le premier problème abordé dans cette thèse traite le comportement d'accès aux données intermédiaires des tâches qui sont exécutées dans un cluster MapReduce-Hadoop. Cette approche développe et explore le modèle de Markov qui utilise la localisation spatiale des blocs et analyse la séquentialité des fichiers spill à travers un modèle de prédiction. Deuxièmement, cette thèse traite le problème de placement de données intermédiaire dans un stockage cloud fédéré en minimisant le coût de stockage. A travers les mécanismes de fédération, nous proposons un algorithme exacte ILP afin d’assister plusieurs centres de données cloud hébergeant les données de dépendances en considérant chaque paire de fichiers. Enfin, un problème plus générique est abordé impliquant deux variantes du problème de placement lié aux dépendances divisibles et entières. L'objectif principal est de minimiser le coût opérationnel en fonction des besoins de dépendances inter et intra-job / The typical cloud big data systems are the workflow-based including MapReduce which has emerged as the paradigm of choice for developing large scale data intensive applications. Data generated by such systems are huge, valuable and stored at multiple geographical locations for reuse. Indeed, workflow systems, composed of jobs using collaborative task-based models, present new dependency and intermediate data exchange needs. This gives rise to new issues when selecting distributed data and storage resources so that the execution of tasks or job is on time, and resource usage-cost-efficient. Furthermore, the performance of the tasks processing is governed by the efficiency of the intermediate data management. In this thesis we tackle the problem of intermediate data management in cloud multi-datacenters by considering the requirements of the workflow applications generating them. For this aim, we design and develop models and algorithms for big data placement problem in the underlying geo-distributed cloud infrastructure so that the data management cost of these applications is minimized. The first addressed problem is the study of the intermediate data access behavior of tasks running in MapReduce-Hadoop cluster. Our approach develops and explores Markov model that uses spatial locality of intermediate data blocks and analyzes spill file sequentiality through a prediction algorithm. Secondly, this thesis deals with storage cost minimization of intermediate data placement in federated cloud storage. Through a federation mechanism, we propose an exact ILP algorithm to assist multiple cloud datacenters hosting the generated intermediate data dependencies of pair of files. The proposed algorithm takes into account scientific user requirements, data dependency and data size. Finally, a more generic problem is addressed in this thesis that involve two variants of the placement problem: splittable and unsplittable intermediate data dependencies. The main goal is to minimize the operational data cost according to inter and intra-job dependencies