Dans le domaine de l'Optimisation Combinatoire, la résolution de manière optimale de problèmes de grande taille par le biais d'algorithmes Branch-and-Bound requiert un nombre très élevé de ressources de calcul. De nos jours, de telles ressources sont accessibles grâce aux grilles de calcul, composées de grappes de clusters réparties sur différents sites géographiques. Ces environnements parallèles posent de nombreux défis scientifiques, notamment en termes de passage à l'échelle, de la prise en compte de l'hétérogénéité des ressources ainsi qu'en termes de tolérance aux pannes. La plupart des approaches existantes pour l'algorithme Branch-and-Bound parallèle sont basées sur une architecture de type Maître-Esclave, où un processus maître répartit les tâches à accomplir auprès de processus esclaves en charge de les traiter. L'utilisation d'une telle entité centrale constitue un obstacle majeur en ce qui concerne le passage à l'échelle. Dans cette thèse, nous proposons de relever ces défis ainsi que de surmonter cet obstacle grâce à une approche innovante et complètement distribuée, basée sur une architecture Pair-à-Pair (P2P). Celle-ci repose sur un seul type de processus (le pair), qui a pour mission d'explorer son propre ensemble de tâches, de le partager avec d'autres pairs et de diffuser l'information globale. Nous définissons des mécanismes adaptés en lien avec l'algorithme Branch-and-Bound, qui traitent de la répartition de la charge, de la diffusion de la meilleure solution trouvée et de la détection de la terminaison des calculs. En plus de multiples expérimentations sur le problème d'ordonnancement du Flow-Shop sur la grille de calcul Grid'5000, nous proposons une preuve formelle de la correction de notre approche. Par ailleurs, nous traitons une problématique souvent ignorés dans les travaux relatifs au calcul P2P, qui est l'importance de la topologie du réseau P2P. Généralement, une topologie très simple est utilisée. Les résultats obtenus montrent que notre approche permet le déploiement de réseaux de calculs à de très grandes échelles, constitués potentiellement de centaines de milliers de coeurs de calcul. Notre dernière contribution consiste en une approche Pair-à-Pair tolérante aux pannes afin de prendre en compte la nature généralement très volatile des ressources de calcul. Les résultats obtenus prouvent la robustesse de l'approche dans des environnements à la fois réalistes et sujets à de nombreux dysfonctionnements. / In the field of Combinatorial Optimization, the resolution to optimality of large instances of optimization problems through the use of Branch-and-Bound algorithms require a huge amount of computational resources. Nowadays, such resources are available from computing grids, which are sets of computing nodes geographically distributed over multiple sites. These parallel environments introduces multiples challenges related to the scalability, the heterogeneity of resources and the fault tolerance. Most of the existing approaches for the Branch-and-Bound algorithm are based on the Master-Slave paradigm where a central entity shares work units among slave entities in charge of processing them. Such an architecture represents an obstacle to scalability. In this thesis, we propose to face the challenges of grid environments and overcome this limitation by proposing an innovative and fully distributed approach based on the Peer-to-Peer paradigm. This architecture is based on a unique type of entity, a peer which is in charge of exploring its own local work pool and broadcasts global information to the network. We provide mechanisms to deal with the main tasks of the Branch-and-Bound algorithm : the load balancing, the diffusion of the best solution and the detection of the termination. Along with extensive experiments conducted on the Flow-Shop Scheduling Problem using the Grid'5000 Experimental Grid, we propose a formal proof of the correctness of our approach.In addition to this, we tackle a central issue when designing a Peer-to-Peer application : the impact of the P2P network topology on the performance of our approach. This aspect is often ignored in most of existing works, where only a predefined organization is chosen for the peers. The obtained results showed that the approach allows to deploy computing networks at extreme scales, involving hundreds of thousands of computing cores. Our final contribution consists in a Fault-Tolerant approach to deal with the dynamicity of the network (the volatility of computational resources). Results indicate that it faces efficiently various real-case and failure-intensive situations.

