VoroNet: A scalable object network based on Voronoi tessellations

Olivier Beaumont 1 Anne-Marie Kermarrec 2 Loris Marchal 3 Etienne Rivière 2
1 SCALAPPLIX - Algorithms and high performance computing for grand challenge applications
INRIA Futurs, Université Bordeaux Segalen - Bordeaux 2, Université Sciences et Technologies - Bordeaux 1, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
2 PARIS - Programming distributed parallel systems for large scale numerical simulation
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, ENS Cachan - École normale supérieure - Cachan, Inria Rennes – Bretagne Atlantique
3 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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.
Document type :
Reports
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071210
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 2:35:49 PM
Last modification on : Monday, April 29, 2019 - 11:10:40 AM

Identifiers

  • HAL Id : inria-00071210, version 1

Citation

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⟩

Share

Metrics

Record views

508

Files downloads

414