Thumbnail
Access Restriction
Open

Author Beaumont, Olivier ♦ Kermarrec, Anne-Marie ♦ Marchal, Loris ♦ Rivière, Etienne
Source Hyper Articles en Ligne (HAL)
Content type Text
File Format PDF
Language English
Subject Keyword SMALL-WORLD NETWORKS ♦ VORONOI TESSELLATIONS ♦ COMPUTATIONAL GEOMETRY ♦ OVERLAY NETWORK ♦ PEER-TO-PEER ♦ SCALABILITY ♦ Diagramme de Voronoi ♦ Réseaux petit-monde ♦ Réseau pair-à-pair ♦ Géométrie algorithmique ♦ Extensibilité ♦ info ♦ Computer Science [cs]/Other [cs.OH]
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.
Educational Use Research
Learning Resource Type Report ♦ Article
Publisher Date 2006-01-01
Publisher Institution INRIA, LIP