Séminaire REGAL
P2P overlays : VoroNet and RayNet
Thursday, October 30, 2008Étienne Rivière
Abstract Searching in large networks is one of the core functionalities offered by peer to peer systems. Among the numerous peer to peer networks that have been proposed in the past 5 years, structured peer to peer networks implementing a distributed hash table mechanism have generated lots of interest. Such networks organize physical nodes in a structure that heavily relies on the use of hashing functions to ensure load balancing. Such networks offer an exact-match interface which make them natural candidates for file systems or archival systems in which requests target well identified files. Conversely, they are not built to handle range queries on either one or several attributes, mainly due to the hashing mechanism.
We propose two novel structured overlays, named VoroNet and RayNet. These object-based overlays create a structure among objects that uses both Voronoi tessellations and small-world principles for efficient routing. They differ 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. This enables a scalable support for efficient and expressive search in large collections of data. VoroNet and RayNet are inspired from the Kleinberg's small-world model where each peer gets connected to close neighbors and maintains an additional pointer to a long-range neighbor. VoroNet and RayNet improves upon the original proposal as it deals with general object topologies and therefore copes with skewed data distributions. While VoroNet uses an explicit construction of the routing structure and the Voronoi tessellation, RayNet relies on estimating the very same structure and using gossip-based overlay construction protocols. Both will be explained and pros/cons will be discussed. In particular, the ability of RayNet to cope with dynamic scenario, mobile objects and higher dimensionality will be presented. The properties of both overlays are conveyed by simulation results.
Biography Etienne Riviere received his PhD in Computer Science from Université de Rennes 1 in November 2007. His thesis, "Collaborative overlay networks for decentralized search in large-scale distributed systems" was conducted under the guidance of Anne-Marie Kermarrec. He is currently an ERCIM research fellow. After nine months at University of Neuchâtel, he is heading for a second 9 months period in NTNU Trondheim in Norway. His research interest lie in the design, analysis and implementation of large-scale distributed systems. More specifically, he is interested in search mechanisms, publish-subscribe, content dissemination networks, decentralized management, and self-organizing systems. He also has a strong interest in epidemic- and gossip-based protocols.