VoroNet: A scalable object network based on Voronoi tessellations - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2006

VoroNet: A scalable object network based on Voronoi tessellations

(1) , (2) , (3) , (2)
1
2
3

Abstract

In this paper, we propose the design of VoroNet, an object-based peer to peer overlay network relying on Voronoi tessellations, along with its theoretical analysis and experimental evaluation. VoroNet differs from previous overlay networks in that peers are application objects themselves and get identifiers reflecting the semantics of the application instead of relying on hashing functions. Thus it provides a scalable support for efficient search in large collections of data. In VoroNet, objects are organized in an attribute space according to a Voronoi diagram. VoroNet is inspired from the Kleinberg's small-world model where each peer gets connected to close neighbours and maintains an additional pointer to a long-range node. VoroNet improves upon the original proposal as it deals with general object topologies and therefore copes with skewed data distributions. We show that VoroNet can be built and maintained in a fully decentralized way. The theoretical analysis of the system proves that the routing in VoroNet can be achieved in a poly-logarithmic number of hops in the size of the system. The analysis is fully confirmed by our experimental evaluation by simulation.
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.
Fichier principal
Vignette du fichier
RR-5833.pdf (305.55 Ko) Télécharger le fichier
Vignette du fichier
RR2006-11.pdf (524.02 Ko) Télécharger le fichier
Loading...

Dates and versions

inria-00071210 , version 1 (23-05-2006)

Identifiers

  • HAL Id : inria-00071210 , version 1

Cite

Olivier Beaumont, Anne-Marie Kermarrec, Loris Marchal, Etienne Rivière. VoroNet: A scalable object network based on Voronoi tessellations. [Research Report] RR-5833, LIP RR-2006-11, INRIA, LIP. 2006, 2+21 p. ⟨inria-00071210⟩
249 View
594 Download

Share

Gmail Facebook Twitter LinkedIn More