Information Technology Reference
In-Depth Information
use the same way to get their keys. The content objects are then placed into
the host with the key closest to themselves.
DHT-based protocols differ in the ways of how they organize the membership
of the participating hosts and how they route to locate the content objects.
1.3.1.2 Pastry
Pastry [25] is a popular large-scale DHT-based P2P network protocol devel-
oped by Microsoft Research and Rice University. Each participating node
gets its unique 128-bit node identifier (nodeId) by a hash function (e.g.,
SHA-1). Pastry uses a circular nodeId space for organizing the membership
of the nodes. Figure 1.13 shows a sample nodeId space used by Pastry. By
reading from the prefix of a nodeId, we can quickly locate a node on the cir-
cular nodeId space. The nodeId can be viewed as a sequence of digits with
base 2
b
. When
b
= 4, then the first digit in the nodeId divides the circular
nodeId space into 16 equal pieces. The second digit divides 1/16 of the circu-
lar nodeId space into another 16 equal pieces. Therefore, we can locate a node
by checking the prefix of its nodeId digit by digit (see Figure 1.14).
Figure 1.15 shows the routing table of a node in Pastry. When a node is
trying to join Pastry, it first contacts a bootstrap node that is already in the
nodeId space. The bootstrap node then routes the newly joined node to the
corresponding location in the nodeId space. During the routing, the newly
joined node collects the routing tables from the nodes it visits to create its
own routing table.
When a node tries to publish a message to the Pastry network, it first cal-
culates the hash key of the message. The message is then routed to the node
0
FFFFFFFF
40000000
C0000000
80000000
Figure 1.13
A sample nodeId space in Pastry.
