Efficiency of tree-structured peer-to-peer service discovery systems

Abstract

(ENG) The efficiency of service discovery is a crucial point in the development of fully decentralized middlewares intended to manage large scale computational grids. The work conducted on this issue led to the design of many peer-to-peer fashioned approaches. More specifically, the need for flexibility and complexity in the service discovery has seen the emergence of a new kind of overlays, based on tries, also known as lexicographic trees. Although these overlays are efficient and well designed, they require a costly maintenance and do not accurately take into account the heterogeneity of nodes and the changing popularity of the services requested by users. In this paper, we focus on reducing the cost of the maintenance of a particular architecture, based on a dynamic prefix tree, while enhancing it with some load balancing techniques that dynamically adapt the load of the nodes in order to maximize the throughput of the system. The algorithms developed couple a self-organizing prefix tree overlay with load balancing techniques inspired by similar previous works undertaken for distributed hash tables. After some simulation results showing how our load balancing heuristics perform in such an overlay and compare to other heuristics, we provide a fair comparison of this architecture and similar overlays recently proposed. (FRE) L’efficacité de la découverte de services est un point crucial du développement d’intergiciels de grille totalement décentralisés. Les travaux ayant pour but la résolution de ce problème ont généré un certain nombre d’approches pair-à-pair. le besoin de flexibilité et d’expressivité a donné lieu au développement d’architecture s’appuyant sur des arbres de préfixes (ou arbres lexicographiques). Ces overlays souffrent d’une maintenance couteuse et ne prennent pas en compte la nature hététogène de la plate-forme physique sous-jacente et la popularité différente et changeante de chaque ressource enregistrée. Dans ce rapport, nous nous focalisons sur la réduction du cout de maintenance d’une telle architecture, basée sur un arbre de préfixes dynamique, tout en lui donnant la possibilité de s’adapter à l’hétérogénéité précitée par l’enrichissant de mécanismes de répartition de la charge qui adaptent dynamiquement la charge des noeuds dans le but de maximiser le débit su service. Notre approche couple des travaux de répartition de la charge dans les DHTs avec un overlay en arbre de préfixes auto-organisant. Après des résultats de simulation mettant en évidence l’efficacité de notre heuristique, nous comparons notre approche avec les travaux s’appuyant sur des structures distribuées similaires.