HIDALGO CASTILLO Nicolas

Docteur
Équipe : REGAL
Date de départ : 01/12/2011
https://lip6.fr/Nicolas.Hidalgo

Direction de recherche : Pierre SENS

Co-encadrement : ARANTES Luciana

Amélioration de la performance de requêtes complexes sur les systèmes pair-à-pair

Les Tables de Hachage Distribuées (Distributed Hash Tables, ou DHT, en anglais) permettent la construction de réseaux pair-à-pair structurés pour des services de stockage persistant, hautement disponibles, et passant à l'échelle. Les fonctions de hachage utilisées pour générer les clés assurent une bonne répartition des objets sur les pairs du réseau et permettent la localisation très efficace d'un objet à partir de sa clé. Cependant, les DHTs sont peu efficaces pour gérer des requêtes complexes telles que les requêtes par intervalle. Pour pallier cela, plusieurs solutions ont été proposées dans la littérature. Dans cette thèse, nous nous intéressons plus particulièrement aux solutions reposant sur des arbres préfixes (trie en anglais) 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 généralement 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 particulièrement inefficaces en cas d'arrivées et de départs massifs de noeuds (churn en anglais). Cette thèse vise donc à fournir de nouveaux supports pour les arbres préfixes au-dessus de DHT permettant de faire des requêtes complexes performantes. Nos approches assurent un bon un équilibrage de charge des noeuds stockant les index et offrent un surcoût limité en messages combiné à une latence faible. De plus, elles supportent mieux la dynamique du réseau pair-à-pair par rapport aux approches classiques. 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. Nous avons implémenté et évalué ses deux solutions au-dessus du simulateur PeerSim. Les résultats des expérimentations confirment que PORQUE et ECHO peuvent réduire la latence et le trafic réseau de plus de 50% 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 (réels et synthétiques) 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.

Soutenance : 29/11/2011 - 16h - Site Jussieu 25-26/105

Membres du jury :

Anne-Marie Kermarrec, Directrice de Recherche INRIA - Rapporteur
Claudia Roncancio, Professeur Université de Grenoble - Rapporteur
Peter Druschel, Scientific Director Max Planck Institute for Software Systems
Franck Petit, Professeur Université Pierre et Marie Curie
Xavier Bonnaire, Professeur Associé Universidad Tecnica Federico Santa Maria
Pierre Sens, Professeur Université Pierre et Marie Curie
Luciana Arantes, Maitre de Conference Université Pierre et Marie Curie

Publications 2010-2016