Structured Overlay Network
From SELFMAN Wiki
| Table of contents |
Structured overlay network
Editor: Boris Mejias
Formulation in terms of components and events
Structured Overlay Networks
Description
An overlay network is just a network built on top of an existing one, for instance, a peer-to-peer network built on top of the Internet. When talk about structured overlay network when such a network is built using Distributed Hash Tables (DHT).
DHT's
Within the development of peer-to-peer networks, three generations can be distinguished. The first one still uses client-server structures for several tasks, such as joining the network and searching information. Napster belongs to that group.
Second generation, identified with Gnutella and Freenet, only uses peer-to-peer connections but relay on important peers to keep information about how to find other peers. Connections in these networks are established arbitrarily and unstructured. One of the disadvantages is that the searching mechanisms may not found all the available information.
Third generation uses DHT's to structure the network, where every peer is responsible for a set of keys, which are used to organised the peers in a ring. All peers can be reached in constant time. Protocols to guarantee the consistency of the ring are based on fully decentralised algorithms, making the network be self-organised. Some of the peer-to-peer that belong to this group are Chord, Tapestry, DKS and P2PS.
Chord
I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Transactions on Networking (TON), 11(1):17–32, 2003.
DKS
Input to this work is the DKS overlay. The up-to-date description can be found in Ali Ghodsi's Thesis on [1] (http://www.sics.se/~ali/dissert.pdf).
P2PS
[2] (http://gforge.info.ucl.ac.be/plugins?id=15&type=g) Wiki home of P2PS, with description of the algorithms and the implementation architecture, based on bottom-up tiers.
[3] (http://gforge.info.ucl.ac.be/projects/p2ps/) P2Ps Website
[4] (http://p2pkit.info.ucl.ac.be) P2PKit Website
[5] (http://lists.gforge.info.ucl.ac.be/pipermail/p2ps-hackers/) Technical discussions about P2PS (read mail archives or our discussions).
Range Queries
Structured Overlay without Consistent Hashing: Empirical Results, Thorsten Schütt, Florian Schintke, and Alexander Reinefeld.Proceedings of the Sixth Workshop on Global and Peer-to-Peer Computing (GP2PC'06), May 2006.
Range Queries on Structured Overlay Networks,Thorsten Schütt, Florian Schintke, Alexander Reinefeld. Computer Communications, Special Issue on "Foundations of P2P Computing". Submitted.
A Structured Overlay for Multi-Dimensional Range Queries Thorsten Schütt, Florian Schintke, Alexander Reinefeld. Euro-Par 2007.
Self-healing
Handling Network Partitions and Mergers in Structured Overlay Networks Tallat M. Shafaat, Ali Ghodsi, Seif Haridi. Seventh IEEE International Conference on Peer-to-Peer Computing (P2P'07), September, 2007, Ireland
Dealing with Network Partitions in Structured Overlay Networks Tallat M. Shafaat, Ali Ghodsi, Seif Haridi. Journal of Peer-to-Peer Networking and Applications (PPNA), Volume 2, Number 4, December, 2009
Documents
Slides from the meeting at ZIB in Berlin, February 15-16, 2007
Advances on Structured Overlay Networks and The relaxed ring intuition
Accepted papers
Boris Mejias and Donatien Grolaux and Peter Van Roy. Improving the Peer-to-Peer Ring for Building Fault-Tolerant Grids. To be presented in the CoreGRID Workshop "Grid Programming Model, Grid and P2P Systems Architecture, Grid Systems, Tools and Environments".
Abstract Peer-to-peer networks are gaining popularity in order to build Grid systems. Among different approaches, structured overlay networks using ring topology are the most preferred ones. However, one of the main problems of peer-to-peer rings is to guarantee lookup consistency in presence of multiple joins, leaves and failures nodes. Since lookup consistency and fault-tolerance are crucial properties for building Grids or any application, these issues cannot be avoided. We introduce a novel relaxed-ring architecture for fault-tolerant and cost-efficient ring maintenance. Limitations related to failure handling are formally identified, providing strong guarantees to develop applications on top of the relaxed-ring architecture. Besides permanent failures, the paper analyses temporary failures and broken links, which are often ignored.
Note: This is a shorter version of the paper submitted to P2P2007 (see bellow) but with some additional analysis with respect the usefulness of this result in Grid computing
Tallat M. Shafaat, Ali Ghodsi, Seif Haridi. A Practical Approach to Network Size Estimation for Structured Overlays. IWSoS '08 - Third International Workshop on Self-Organizing Systems, December, 2008, Austria.
Work submitted and waiting for acceptance notification
Boris Mejias, Donatien Grolaux and Peter Van Roy. A relaxed-ring for fault-tolerant structured overlay networks. Paper submitted to the IEEE P2P2007 Conference.
Abstract One of the main problems of peer-to-peer systems using ring topology is to guarantee lookup consistency in presence of multiple joins, leaves and failures of network nodes. Lookup consistency and fault-tolerance are considered crucial properties for building applications on top of peer-to-peer networks. We introduce a novel relaxed-ring architecture where leaves and failures are considered as the same event. This approach allows us to provide a fault-tolerant join algorithm and a self-organizing ring in all cases. The relaxed-ring maintenance algorithms do not prevent the network from answering lookup requests while nodes are joining or leaving. Limitations related to failure handling are formally identified, providing strong guarantees to develop applications on top of the relaxed-ring architecture. Besides permanent failures, the paper analyses temporary failures and broken links, which are often ignored.
Donatien Grolaux, Boris Mejias, and Peter Van Roy. PEPINO: PEer-to-Peer network INspectOr. Demo proposal submitted to the IEEE P2P2007 Conference.
Abstract PEPINO is a simple and effective peer-to-peer network inspector. It visualises not only meaningful pointers and connections between peers, but also the exchange of messages between them, providing a useful tool for debugging purposes. It can monitor running networks, simulate them and log them in order to reproduce interesting case scenarios. Failures can be explicitly introduced to study fault tolerant algorithms. The graphical representation of the network uses a physical model to attract or repel peers, allowing the user to study the system from different points of view. This demo aims to present the use of PEPINO in the development of a novel relaxed-ring topology for fault tolerant networks, where the representation of the ring based on predecessors may differ from the ring based on successors. We show how PEPINO is also useful for visualising other network topologies such as perfect ring or unstructured networks.
Boris Mejias and Jorge Vallejos. Designing and Programing Self-Adaptibility in Context-Aware Systems. Extended abstract submitted to the MPOOL'07 workshop at ECOOP'07.
Notes This work is not related to Structured overlay networks, but it is related to decentralised systems. It applies the feedback-loop methodology to context-aware systems in order to provide self-adaptability.
