Peer to peer multidimensional overlays: Approximating complex structures

Olivier Beaumont 1, 2 Anne-Marie Kermarrec 3 Etienne Rivière 3
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
INRIA Futurs, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
3 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : Peer to peer overlay networks have proven to be a good support for storing and retrieving data in a fully decentralized way. A sound approach is to structure them in such a way that they reflect the structure of the application. Peers represent objects of the application so that neighbours in the peer to peer network are objects having similar characteristics from the application's point of view. Such structured peer to peer overlay networks provide a natural support for range queries. While some complex structures such as a Voronoï tessellation, where each peer is associated to a cell in the space, are clearly relevant to structure the objects, the associated cost to compute and maintain these structures is usually extremely high for dimensions larger than 2. We argue that an approximation of a complex structure is enough to provide a native support of range queries. This stems fromthe fact that neighbours are importantwhile the exact space partitioning associated to a given peer is not as crucial. In this paper we present the design, analysis and evaluation of RayNet, a loosely structured Voronoï-based overlay network. RayNet organizes peers in an approximation of a Voronoï tessellation in a fully decentralized way. It relies on a Monte-Carlo algorithm to estimate the size of a cell and on an epidemic protocol to discover neighbours. In order to ensure efficient (polylogarithmic) routing, RayNet is inspired from the Kleinberg's small world model where each peer gets connected to close neighbours (its approximate Voronoï neighbours in Raynet) and shortcuts, long range neighbours, implemented using an existing Kleinberg-like peer sampling.
Type de document :
[Research Report] RR-6248, INRIA. 2007, pp.19
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 25 juillet 2007 - 09:47:59
Dernière modification le : mercredi 11 avril 2018 - 01:56:40
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 17:38:14


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00164667, version 2


Olivier Beaumont, Anne-Marie Kermarrec, Etienne Rivière. Peer to peer multidimensional overlays: Approximating complex structures. [Research Report] RR-6248, INRIA. 2007, pp.19. 〈inria-00164667v2〉



Consultations de la notice


Téléchargements de fichiers