Circular DHT

Circular DHT

To deal with this problem of scale. let's now look at organizing the peers into a circle. In this circular arrangement, each peer only keeps track of its immediate successor (modulo 2n). An instance of such a circle is shown in Figure 1(a). In this instance, n is again 4 and there are the same eight peers from the previous example.

A circular DHT

Each peer is only aware of its immediate successor; for instance, peer 5 knows the IP address and identifier for peer 8 but does not essentially know anything about any other peers that may be in the DHT. This circular arrangement of the peers is a particular case of an overlay network. In an overlay network, the peers form an abstract logical network which resides above the "underlay" computer network consisting of physical links, routers, and hosts. The links in an overlay network are not physical links, but are simply virtual liaisons between pairs of peers. In the overlay in Figure 1(a), there are eight peers and eight overlay links; in the overlay in figure 1(b) there are eight peers and 16 overlay links. A single overlay link normally uses many physical links and physical routers in the underlay network.

Using the circular overlay in Figure 1(a), now suppose that peer 3 wants to determine which peer in the DHT is responsible for key 11 [either for inserting  or querying for a (key-value) pair]. Using the circular overlay, the origin peer (peer 3) creates a message saying "Who is responsible for key 11?" and sends this message to its successor, peer 4. Whenever a peer receives such a message, because it knows the identifier of its successor, it can determine whether it is responsible (that is, Closest to) the key in question. If a peer is not responsible for the key, it simply sends the message to its successor. So, for instance, when peer 4 receives the message asking about key 11, it determines that it is not responsible for the key (because its successor is closer to the  key), so it just passes the message to its own successor, namely, peer 5. This process continues until the message arrives at peer 12, who determines that it is the closest peer to key 11. At this point, peer 12 can send a message back to the origin, peer 3, indicating that it is responsible for key 11.

The circular DHT provides a very elegant solution for reducing the amount of overlay information each peer must manage. Particularly, each peer is only aware of two peers, its immediate successor and its immediate predecessor. (By default, the peer is aware of its predecessor, since the predecessor is sending it messages.) But this solution introduces yet a new problem. Although each peer is only aware of two neighboring peers, to find the node responsible for a key (in the worst-case), all N nodes in the DHT will have to forward a message around the circle; NI2 messages are sent on average.

Therefore, in designing a DHT, there is tradeoff between the number of neighbors each peer has to track and the number of messages that the DHT needs to send to resolve a single query. On one hand, if each peer tracks all other peers (mesh overlay), then only one message is sent per query, but each peer has to keep track of N peers. On the other hand, with a circular DHT, each peer is only aware of two peers, but NI2 messages are sent on average for each query. Fortunately, we can refine our designs of DHTs so that the number of neighbors per peer as well as the number of messages per query is kept to an acceptable size. One such refinement is to use the circular overlay as a foundation, but add "shortcuts" so that each peer not only keeps track of its immediate successor, but also of a relatively small number of shortcut peers scattered about the circle. An instance of such a circular DHT with some shortcuts is shown in Figure 1(b). Shortcuts are used to facilitate the routing of query messages. Particularly, when a peer receives a message that is querying for a key, it forwards the message to the neighbor (successor neighbor or one of the shortcut neighbors) which is the closet to the key. Therefore, in Figure 1(b), when peer 4 receives the message asking about key 11, it determines that the closet peer to the key (among its neighbors) is its shortcut  neighbor 10 and then forwards the message directly to peer 10. Clearly, shortcuts can considerably reduce the number of messages used to process a query.

The next natural question is "How many shortcut neighbors should each peer have, and which peers should be these shortcut neighbors"? This question has received significant attention in the research community [Stoica 2001; Rowstron 2001; Ratnasamy 2001; Zhao 2004; Maymounkov 2002; Garces-Erce 2003]. Importantly, it has been shown that the DHT can be designed so that both the number of neighbors per peer as well as the number of messages per query is O(log N), where N is the number of peers. Such designs strike a satisfactory compromise between the extreme solutions of using mesh and circular overlay topologies.

Peer Churn

In P2P systems, a peer can come or go without warning. Therefore, when designing a DHT, we also must be concerned about maintaining the DHT overly in the presence of such peer churn. To get a big-picture understanding of how this could be accomplished, let's once again consider the circular DHT in Figure 1(a). To handle peer churn, we will now require each peer to track (that is, know the IP address of) its first and second successors; for instance peer 4 now tracks both peer 5 and peer 8. We also require each peer to periodically verify that its two successors are alive (for example, by periodically sending ping messages to them and asking for responses). Let's now examine how the DHT is maintained when a peer suddenly leaves. For instance, assume peer 5 in Figure 1(a) suddenly leaves. In this case, the two peers preceding the departed peer (4 and 3) learn that 5 has departed, since it no longer responds to ping messages. Peers 4 and 3 thus need to update their successor state information. Let's consider how peer 4 updates its state:

1. Peer 4 replaces its first successor (peer 5) with its second successor (peer 8).
2. Peer 4 then asks its new first successor (peer 8) for the identifier and IP address of its immediate successor (peer 10). Peer 4 then makes peer 10 its second successor.
Having briefly addressed what has to be done when a peer leaves, let's now examine what happens when a peer wants to join the DHT. Let's say a peer with identifier 13 wants to join the DHT, and at the time of joining, it only knows about peer 1's existence in the DHT. Peer 13 would first send peer 1 a message, saying "what will be 13's predecessor and successor"? This message gets forwarded through the DHT until it reaches peer 12, who realizes that it will be 13's predecessor and that its current successor, peer 15, will become 13's successor. Next, peer 12 sends this predecessor and successor information to peer 13. Peer 13 can now join the DHT by making peer 15 its successor and by notifying peer 12 that it should change its immediate successor to 13.

DHTs have been finding extensive use in practice. For instance, BitTorrent uses the Kademlia DHT to create a distributed tracker. In the BitTorrent, the key is the torrent identifier and the value is the IP addresses of all the peers currently participating in the torrent [Falkner 2007, Neglia 2007]. In this way, by querying the DHT with a torrent identifier, a newly arriving BitTorrent peer can determine the peer that is responsible for the identifier (that is, for tracking the peers in the torrent). After having found that peer, the arriving peer can query it for a list of other peers in the torrent. DHTs are also used extensively in the eMule file-sharing system for locating content in peers [Liang 2006].


peers, successor, identifier, dht, overlay network, routers, circular overlay

Copy Right

The contents available on this website are copyrighted by TechPlus unless otherwise indicated. All rights are reserved by TechPlus, and content may not be reproduced, published, or transferred in any form or by any means, except with the prior written permission of TechPlus.