Academic literature on the topic 'Tables de hachage distribuées [DHT]'

Ce mémoire est une synthèse de nos travaux de recherche menés au sein des laboratoires d'Orange Labs (anciennement France Télécom R&D) pour répondre à une problématique identifiée par ledit opérateur et concernant les flux d'échanges en mode pair-à-pair (P2P). Communément assimilé à un échange de fichiers, le P2P a de nombreuses applications. Il correspond à une évolution du monde du logiciel, des réseaux et des équipements. Au-delà du partage, nous sommes confrontés à une puissance disponible de façon distribuée (en termes de CPU, bande passante, stockage, etc.). La montée en puissance du P2P exige de nouveaux systèmes pouvant satisfaire les besoins des usagers, mais aussi ceux des fournisseurs d'accès à Internet (FAI) et autres opérateurs de réseaux. Les premiers cherchent en permanence une bonne qualité de service (QoS) bien perceptible. Les seconds aspirent à l'optimisation de l'usage des ressources du réseau (notamment la bande-passante) et à la réduction des différents coûts d'opération et de maintenance (dont ceux découlant de leurs accords économiques inter-opérateurs). D'où l'intérêt de nos travaux de recherche qui visent à sensibiliser un réseau P2P au réseau IP sous-jacent, afin d'aboutir à un système de routage P2P efficace, en phase avec les politiques des réseaux d'infrastructures sous-jacents. Ces travaux se focalisent sur les systèmes P2P utilisant des tables de hachage distribuées (DHT), après les avoir étudiées et analysées. Ce mémoire commence par une analyse des principaux protocoles de découverte de ressources dynamiques dans les différentes architectures de réseaux P2P. Les exigences requises pour un routage P2P efficace sont par la suite établies. Il s'en suit une présentation des techniques de génération de l'information de proximité sous-jacente, ainsi que des techniques et principaux systèmes d'exploitation de cette information. Nos travaux de recherche ont abouti à la définition, la conception, la spécification et l'analyse individuelle et comparative de deux systèmes : CAP (Context-Aware P2P system) et NETPOPPS (NETwork Provider Oriented P2P System). Le premier système est sensible au contexte et introduit une sémantique dans les identifiants des pairs et des objets. Le second système est orienté opérateur de réseau, et adapte les flux P2P à la topologie sous-jacente et aux politiques de l'opérateur, tout en simplifiant la gestion des différents identifiants.

