Structured peer-to-peer

From P2P Wiki

(Redirected from Structured)

1 Overview
2 Comparison
3 See also
4 Papers

Overview

As we saw in unstructured p2p systems resource location was non-deterministic (a resource could be in the network, but not found). In structured systems, the idea is that if a specific resource is on the network, it should be found. To find it, the philosophy changes, and these networks start becoming structured node groupings. Nodes are arranged in a structured fashion, typically following tree or ring formations. The objective is to assign particular nodes to store particular content. When a node wishes to look for a resource, it must be redirected to the node which is supposed to hold it.

The challenges of these structured peer-to-peer networks are:

To avoid bottlenecks in particular nodes, thus distributing responsibilities evenly among the existing peers.
To adapt to nodes joining or leaving (or failing). As a consequence, it is logical to give new responsibilities to joining nodes, and redistribute responsibilities from leaving nodes.

These challenges perfectly match the idea of a hash table Distributed Hash Table, in which each data item is associated with a key. The key is hashed to find its corresponding bucket in the hash table. Each bucket is expected to hold #items/#buckets items. In order to map this data structure to our problem, it is considered that nodes are the buckets in our global Distributed Hash Table (DHT). Therefore, the key is hashed to find the resource‘s responsible peer node, obtaining data and load balancing across nodes. As a consequence, we can define Distributed Hash Tables as a class of decentralized distributed systems that partition ownership of a set of keys among participating nodes, and can efficiently route messages to the unique owner of any given key. Each node is analogous to a bucket in a hash table. DHTs are typically designed to scale to large numbers of nodes and to handle continual node arrivals and failures. This infrastructure can be used to build more complex services, such as distributed file systems, p2p file sharing systems, cooperative web caching, multicast, anycast, and domain name services.

Some well known DHTs are Chord, Pastry, Tapestry, and Content Addressable Network. Not a DHT-approach but a structured P2P network is HyperCuP.

The challenge to develop scalable unstructured Peer-to-Peer applications has attracted the research community. Thanks to the advantages of decentralized self-organizing systems, researchers focused on approaches for distributed, content-addressable data storage (Distributed Hash Tables). Those were developed to provide distributed indexing as well as scalability, reliablility and fault tolerance. DHTs outperform unstructured approaches in the latter listed properties. Commonly, a data item can be retrieved from the network with a complexity of O(log N). The underlying network and the number of peers in structured approaches can grow arbitrarily without impacting the efficiency of the distributed application; this is in marked contrast to the previously described unstructured Peer-to-Peer applications which usually exhyibit linear search complexity at best. Management operations, such as adding new content or peers and handling failures, have a complexity of O(log N) and O(log2N) respectively.

Many systems have adopted this scheme, starting with Content Addressable Networks and Chord, which were the first to appear, followed by Tapestry, Pastry, Kademlia, Symphony and Bamboo. This kind of structured peer-to-peer overlay networks are often called Key Based Routing (KBR) substrates, since message routing depends upon node identifiers.