La quantité de données numériques produites par les utilisateurs, comme les photos, les vidéos et les documents numériques, a énormément augmenté durant cette dernière décennie. Ces données possèdent une grande valeur et nécessitent d'être sauvegardées en sécurité. D'une part, les solutions basées sur les DVDs et les disques durs externes, bien que très communes, ne fournissent pas un niveau suffisant de fiabilité. D'autre part les solutions basées sur de serveurs centralisées sont très coûteuses. Pour ces raisons, la communauté de recherche a manifesté un grand intérêt pour l'utilisation des systèmes pair-à-pair pour la sauvegarde de donnés. Les systèmes pair-à-pair représentent une solution intéressante grâce à leur capacité de passage à l'échelle. En effet, la capacité du service augmente avec la demande. La conception d'un réseau de sauvegarde de fichiers pair-à-pair est une tâche très complexe et présente un nombre considérable de défis. Les pairs peuvent avoir une durée de connexion limitée et peuvent quitter le système à un taux qui est considérablement plus élevé que dans le cas des systèmes de stockage centralisés. Notre intérêt se concentre sur la manière de fournir efficacement du stockage de données suffisamment fiable en appliquant des schémas de redondance appropriés et en adoptant des bons mécanismes pour maintenir une telle redondance. Cet effort n'est pas négligeable, dans la mesure où la maintenance du stockage de données dans un tel système exige des ressources importantes en termes de capacité de stockage et de largeur de bande passante. Notre contribution se porte sur deux aspects. Premièrement, nous proposons et étudions des codes correcteurs pour la redondance capables de combiner l'efficacité en bande passante de la réplication à l'efficacité en stockage des codes correcteurs classiques. En particulier, nous présentons et analysons deux nouvelles classes de codes: Regenerating Codes et Hierarchical Codes. Deuxièmement, nous proposons un système de réparation, nommé "adaptive proactive repair scheme", qui combine l'adaptabilité des systèmes réactifs avec l'utilisation régulière de la bande passante des systèmes proactifs, en généralisant les deux approches existantes.

Cette thèse se base sur une vision originale des systèmes de Recherche d'Information en pair-à-pair (RI-P2P) ; pour proposer un ensemble d'outils pour mieux les évaluer et mieux les concevoir.Synthétiquement, la problématique d'évaluation consiste à comprendre quel système fonctionne bien dans quelles conditions ; comment les différents composants/aspects d'un système contribuent à ses performances ; comment des modifications du système peuvent faire évoluer ses performances. D'un point de vue conception, on voudrait savoir choisir une approche P2P en fonction du contexte de l'application à implémenter (jeu de données, propriétés du réseau...) ; comprendre comment mixer des systèmes ; mieux maîtriser l'impact d'une modification de l'implémentation sur le comportement et les performances d'un système.Nous pensons que ces deux problématiques d'évaluation et de conception sont fortement liées. Un même fondement est nécessaire pour progresser dans ces deux sens : mieux comprendre l'architecture des systèmes RI-P2P. À la base de notre réflexion, nous considérons qu'un système RI-P2P est l'implémentation en P2P d'un modèle RI, idée qui s'oppose au modèle traditionnel en deux couches. Nous nous appuyons sur cette idée pour donner un ensemble de définitions qui permettent de mieux appréhender les différents composants RI et composants P2P d'un même système et la façon dont ils s'organisent. Nous montrons ensuite comment on peut utiliser cette vision originale du domaine pour spécifier la démarche d'évaluation d'un système P2P et pour aider à la conception de nouveaux systèmes. / This PhD thesis develops an original vision of Peer-to-Peer Information Retrieval Systems. Based on this vision, we ropose a set of tools for a better evaluation and conception of P2P-IR systems.Synthetically, on the one hand, evaluating means understanding which system behaves well in which context ; how different components/aspects of a single system contribute to its performance ; how modifications of the system can make its performance evolve. On the other hand, considering design of P2P-IR systems, we would like to be able to choose a P2P approach based on what is known about the context the application will execute in (data set, network properties...) ; understand how to mix P2P systems ; better control the impact of a modification of the implementation of a system on its behavior an performance.We believe those concerns of evaluation and design are strongly related. There is a common need to improve on both directions : better understand the architecture of P2P-IR systems. On the basis of our reflexion, we consider a P2P-IR system is the implementation in P2P of an IR system, which contrasts with the traditional two-layered vision. We use this idea to give a set of definitions that help better understand the different RI and P2P components of a single system and their relationships. We then show how this vision can be used to help design new systems.