Cette thèse étudie la problématique de l’indexation et de la recherche dans les tables de hachage distribuées –Distributed Hash Table (DHT). Elle propose un système de stockage distribué des résumés de documents en se basant sur leur contenu. Concrètement, la thèse utilise les Filtre de Blooms (FBs) pour représenter les résumés de documents et propose une méthode efficace d’insertion et de récupération des documents représentés par des FBs dans un index distribué sur une DHT. Le stockage basé sur contenu présente un double avantage, il permet de regrouper les documents similaires afin de les retrouver plus rapidement et en même temps, il permet de retrouver les documents en faisant des recherches par mots-clés en utilisant un FB. Cependant, la résolution d’une requête par mots-clés représentée par un filtre de Bloom constitue une opération complexe, il faut un mécanisme de localisation des filtres de Bloom de la descendance qui représentent des documents stockés dans la DHT. Ainsi, la thèse propose dans un deuxième temps, deux index de filtres de Bloom distribués sur des DHTs. Le premier système d’index proposé combine les principes d’indexation basée sur contenu et de listes inversées et répond à la problématique liée à la grande quantité de données stockée au niveau des index basés sur contenu. En effet, avec l’utilisation des filtres de Bloom de grande longueur, notre solution permet de stocker les documents sur un plus grand nombre de serveurs et de les indexer en utilisant moins d’espace. Ensuite, la thèse propose un deuxième système d’index qui supporte efficacement le traitement des requêtes de sur-ensembles (des requêtes par mots-clés) en utilisant un arbre de préfixes. Cette dernière solution exploite la distribution des données et propose une fonction de répartition paramétrable permettant d’indexer les documents avec un arbre binaire équilibré. De cette manière, les documents sont répartis efficacement sur les serveurs d’indexation. En outre, la thèse propose dans la troisième solution, une méthode efficace de localisation des documents contenant un ensemble de mots-clés donnés. Comparé aux solutions de même catégorie, cette dernière solution permet d’effectuer des recherches de sur-ensembles en un moindre coût et constitue est une base solide pour la recherche de sur-ensembles sur les systèmes d’index construits au-dessus des DHTs. Enfin, la thèse propose le prototype d’un système pair-à-pair pour l’indexation de contenus et la recherche par mots-clés. Ce prototype, prêt à être déployé dans un environnement réel, est expérimenté dans l’environnement de simulation peersim qui a permis de mesurer les performances théoriques des algorithmes développés tout au long de la thèse
This thesis examines the problem of indexing and searching in Distributed Hash Table (DHT). It provides a distributed system for storing document summaries based on their content. Concretely, the thesis uses Bloom filters (BF) to represent document summaries and proposes an efficient method for inserting and retrieving documents represented by BFs in an index distributed on a DHT. Content-based storage has a dual advantage. It allows to group similar documents together and to find and retrieve them more quickly at the same by using Bloom filters for keywords searches. However, processing a keyword query represented by a Bloom filter is a difficult operation and requires a mechanism to locate the Bloom filters that represent documents stored in the DHT. Thus, the thesis proposes in a second time, two Bloom filters indexes schemes distributed on DHT. The first proposed index system combines the principles of content-based indexing and inverted lists and addresses the issue of the large amount of data stored by content-based indexes. Indeed, by using Bloom filters with long length, this solution allows to store documents on a large number of servers and to index them using less space. Next, the thesis proposes a second index system that efficiently supports superset queries processing (keywords-queries) using a prefix tree. This solution exploits the distribution of the data and proposes a configurable distribution function that allow to index documents with a balanced binary tree. In this way, documents are distributed efficiently on indexing servers. In addition, the thesis proposes in the third solution, an efficient method for locating documents containing a set of keywords. Compared to solutions of the same category, the latter solution makes it possible to perform subset searches at a lower cost and can be considered as a solid foundation for supersets queries processing on over-dht index systems. Finally, the thesis proposes a prototype of a peer-to-peer system for indexing content and searching by keywords. This prototype, ready to be deployed in a real environment, is experimented with peersim that allowed to measure the theoretical performances of the algorithms developed throughout the thesis

Les Tables de Hachage Distribuées (Distributed Hash Tables, ou DHT, en anglais) permettent la construction de services de stockage persistant, hautement disponible, et passant à l’échelle. Cependant, leur interface put/get s’avère assez limitée : la granularité des accès se fait au niveau fichier, il existe un seul espace d’adressage plat, et la cohérence des répliques doit souvent être gérée par l’application. En revanche, un système de fichiers pair-à-pair fournit une interface plus riche et de haut niveau, tout en garantissant la compatibilité avec les applications existantes. Dans la première partie de cette thèse nous présentons Pastis, un nouveau système de fichiers pair-à-pair reposant sur la DHT PAST. Contrairement aux systèmes précédents, Pastis est complètement décentralisé et supporte un très grand nombre d’utilisateurs en lecture-écriture. D’autre part, il permet aux utilisateurs de choisir entre deux modèles de cohérence en fonction des besoins de l’application. Enfin, Pastis garantit l'authenticité et l'intégrité des données au travers de mécanismes standard de cryptographie. Notre évaluation expérimentale montre que Pastis a des performances comparables ou supérieures à celles des systèmes précédents. Dans la seconde partie nous présentons une étude sur la pérennité des données dans les systèmes de stockage pair-à-pair. Des travaux récents ont proposé d’estimer la probabilité de perte d’une donnée en utilisant un modèle basé sur des chaînes de Markov. Or, les paramètres du modèle proposées jusqu’à maintenant produisent des résultats très différents par rapport à ceux mesurés par la simulation. Nous présentons une nouvelle expression qui permet d’obtenir ces paramètres avec plus de précision, ce qui se traduit par une estimation plus réaliste de la probabilité de perte des données du système.

