VoroNet: A scalable object network based on Voronoi tessellations

Abstract

Dans ce rapport, nous introduisons VoroNet, un réseau d’objets pair-à-pair reposant sur une décomposition de Voronoi de l’espace de nommage. Nous présentons à la fois le protocole, sa justification théorique ainsi que son évaluation expérimentale. VoroNet se distingue des autres réseaux pair-à-pair par le fait que dans VoroNet, les pairs sont les objets de l’application eux-mêmes et ont des identificateurs liés à la sémantique de l’application, au lieu de dépendre d’une fonction de hachage. Cela permet un support extensible pour une recherche efficace dans une grande collection de données. Dans VoroNet, les objets sont organisés dans l’espace de leurs attributs selon un diagramme de Voronoi. VoroNetest inspiré du modèle petit-monde de Kleinberg dans lequel chaque pair est connecté à des voisins proches ainsi qu’à un nœud distant. VoroNet améliore le modèle initial de Kleinberg car il gère des topologies quelconques et ainsi peut faire face à des distributions de données hétérogènes. Nous montrons que VoroNet peut être construit et maintenu de façon totalement décentralisée. L’analyse théorique du système montre que le routage dans VoroNet peut être effectué avec un nombre de sauts polylogarithmique en la taille du système. Cette analyse est confirmée par l’évaluation expérimentale, menée sous forme de simulations.