peuvent intéragir à travers des avatars. Les jeux en ligne comme Quake et World of Warcraft sont les applications les plus populaires pour les NVEs. Au début de l'année 2003, est apparu Second Life (SL), un monde virtuel où les avatars peuvent créer une nouvelle vie sociale. La principale caractéristique innovatrice de SL est le contenu créé par les utilisateurs: les avatars participent au développement de l'environnement virtuel par la création d'objets tels que des voitures, des arbres et des bâtiments. SL est devenu rapidement le monde virtuel le plus populaire, avec plus de 16 millions d'utilisateurs en Septembre 2009. L'état de l'art pour la conception des NVEs est principalement une architecture Client/Serveur où plusieurs serveurs maintiennent l'état du monde virtuel pour le transférer aux utilisateurs. Cette architecture est très chère puisqu'une grande quantité de serveurs doivent être déployés, exploités et maintenus. Par ailleurs, cette architecture ne passe pas à l'échelle. Ces inconvénients motivent la conception des architectures innovatrices tels que l'architecture Pair-à-Pair (P2P). Idéalement, une architecture P2P pour les NVEs passe à l'échelle, car chaque utilisateur consacre une partie de ses ressources (stockage, CPU, bande passante) à la gestion du monde virtuel. En outre, le P2P peut considérablement réduire le coût pour le fournisseur du monde virtuel. Il y a trois contributions majeures dans cette thèse. Premièrement, en raison du manque de statistiques sur les mondes virtuels (par exemple, mouvement des avatars et distribution des objets), nous procédons à une analyse exhaustive de SL. Pour cette raison, on a implémenté deux applications qui surveillent, pendant un mois, objets, avatars, Qualité d'Expérience des utilisateurs et performance des serveurs dans la partie publique de SL. Deuxièmement, nous concevons une gestion distribuée des objets pour les NVEs générées par ses utilisateurs. Nous intégrons cette infrastructure de communication sur Kad, le réseau P2P utilisé par des millions d'utilisateurs d'eMule, et réalisons des expériences à grande échelle. Ensuite, nous concevons Walkad un réseau P2P structuré spécialement conçu pour gérer les objets générés par les utilisateurs dans un monde virtuel. Troisièmement, nous étudions la faisabilité d'une gestion distribuée des avatars en utilisant la triangulation de Delaunay. D'abord, nous évaluons la performance de la triangulation de Delaunay par des expériences réalisées dans SL grâce à un client modifié que nous avons développé. Successivement, nous concevons et évaluons deux optimisations pour la triangulation de Delaunay: (1) un algorithme de clustering qui améliore la réactivité des interactions entre les avatars en présence de larges groupes d'avatars; (2) le Réseau Delaunay Social, un réseau P2P qui résout le problème de la sécurité dans un NVE en utilisant les relations d'amitié qui existent entre les avatars.

Des réseaux de type pair-à-pair "overlay" sont des systèmes distribués sans aucune organisation hiérarchique ni contrôle centralisé. Les pairs forment un réseau overlay au dessus de l'Internet. Les deux parties de cette thèse traitent les réseaux pair-à-pair overlay. La première partie utilise un réseau non structuré afin de construire un environnement virtuel partagé à grande échelle. Nous présentons une étude complète d'un overlay basé sur la triangulation de Delaunay. Avant tout nous décrivons les algorithmes auto-organisant pour l'insertion et la suppression d'un pair. Afin de réduire la pénalité de latence introduite par le routage dans l'overlay, nous proposons d'augmenter chaque nœud par quelques liens raccourcis qui créent un petit monde. Nous montrons que très peu de liens sont suffisants pour réduire la latence de manière significative. La deuxième partie de cette thèse donne des aperçus du comportement des utilisateurs d'un réseau pair-à-pair structuré dans le monde réel. Nous détaillons le fonctionnement de KAD, une table de hachage distribuée basé sur Kademlia, un système de partage de fichier avec plusieurs millions d'utilisateurs simultanés. Nous avons exploré le réseau de KAD pendant plus d'une année. C'est ainsi que nous avons obtenu des informations sur la distribution géographique, les temps de sessions, la disponibilité et le temps de vie des pairs. Nous sommes fascinés et effrayés par les possibilités que KAD offre. Le montage d'une attaque Sybil est très facile et permet de récupérer des données personnelles des utilisateurs, de compromettre le fonctionnement correct de la recherche dans KAD et de conduire une attaque DDOS.