Les réseaux pair-à-pair (P2P) constituent un modèle de plus en plus populaire pour la programmation d’applications Internet car ils favorisent la décentralisation, le passage à l’échelle, la tolérance aux pannes et l’auto-organisation. à la différence du modèle traditionnel client-serveur, un réseau P2P est un système réparti décentralisé dans lequel tous les nœuds interagissent directement entre eux et jouent à la fois les rôles de fournisseur et d’utilisateur de services et de ressources. Une table de hachage distribuée (DHT) est réalisée par un réseauP2P et offre les mêmes services qu’une table de hachage classique, hormis le fait que les différents couples (clef, valeur) sont stockés dans différents nœuds du réseau. La fonction principale d’une DHT est la recherche d’une valeur associée à une clef donnée. Parmi les protocoles réalisant une DHT on peut nommer Chord, Pastry, Kademlia et Tapestry. Ces protocoles promettent de garantir certaines propriétés de correction et de performance ; or, les tentatives de démontrer formellement de telles propriétés se heurtent invariablement à des cas limites dans lesquels certaines propriétés sont violées. Tian-xiang Lu a ainsi décrit des problèmes de correction dans des versions publiées de Pastry. Il a conçu un modèle, appelé LuPastry, pour lequel il a fourni une preuve partielle, mécanisée dans l’assistant à la preuve TLA+ Proof System, démontrant que les messages de recherche de clef sont acheminés au bon nœud du réseau dans le cas sans départ de nœuds. En analysant la preuve de Lu j’ai découvert qu’elle contenait beaucoup d’hypothèses pour lesquelles aucune preuve n’avait été fournie, et j’ai pu trouver des contre-exemples à plusieurs de ces hypothèses. La présente thèse apporte trois contributions. Premièrement, je présente LuPastry+, une spécification TLA+ revue de LuPastry. Au-delà des corrections nécessaires d’erreurs, LuPastry+ améliore LuPastry en introduisant de nouveaux opérateurs et définitions, conduisant à une spécification plus modulaire et isolant la complexité de raisonnement à des parties circonscrites de la preuve, contribuant ainsi à automatiser davantage la preuve. Deuxièmement, je présente une preuve TLA+ complète de l’acheminement correct dans LuPastry+. Enfin, je démontre que l’étape finale du processus d’intégration de nœuds dans LuPastry (et LuPastry+) n’est pas nécessaire pour garantir la cohérence du protocole. Concrètement, j’exhibe une nouvelle spécification avec un processus simplifié d’intégration de nœuds, que j’appelle Simplified LuPastry+, et je démontre qu’elle garantit le bon acheminement de messages de recherche de clefs. La preuve de correction pour Simplified LuPastry+ est obtenue en réutilisant la preuve pour LuPastry+, et ceci représente un bon succès pour la réutilisation de preuves, en particulier considérant la taille de ces preuves. Chacune des deux preuves requiert plus de 30000 étapes interactives ; à ma connaissance, ces preuves constituent les preuves les plus longues écrites dans le langage TLA+ à ce jour, et les seuls exemples d’application de preuves mécanisées de théorèmes pour la vérification de protocoles DHT
A distributed hash table (DHT) is a peer-to-peer network that offers the function of a classic hash table, but where different key-value pairs are stored at different nodes on the network. Like a classic hash table, the main function provided by a DHT is key lookup, which retrieves the value stored at a given key. Examples of DHT protocols include Chord, Pastry, Kademlia and Tapestry. Such DHT protocols certain correctness and performance guarantees, but formal verification typically discovers border cases that violate those guarantees. In his PhD thesis, Tianxiang Lu reported correctness problems in published versions of Pastry and developed a model called {\LP}, for which he provided a partial proof of correct delivery of lookup messages assuming no node failure, mechanized in the {\TLA} Proof System. In analyzing Lu's proof, I discovered that it contained unproven assumptions, and found counterexamples to several of these assumptions. The contribution of this thesis is threefold. First, I present {\LPP}, a revised {\TLA} specification of {\LP}. Aside from needed bug fixes, {\LPP} contains new definitions that make the specification more modular and significantly improve proof automation. Second, I present a complete {\TLA} proof of correct delivery for {\LPP}. Third, I prove that the final step of the node join process of {\LP}/{\LPP} is not necessary to achieve consistency. In particular, I develop a new specification with a simpler node join process, which I denote by {\SLP}, and prove correct delivery of lookup messages for this new specification. The proof of correctness of {\SLP} is written by reusing the proof for {\LPP}, which represents a success story in proof reuse, especially for proofs of this size. Each of the two proofs amounts to over 32,000 proof steps; to my knowledge, they are currently the largest proofs written in the {\TLA} language, and---together with Lu's proof---the only examples of applying full theorem proving for the verification of DHT protocols

