Abstract
Structured peer-to-peer networks are scalable overlay network infrastructures that support Internet-scale network applications. A globally consistent peer-to-peer protocol maintains the structural properties of the network with peers dynamically joining, leaving and failing in the network. In this chapter, the authors discuss hierarchical distributed hash tables (DHT) as an approach to reduce the overhead of maintaining the overlay network. In a two-level hierarchical DHT, the top-level overlay consists of groups of nodes where each group is distinguished by a unique group identifier. In each group, one or more nodes are designated as supernodes and act as gateways to nodes at the second level. Collisions of groups occur when concurrent node joins result in the creation of multiple groups with the same group identifier. This has the adverse effects of increasing the lookup path length due to a larger top-level overlay, and the overhead of overlay network maintenance. We discuss two main approaches to address the group collision problem: collision detection-and-resolution, and collision avoidance. As an example, they describe an implementation of hierarchical DHT by extending Chord as the underlying overlay graph.
TopDistributed Hash Tables
Distributed hash table (Gummadi, 2003; Hsiao, 2003; Ratnasamy, 2002; Stribling, 2004) is a decentralized lookup scheme designed to provide scalable lookups, i.e., shorter lookup path length with high result guarantee and reduced number of false negative answers. The DHT protocol provides an interface to retrieve a key-value pair. A key is an identifier assigned to a resource; traditionally this key is a hash value associated with the resource. A value is an object to be stored into DHT; this could be the shared resource itself such as a file, an index or a pointer to a resource, or a resource metadata. An example of a key-value pair is <SHA1(file name), http://peer-id/file>, where the key is the SHA1 hash of the file's name and the value is the address (location) of the file.
To support scalable lookups with high result guarantee, DHT exploits the following:
Key Terms in this Chapter
Stabilization: A procedure to keep the routing information in each peer nodes updated.
Chord: A structured overlay network with nodes organized as a logical ring.
Key-value Pair: A tuple consisting of a unique identifier (key) and an object (value) to be stored into DHT.
Collision of Groups: An occurrence when two or more groups with the same group identifier occupy the top-level overlay network.
Predecessor: The immediate counter-clockwise neighbor of a node in Chord.
Finger: An entry in each node’s routing table (finger table) in Chord
Churn: Changes in overlay networks due to dynamic node joins, leaves, or failures.
Successor: The immediate clockwise neighbor of a node in Chord.
Supernode: A gateway node to a second-level hierarchical overlay network.
Distributed Hash Table: A class of distributed systems where keys are map onto nodes and nodes are organized as a structured overlay network to support scalable lookup service.