Depuis quelques décennies, la quantité d'information numérique produite ne cesse de croître exponentiellement, ce qui soulève des difficultés de plus en plus critiques en terme de stockage, d'accessibilité et de disponibilité de cette information. Les architectures logicielles et matérielles construites autour du modèle pair-à-pair (P2P) semblent répondre globalement aux exigences liées au stockage de l'information mais montrent leurs limites en ce qui concerne les exigences d'accessibilité et de disponibilité de l'information. Nous présentons dans cette thèse différents apports concernant les architectures P2P pour la gestion de grands volumes d'information. Les stratégies algorithmiques que nous proposons exploitent des topologies virtuelles dédiées sur lesquelles nous développons des protocoles de maintenance et de gestion du réseau efficaces. En particulier, pour assurer le passage à grande échelle, nous proposons des solutions pour lesquelles les coûts des opérations de maintenance et de gestion des topologies virtuelles sont constants en moyenne pour chaque noeud du réseau, et ceci, quelle que soit la taille du réseau. Nous analysons les principaux paradigmes de la répartition d'information sur un réseau P2P, en considérant successivement, le problème de l'accès à de l'information typée (semi-structurée) et le cas général qui dissocie entièrement la nature des requêtes du placement de l'information. Nous proposons une méthode d'aiguillage de requêtes portant sur la structure et le contenu de documents semi-structurés ainsi qu'une technique plus générale dans le cas le plus défavorable où aucune connaissance n'est disponible a priori sur la nature des informations stockées ou sur la nature des requêtes. Dans l'optique de la gestion d'une qualité de service (qui s'exprime en terme de rapidité et de fiabilité), nous nous intéressons également au problème de la disponibilité pérenne de l'information sous l'angle de la réplication des données stockées dans le réseau. Nous proposons une approche originale exploitant une mesure locale de densité de réplicas estimée sur une topologie virtuelle dédiée.

Les systèmes pair-à-pair décentralisés mettent en relation un grand nombre d'utilisateurs pour mutualiser des ressources dans un environnement dynamique. Les applications de ces systèmes vont du partage de fichiers à la téléphonie par Internet, en passant par la décentralisation de services comme les DNS. Afin de limiter les ressources nécessaires, chaque recherche doit transmettre les messages rapidement et contrôler le nombre de messages dans le réseau. C'est pourquoi cette thèse s'intéresse au routage et à l'interconnexion nécessaire pour assurer ce routage.Dans la première partie, je présente un état de l'art des différents systèmes existants. J'y détaille la problématique générale et les caractéristiques des différentes classes de systèmes pair-à-pair. La seconde partie traite des réseaux à contenu adressable, qui permettent d'assurer un routage avec des bornes sur le nombre de sauts des requêtes et la charge par noeud. J'y expose d'abord les différents réseaux à contenu adressable existants. Je présente ensuite un nouveau protocole, D2B, dont je prouve en particulier qu'il améliore la charge par noeud tout en assurant un nombre de sauts et un degré faible. Je détaille enfin une liste d'optimisations applicables aux réseaux à contenu adressable en général, ou à D2B en particulier. Dans la troisième partie, je récapitule les principaux travaux qui tirent parti des communautés d'utilisateurs d'une part, et ceux qui exploitent la structure de loi de puissance de l'autre. Je présente ensuite ma seconde contribution, QRE, qui exploite efficacement à la fois ces deux caractéristiques des échanges: agrégats en communautés et loi de puissance.

Cette thèse se base sur une vision originale des systèmes de Recherche d'Information en pair-à-pair (RI-P2P) ; pour proposer un ensemble d'outils pour mieux les évaluer et mieux les concevoir.Synthétiquement, la problématique d'évaluation consiste à comprendre quel système fonctionne bien dans quelles conditions ; comment les différents composants/aspects d'un système contribuent à ses performances ; comment des modifications du système peuvent faire évoluer ses performances. D'un point de vue conception, on voudrait savoir choisir une approche P2P en fonction du contexte de l'application à implémenter (jeu de données, propriétés du réseau...) ; comprendre comment mixer des systèmes ; mieux maîtriser l'impact d'une modification de l'implémentation sur le comportement et les performances d'un système.Nous pensons que ces deux problématiques d'évaluation et de conception sont fortement liées. Un même fondement est nécessaire pour progresser dans ces deux sens : mieux comprendre l'architecture des systèmes RI-P2P. À la base de notre réflexion, nous considérons qu'un système RI-P2P est l'implémentation en P2P d'un modèle RI, idée qui s'oppose au modèle traditionnel en deux couches. Nous nous appuyons sur cette idée pour donner un ensemble de définitions qui permettent de mieux appréhender les différents composants RI et composants P2P d'un même système et la façon dont ils s'organisent. Nous montrons ensuite comment on peut utiliser cette vision originale du domaine pour spécifier la démarche d'évaluation d'un système P2P et pour aider à la conception de nouveaux systèmes.