Le pair-à-pair (P2P) offre de bonnes solutions pour de nombreuses applications distribuées, comme le partage de grandes quantités de données et/ou le support de collaboration dans les réseaux sociaux. Il apparaît donc comme un puissant paradigme pour développer des applications distribuées évolutives, comme le montre le nombre croissant de nouveaux projets basés sur cette technologie. Construire des applications P2P fiables est difficile, car elles doivent être déployées sur un grand nombre de noeuds, qui peuvent être autonomes, refuser de répondre à certaines demandes, et même quitter le système de manière inattendue. Cette volatilité des noeuds est un comportement commun dans les systèmes P2P et peut être interprétée comme une faute lors des tests. Dans cette thèse, nous proposons un cadre et une méthodologie pour tester et valider des applications P2P. Ce cadre s'appuie sur le contrôle individuel des noeuds, permettant de contrôler précisément la volatilité des noeuds au cours de leur exécution. Nous proposons également trois différentes approches de contrôle d'exécution de scénarios de test dans les systèmes distribués. La première approche étend le coordonnateur centralisé classique pour gérer la volatilité des pairs. Les deux autres approches permettent d'éviter le coordinateur central afin de faire passer à l'échelle l'exécution des cas de tests. Nous avons validé le cadre et la méthodologie à travers la mise en oeuvre et l'expérimentation sur des applications P2P open-source bien connues (FreePastry et OpenChord). Les expérimentations ont permis de tester le comportement des systèmes sur différentes conditions de volatilité, et de détecter des problèmes d'implémentation complexes.

Les paradigmes et architectures du pair-à-pair (P2P) sont au centre des réalisations d'applications à grande échelle de tout type. Il est nécessaire d'intégrer un niveau de contrôle sur de telles applications. De telles applications seront ainsi opérées et auront comme maître d'œuvre un opérateur de services. Dans la pratique actuelle les entités pairs partageant des ressources se placent d'une manière aléatoire sur un large réseau physique (IP). Nous proposons la conception d'une architecture globale pour la mise en place de telles applications sur des plateformes de type P2P. Dans ce paradigme il est possible d'isoler trois principales composantes : la première est celle qui concerne le service applicatif, la deuxième est le routage (ou la recherche), la troisième est celle qui traite du transport des données. Ce travail consiste à optimiser chaque composante du modèle P2P. Ces études nous permettent de spécifier des structures pour trois principales contributions. La première a pour objectif de cloisonner le trafic P2P et, après généralisation, d'appliquer un algorithme sensible au contexte où chaque groupe de pairs (appartenant à un même système autonome par exemple) est basé sur une DHT (Distributed Hash Table). La seconde est d'accélérer le transfert des données à l'aide du mécanisme FEC (Forward Error Correction). La troisième est d'intégrer une entité de Contrôle/Gestion. BitTorrent est le protocole choisi au niveau transport sur une architecture intégrant ces contributions. L'architecture SPOP (Service Oriented Provider P2P) a été validée par simulation et grâce à une application de sécurité de défense contre les attaques DDoS

