Pastry (http://www.freepastry.org/) is a P2P routing overlay system. FreePastry (http://www.freepastry.org/FreePastry/) is an open source implementation of Pastry and is simple enough for us to use to illustrate many of the features of a P2P system. Pastry will route messages with a network of n nodes in O(log n) steps. That is, given a network of nodes, it requires, at most, log base 2 of n steps to reach the node. This is an efficient routing approach. However, while it may only require traversing three nodes to get to a resource, it may require a considerable number of IP hops to get to it.
Pastry uses the concept of leaf sets in the routing process. Each node has a leaf set. A leaf set is a collection of GUIDS and IP addresses of nodes that are numerically closest to this node. The nodes are logically arranged in a circle, as shown next.
In the following figure, each dot represents a node with an identifier. The addresses used here range from 0
to FFFFFF
. The real addresses...