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.

Publications 2010-2023

• 2023
  • D. Wladdimiro, L. Arantes, N. Hidalgo, P. Sens : “PRESPS: a PREdictive model to determine the number of replicas of the operators in Stream Processing Systems”, Compas 2023 - Conférence francophone d'informatique en Parallélisme, Architecture et Système, Annecy, France (2023)
• 2022
  • D. Wladdimiro, L. Arantes, P. Sens, N. Hidalgo : “A predictive approach for dynamic replication of operators in distributed stream processing systems”, SBAC-PAD 2022 - IEEE 34^th International Symposium on Computer Architecture and High Performance Computing, Bordeaux, France, pp. 120-129, (IEEE) (2022)
  • D. Wladdimiro, L. Arantes, N. Hidalgo, P. Sens : “A predictive model for Stream Processing System that dynamically calibrates the number of operator replicas”, ComPAS 2022 - Conférence francophone d'informatique en Parallélisme, Architecture et Système, Amiens, France (2022)
• 2021
  • D. Wladdimiro, L. Arantes, P. Sens, N. Hidalgo : “A Multi-Metric Adaptive Stream Processing System”, NCA 2021 - 20^th IEEE International Symposium on Network Computing and Applications, Cambridge, Boston, United States (2021)
• 2016
  • N. Hidalgo, L. Arantes, P. Sens, X. Bonnaire : “ECHO: Efficient Complex Query over DHT overlays”, Journal of Parallel and Distributed Computing, vol. 88, pp. 31-45, (Elsevier) (2016)
  • E. Rosas, N. Hidalgo, V. Gil Costa, M. Marin, C. Bonacic, H. Senger, L. Arantes, C. Marcondes, O. Marin : “Survey on Simulation for Mobile Ad-Hoc Communication for Disaster Scenarios”, Journal of Computer Science and Technology, vol. 31 (2), (Springer Verlag) (2016)
• 2014
  • F. Coriat, L. Arantes, O. Marin, A. Fladenmuller, N. Hidalgo, E. Rosas : “Towards distributed geolocation for large scale disaster management”, WSDP - Chilean Workshop on Distributed and Parallel Systems, Talca, Chile (2014)
• 2012
  • N. Hidalgo, E. Rosas, L. Arantes, O. Marin, P. Sens, X. Bonnaire : “Optimized range queries for large scale networks”, Advanced Information Networking and Applications (AINA), 26^th IEEE International Conference on, Fukuoka, Japan, pp. 438-445, (IEEE) (2012)
• 2011
  • N. Hidalgo Castillo : “Towards an Efficient Support for Complex Queries on Structured Peer-to-Peer Networks”, thèse, soutenance 29/11/2011, direction de recherche Sens, Pierre, co-encadrement : Arantes, Luciana (2011)
  • N. Hidalgo, L. Arantes, P. Sens, X. Bonnaire : “A Tabu Based Cache to Improve Latency and Load Balancing on Prefix Trees”, ICPADS 2011 - IEEE International Conference on Parallel and Distributed Systems, Tainan, Taiwan, Province of China, pp. 557-564, (IEEE) (2011)
  • N. Hidalgo, E. Rosas, L. Arantes, O. Marin, P. Sens, X. Bonnaire : “DRing: A Layered Scheme for Range Queries over DHTs”, IEEE International Conference on Computer and Information Technology, Paphos, Cyprus, pp. 29-34, (IEEE) (2011)
  • N. Hidalgo, L. Arantes, P. Sens, X. Bonnaire : “TPT-C: A Heuristic-Based Cache to Improve Range Queries over DHTs”, 24 pages (2011)
• 2010
  • N. Hidalgo, L. Arantes, P. Sens, X. Bonnaire : “An Aggregation-Based Routing Protocol for Structured Peer to Peer Overlay Networks”, AP2PS 2010 - 2^nd International Conference on Advances in P2P Systems, Florence, Italy, pp. 76-81, (ThinkMind) (2010)