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.

With the fast growth of data-intensive distributed systems today, more novel and principled approaches are needed to improve the system efficiency, ensure the service quality to satisfy the user requirements, and lower the system running cost. This dissertation studies the design issues in the data-intensive distributed systems, which are differentiated from other systems by the heavy workload of data movement and are characterized by the fact that the destination of each data flow is limited to a subset of available locations, such as those servers holding the requested data. Besides, even among the feasible subset, different locations may result in different performance. The studies in this dissertation improve the data-intensive systems by exploiting the data storage location flexibility. It addresses how to reasonably determine the data placement based on the measured request patterns, to improve a series of performance metrics, such as the data access latency, system throughput and various costs, by the proposed hypergraph models for data placement. To implement the proposal with a lower overhead, a sketch-based data placement scheme is presented, which constructs the sparsified hypergraph under a distributed and streaming-based system model, achieving a good approximation on the performance improvement. As the network can potentially become the bottleneck of distributed data-intensive systems due to the frequent data movement among storage nodes, the online data placement by reinforcement learning is proposed which intelligently determines the storage locations of each data item at the moment that the item is going to be written or updated, with the joint-awareness of network conditions and request patterns. Meanwhile, noticing that distributed memory caches are effective measures in lowering the workload to the backend storage systems, the auto-scaling of memory cache clusters is studied, which tries to balance the energy cost of the service and the performance ensured. As the outcome of this dissertation, the designed schemes and methods essentially help to improve the running efficiency of data-intensive distributed systems. Therefore, they can either help to improve the user-perceived service quality under the same level of system resource investment, or help to lower the monetary expense and energy consumption in maintaining the system under the same performance standard. From the two perspectives, both the end users and the system providers could obtain benefits from the results of the studies. / Graduate

No description available.

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.

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.

Le nombre de véhicules circulant sur les routes dans le monde est passé de 500 millions en 1986 à 1 milliard de véhicules en 2010. Un tel réseau routier immense a apporté un certain confort à de nombreux conducteurs mais d'un autre coté il a représenté environs 1,24 millions d'accidents en 2010. Avec ces chiffres vient l'augmentation du niveau des émissions de CO2 et des milliards d'heures perdues dans les embouteillages. Avec le progrès et le développement des technologies sans fil ces dernières années, les réseaux véhiculaires ont rapidement évolués. Beaucoup de constructeurs automobiles et de pays ont intégré et imaginé différentes applications dans les réseaux véhiculaires : des applications de sécurité routières, d'autres pour l'information sur le trafic, ainsi que des applications de divertissement. Cette dernière catégorie d'applications se distingue des autres par la quantité et le volume de données échangées, et constitue un réel problème dû à la nature des communications sans fil véhiculaires. Dans cette thèse, nous traitons le problème de la dissémination d'information dans les systèmes véhiculaires distribués. Notre objectif principal est de proposer des solutions pratiques et réalisables pour diffuser les données dans des environnements véhiculaires réalistes. Le concept de la diffusion des données est large et significatif. Dans ce contexte, nous nous référons à la diffusion de données chaque fois qu'il y a une certaine quantité de données qui doit être répartie sur un réseau distribué sans fil. Les données sont envoyées vers plusieurs destinations (même à tous les nœuds du réseau dans certain cas) qui sont intéressés pour récupérer la totalité ou une partie des informations générées. A titre d'exemples, nous pouvons considérer les applications de partage de fichiers, la diffusion de fichiers multimédia et ainsi de suite. Nous abordons dans cette thèse le problème de dissémination de données dans les réseaux véhiculaires, plus précisément la dissémination de grands volumes de données tel que le contenu multimédia. Avec l'évolution au cours de ces dernières années des réseaux véhiculaires notamment grâce au support de nombreux constructeurs automobiles (e.x. Toyota, Nissan, BMW, Ford, etc.), la quantité de données échangée a augmenté de manière exponentielle au fil des années. Malheureusement malgré l'avancement des technologies de communications sans fil, l'échange de grands volumes de données dans des réseaux véhiculaires reste un réel défi, à cause des caractéristiques de communications sans fil et celles spécifiques aux réseaux véhiculaires. / The number of vehicles on the roads in the world increased from 500 million in 1986 to 1 billion vehicles in 2010. Such a huge road network has brought some comfort to many drivers but on the other hand it represented around 1.24 million accidents in 2010. With the progress and development of wireless technologies these recent years, vehicular networks quickly evolved. Many car manufacturers and countries have built and imagined different applications in vehicular networks: road safety applications, others for traffic information, and entertainment applications. This last category of applications is distinguished from others by the quantity and volume of exchanged data, and represents a real problem due to the lossy nature of vehicular communications. In this thesis, we address the problem of data dissemination in distributed vehicular systems. Our main objective is to provide practical and workable solutions to disseminate data in realistic vehicular environments. The concept of data dissemination is large and significant. In this context, we call data dissemination each time there is a certain amount of data which must be distributed on in wireless network. The data is sent to multiple destinations who are interested to recover all or part of the information. As examples, we can consider the file sharing applications, streaming multimedia files and so on. We discuss in this thesis the data dissemination problem in vehicular networks, specifically the dissemination of large volumes of data such as content distribution. With the evolution in recent years of vehicular networks thanks to many car manufacturers support (eg Toyota, Nissan, BMW, Ford, etc.), the amount of exchanged data has increased exponentially over the years. Unfortunately, despite the advancement of wireless communications technologies, exchange large volumes of data in vehicular networks remains a challenge because of wireless communications features and those specific to vehicular networks.

Energy conservation is a major concern in todays data centers, which are the 21st century data processing factories, and where large and complex software systems such as distributed data management stores run and serve billions of users. The two main drivers of this major concern are the pollution impact data centers have on the environment due to their waste heat, and the expensive cost data centers incur due to their enormous energy demand. Among the many subsystems of data centers, the storage system is one of the main sources of energy consumption. Among the many types of storage systems, key/value stores happen to be the widely used in the data centers. In this work, I investigate energy saving techniques that enable a consistent hash based key/value store save energy during low activity times, and whenever there is an opportunity to reuse the waste heat of data centers.

Energy conservation is a major concern in todays data centers, which are the 21st century data processing factories, and where large and complex software systems such as distributed data management stores run and serve billions of users. The two main drivers of this major concern are the pollution impact data centers have on the environment due to their waste heat, and the expensive cost data centers incur due to their enormous energy demand. Among the many subsystems of data centers, the storage system is one of the main sources of energy consumption. Among the many types of storage systems, key/value stores happen to be the widely used in the data centers. In this work, I investigate energy saving techniques that enable a consistent hash based key/value store save energy during low activity times, and whenever there is an opportunity to reuse the waste heat of data centers.