Options
Load-balanced structures for decentralized overlays
Auteur(s)
Bianchi, Silvia Cristina
Editeur(s)
Résumé
Dans les environnements distribués à large échelle, d’énormes quantités d'informations sont échangées et accédées par de très nombreux utilisateurs. Les informations ne sont pas seulement stockées sur les serveurs, mais également par les utilisateurs qui les partagent. Ces caractéristiques particulières rendent le modèle de communication client/serveur classique inadapté à certains types d'applications émergentes. De nouveaux paradigmes ont été proposés comme alternatives, tels la communication pair-à-pair ou le modèle « publication/abonnement » qui permettent efficacement de rechercher les informations partagées sur le réseau et les diffuser aux utilisateurs intéressés. Dans cette thèse, nous nous concentrons sur le développement de mécanismes de recherche d’information permettant d'éviter les goulets d'étranglement dans les systèmes pair-à-pair à large échelle, ainsi sur la mise au point de techniques de diffusion d'information faisant un usage efficace des ressources disponibles dans le système. Dans la première partie de cette thèse, nous proposons une solution pour l’équilibrage de charge dans des systèmes pair-à-pair structurés. L'approche vise à répartir le trafic en considérant une distribution de requêtes biaisée. Pour atteindre cet objectif, nous réorganisons dynamiquement les tables de routage et nous copions les informations les plus populaires sur les chemins qui permettent d’y accéder. Ces mécanismes améliorent la répartition de la charge et, par conséquent, permettent un meilleur passage à l’échelle. Dans la deuxième partie de cette thèse, nous nous concentrons sur le problème de la diffusion d'information. Nous proposons des structures de type « R-trees » et « Hilbert R-trees » distribués pour construire un réseau applicatif pair-à-pair optimisé pour la diffusion sélective d'information. Nous adaptons les variantes de R-trees pour organiser les éditeurs et les abonnés dans un réseau structuré équilibré qui limite l'occurrence de faux positifs tout en évitant les faux négatifs. En outre, nous mettons en œuvre des algorithmes auto-stabilisant pour garantir la cohérence du système en dépit de pannes ou de variations importantes dans la population des pairs., In large scale distributed environments, huge amounts of information are exchanged and accessed by a large and dynamic number of users. The information is not only stored in servers, but also users store and share the information. Due to these characteristics, the client/server communication model is not well adapted for certain types of applications. As an alternative to the client/server model, new paradigms such as peer-to-peer and publish/subscribe have been proposed providing mechanisms to locate the information stored and shared between the users and to disseminate the information to interested users. In this thesis, we focus on developing efficient lookup mechanisms avoiding bottlenecks on large scale peer-to-peer systems and efficient information dissemination taking into account the system resources. In the first part of this thesis, we propose an adaptive load-balancing solution in structure peer-to-peer systems. The approach aims to balance the request and routing load of the peers, under biased request workloads, distributing the traffic among the peers in the overlay. We achieve the routing load balancing through a dynamic reorganization of the routing tables and the request load balancing by caching the most popular keys. We significantly improve the load balancing, and consequently their scalability and performance. In the second part of this thesis, we focus on achieving scalable and efficient information dissemination. We propose Distributed R-tree overlays and Distributed Hilbert R-trees, which use R-tree-based spatial filters to construct a peer-to-peer overlay optimized for selective dissemination of information. We adapt well-known variants of R-trees to build content-based publish/subscribe where publishers and subscribers are organized in a peer-to-peer network in order to minimize the occurrences of false positives while avoiding false negatives. In addition, we implement self-stabilizing algorithms that guarantee consistency despite failures and rapid changes in the peer populations
Notes
Thèse de doctorat : Université de Neuchâtel, 2008 ; Th. 2052
Type de publication
Resource Types::text::thesis::doctoral thesis
Dossier(s) à télécharger