La sécurisation inhérente aux échanges dans les environnements dynamiques et distribués, dépourvus d’une coordination centrale et dont la topologie change perpétuellement, est un défi majeur. Dans le cadre de cette thèse, on se propose en effet de définir une infrastructure de sécurité adaptée aux contraintes des systèmes P2P actuels. Le premier volet de nos travaux consiste à proposer un intergiciel, appelé SEMOS, qui gère des sessions sécurisées et mobiles. SEMOS permet en effet de maintenir les sessions sécurisées actives et ce, même lorsque la configuration réseau change ou un dysfonctionnement se produit. Cette faculté d’itinérance est rendue possible par la définition d’un nouveau mécanisme de découplage afin de cloisonner l’espace d’adressage de l’espace de nommage ; le nouvel espace de nommage repose alors sur les tables de hachage distribuées (DHT). Le deuxième volet définit un mécanisme distribué et générique d’échange de clés adapté à l’architecture P2P. Basé sur les chemins disjoints et l’échange de bout en bout, le procédé de gestion des clés proposé est constitué d’une combinaison du protocole Diffie-Hellman et du schéma à seuil(k, n) de Shamir. D’une part, l’utilisation des chemins disjoints dans le routage des sous-clés compense l’absence de l’authentification certifiée, par une tierce partie, consubstantielle au protocole Diffie-Hellman et réduit, dans la foulée, sa vulnérabilité aux attaques par interception. D’autre part, l’extension de l’algorithme Diffie-Hellman par ajout du schéma à seuil (k, n) renforce substantiellement sa robustesse notamment dans la segmentation des clés et/ou en cas de défaillances accidentelles ou délibérées dans le routage des sous-clés. Enfin, les sessions sécurisées mobiles sont évaluées dans un réseau virtuel et mobile et la gestion des clés est simulée dans un environnement générant des topologies P2P aléatoires
Securing communications in distributed dynamic environments, that lack a central coordination point and whose topology changes constantly, is a major challenge.We tackle this challenge of today’s P2P systems. In this thesis, we propose to define a security infrastructure that is suitable to the constraints and issues of P2P systems. The first part of this document presents the design of SEMOS, our middleware solution for managing and securing mobile sessions. SEMOS ensures that communication sessions are secure and remain active despite the possible disconnections that can occur when network configurations change or a malfunction arises. This roaming capability is implemented via the definition of a new addressing space in order to split up addresses for network entities with their names ; the new naming space is then based on distributed hash tables(DHT). The second part of the document presents a generic and distributed mechanism for a key exchange method befitting to P2P architectures. Building on disjoint paths andend-to-end exchange, the proposed key management protocol consists of a combination of the Diffie-Hellman algorithm and the Shamir’s (k, n) threshold scheme. On the onehand, the use of disjoint paths to route subkeys offsets the absence of the third party’s certified consubstantial to Diffie-Hellman and reduces, at the same time, its vulnerability to interception attacks. On the other hand, the extension of the Diffie-Hellman algorithm by adding the threshold (k, n) scheme substantially increases its robustness, in particular in key splitting and / or in the case of accidental or intentional subkeys routing failures. Finally, we rely on a virtual mobile network to assess the setup of secure mobile sessions.The key management mechanism is then evaluated in an environment with randomly generated P2P topologies

ISPs are concerned about providing and maintaining the level of security of its End User's communications. A communication is initiated by the End User with a name, and goes on by exchanging packets between two IP addresses. In this thesis, we focused our attention on two main points: (1) providing a secure Naming service, and (2) making IPsec communication resilient to IP address modification, addition or lost of an interface. We designed MOBIKE-X for that purpose and propose it as a standard at the IETF

Les Tables de Hachage Distribuées (DHT) permettent la construction de réseaux pair-à-pair structurés pour des services de stockage persistant, hautement disponibles, et passant à l'échelle. Cependant, les DHTs sont peu efficaces pour gérer des requêtes complexes telles que les requêtes par intervalle. Dans cette thèse, nous nous intéressons particulièrement aux solutions reposant sur des arbres préfixes construit au-dessus des DHTs car ces arbres fournissent une solution portable et passant à l'échelle pour réaliser des requêtes complexes. Cependant, les méthodes de recherche proposées par les arbres préfixes distribués ont une latence importante et génèrent un nombre de messages élevés qui dégradent les performances du système global. De plus, certaines des solutions proposées équilibrent mal la charge des noeuds et sont inefficaces en cas d'arrivées et de départs massifs de noeuds. Dans cette thèse nous avons étendu l'arbre préfixe PHT en proposant deux solutions: PORQUE et ECHO. PORQUE vise à réduire la latence tandis qu'ECHO fournit des recherches avec un faible surcoût. Les résultats des expérimentations confirment que PORQUE et ECHO peuvent réduire la latence et le traffic réseau par rapport à PHT. Nos solutions équilibrent aussi la charge en évitant les goulets d'étranglement dans les noeuds stockant les niveaux supérieurs de l'arbre. Nous avons réalisé nos évaluations sur plusieurs ensembles de données ayant des répartitions de clés différentes. Les résultats montrent que nos solutions sont peu sensibles à l'asymétrie dans la distribution des clés tout en ayant une bonne résistance à la dynamique du réseau.