Cette thèse contribue à l'amélioration de la fiabilité des réponses fournies par les systèmes pair-à-pair sémantiques de plusieurs façons. La première partie de la thèse a pour but de garantir de ne produire que des réponses bien-fondées quand le réseau global d'un tel système est inconsistant. Deux algorithmes ont été proposés. Le premier détecte des causes d'inconsistances. Il termine, est décentralisé, complet, correct. Le deuxième profite des résultats du premier pour garantir de ne raisonner que de manière bien-fondée. Il termine, est décentralisé, correct. Des résultats prometteurs ont été obtenus à partir des expérimentations. La seconde partie de la thèse considère le problème de modéliser la confiance des pairs en des réponses obtenues. Basé sur un modèle probabiliste, le modèle de confiance proposé a une sémantique claire et permet aux pairs d'estimer la confiance en des réponses obtenues avec une bonne précision même avec peu observations.

Avec l'émergence des terminaux de communication mobiles plus petits et plus performants, la dissémination de l'information prend une place plus importante dans les réseaux mobiles pair-à-pair ; à l'exemple de la dissémination des messages de routine, des messages d'urgence, ou du contenu multimédia dans les réseaux VANETS (Vehicular Ad hoc NETwork). Dans ce projet de doctorat, nous proposons une approche de dissémination de l'information dans les réseaux mobiles pair-à-pair, dont l'originalité consiste à utiliser les transmissions simultanées dans la même bande de fréquences pour réduire considérablement la durée de la dissémination. Pour ce faire, nous nous intéressons dans la première partie de cette thèse, au décodage des paquets qui résultent de la collision de deux paquets sources sans la connaissance préalable de ces derniers. L'analyse du symbole d'interférence révèle qu'en raison de la présence d'un point de symétrie centrale dans les constellations traditionnelles, le démodulateur conventionnel ne peut distinguer les symboles d'interférence issus de la superposition de symboles sources symétriques. Par conséquent, nous proposons, dans le cadre des transmissions simultanées synchronisées, une constellation dénommée 4-TRAQAM (TRApezoidal Quadrature Amplitude Modulation), qui n'admet pas de symétrie centrale et pour laquelle les régions de décision de tous les symboles d'interférence sont deux à deux disjoints. Dans le cas où les transmissions simultanées sont non synchronisées et effectuées dans un canal bruité dissipatif, nous proposons une modulation multidimensionnelle de dimension quatre appelée MNC (Modulation Network Coding), et dans laquelle deux symboles de dimension deux (symbole pilote et symbole d'information) issus d'une constellation M-PAM (Pulse Amplitude Modulation) de rotation pi/4 sont couplés pour constituer le symbole MNC qui est alors transmis par chaque nœud. Les résultats analytiques et de simulation dans les cas du 4-TRAQAM et du MNC montrent qu'il est ainsi possible de séparer deux symboles constituant une collision avec une faible probabilité d'erreur des symboles. Dans la deuxième partie de cette thèse, pour faire du CRP (Codage Réseau Physique) une technique de dissémination de l'information dans les réseaux mobiles pair-à-pair effective, nous proposons des techniques d'accès multiples propices aux transmissions simultanées contrôlées. Nous présentons ainsi deux protocoles d'accès au canal : le protocole VPNC-MAC (Physical-layer Network Coding based MAC protocol for VANETS) adapté aux réseaux véhicule-à-véhicule à une zone, et le protocole MAP (Medium Access for Physical-layer Network Coding) favorable à la dissémination de l'information dans un réseau véhiculaire multi-saut (plusieurs zones). La spécificité des protocoles d'accès multiple proposés est qu'ils permettent la mise en place des transmissions multiples contrôlées par une approche décentralisée sans avoir recours explicitement à des échanges de messages de contrôle. Les résultats des simulations montrent que la combinaison des techniques d'accès au canal VPNC-MAC ou MAP et des techniques de décodage MNC et/ou 4-TRAQAM permet d'améliorer considérablement la dissémination de l'information dans les réseaux mobiles pair-à-pair, comparativement aux méthodes conventionnelles.