DONUT: Building Shortcuts in Large-Scale Decentralized Systems with Heterogeneous Peer Distributions

Résumé : Les systèmes distribués à grande échelle rassemblent des milliers de noeuds répartis dans le monde. Ces systèmes doivent offrir de bonnes performances de routage indépendamment de leur taille et malgré le taux élevé de connexion\slash déconnexion. Pour cela, le système doit ajouter des raccourcis à son graphe logique (\emph{overlay} en anglais). Cependant, pour construire raccourcis efficaces, les pair ont besoin d'avoir des informations sur la topologie de l'overlay. En cas de distributions de pairs hétérogènes, la récupération de ces informations n'est pas simple. En outre, en raison du fort taux de connexion/déconnexion, la topologie évolue rapidement, ce qui rend vite les informations recueillies obsolètes. Les systèmes de l'état de l'art, soit évitent le problème en forçant les pairs à adopter une distribution uniforme, soit ne satisfont que partiellement les exigences de performances de routage. Pour faire face à ce problème, nous proposons DONUT, un mécanisme de construction d'une carte locale qui se rapproche de la distribution des pairs. Cette carte permet d'estimer localement, avec précision, la distance graphique avec les autres pairs. L'évaluation réalisée avec une matrice de latences réelles et des traces de connexion/déconnexion montre que notre carte augmente l'efficacité du routage d'au moins 20%, comparativement aux techniques de l'état de l'art. Elle montre également que chaque carte est petite et peut être propagé efficacement à travers le réseau en consommant moins de 10 bps sur chaque pair.
Type de document :
Rapport
[Research Report] RR-7614, inria. 2011, pp.20
Liste complète des métadonnées

https://hal.inria.fr/inria-00591922
Contributeur : Sébastien Monnet <>
Soumis le : mardi 10 mai 2011 - 14:58:28
Dernière modification le : mardi 17 avril 2018 - 11:30:59
Document(s) archivé(s) le : samedi 3 décembre 2016 - 04:45:36

Fichier

RR-7614.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00591922, version 1

Collections

Citation

Sergey Legtchenko, Sébastien Monnet, Pierre Sens. DONUT: Building Shortcuts in Large-Scale Decentralized Systems with Heterogeneous Peer Distributions. [Research Report] RR-7614, inria. 2011, pp.20. 〈inria-00591922〉

Partager

Métriques

Consultations de la notice

423

Téléchargements de fichiers

154