Pastry

Pastry

• About: http://freepastry.rice.edu/
• Discussion: https://mailman.rice.edu/pipermail/freepastry-discussion-l/

Pastry is a peer to peer content location and routing system based on a self-organizing overlay network of nodes connected over Internet. It is build to be completely decentralized, scalable, fault-resilient and to reliably route a message to the live node with the nodeID numerically closest to a key. It also automatically adapts to the arrival, departure and failure of nodes. Pastry nodes are organized in a circular ID space, each node having a unique 128 bit nodeID. The nodeID is assigned randomly when a node joins the system by computing a cryptographic of the node public key or its IP address (not practical if nodes are behind NAT). Using this naming mechanism Pastry makes the assumption that nodeID?s are generated so that the resulting set of nodeIDs is uniformly distributed in the circular nodeID space. Keys are also 128 bit values. Data associated with a key is stored in the node whose ID is numerically closest to the key.

For routing each Pastry node maintains several structures: a routing table, a neighborhood set and a leaf set. Having N nodes in the network, a node?s routing table is organized in log_2^bN rows with 2^b-1 entries in each row (the ID?s are sequence of digits in base 2^b, usually b is 1 or 4). The n?th row of the routing table contains the nodeIDs and IP addresses of those nodes whose nodeID shares the present node?s nodeID in the first n digits but differ in the n+1 digit. If there are more than 2^b-1 qualified nodes, the closest 2^b-1 nodes will be selected, according to proximity metric.

The neighborhood set contains the m closest nodes according to the proximity metric and it is not used for routing. It is used for maintaining locality properties.

The leaf set contains L numerically closest nodes:L/2 numerically smaller nodes and L/2 numerically larger nodes.

Given a message, the node first checks to see if the key falls into the range of nodeIDs covered by its leaf set. If so, the message is forwarded directly to the destination node, namely the node in the leaf set whose nodeID is closest to the key. If the key is not covered by the leaf set then the routing table is used and the message is forwarded to a node that shares a common prefix with the key by at least one more digit (so routing is based on prefix matching rather than numerical difference). It is possible that the appropriate entry in the routing table is empty or the associated node is not reachable in which case the message is forwarded to a node that shares a prefix with the key at least as long as the present node?s nodeID. Such a node must be in the leaf set unless the message has already arrived at the node with the numerically closest nodeID.

Routing in Pastry can be random meaning the choice among multiple nodes can be made randomly. In the event of a malicious or failed node along the path, the query may be repeated several times by the client until a route is chosen that avoids the bad node.

When entering the ring, a new node n asks any existing node z to route its nodeID to numerically closest node x. Every node on the path from z to x will send complete routing table to n so the i?th row in node n routing table will be initialized with i?th row of i?th node on the path from z to x. In the end n will send a copy of its resulting state to each node in its routing table, neighborhood set and leaf set.

What makes Pastry different is the fact that Pastry tries to have each entry in the route table to refer to a node that is near the node trying to take advantage of proximity routing. When routing there are potentially several nodes in the routing table closer to the message?s key in the ID space so Pastry tries to select among the set of possible next hops the one that is closest in the physical network or one that represents a good compromise between progress in the ID space and proximity.

Another interesting property is that a new node n will chose an initial contact node z closer. It can also be proved that the route table initialization also sustains the locality as every node periodically requests state from nodes in the neighborhood set in order to update its route table.

Also it is worth mentioning that if replicas of an object are stored on k nodes with adjacent nodeIDs, Pastry messages requesting the object have the tendency to first reach a node near the requesting node.

Though Pastry seems more adequate than Chord, the amount of traffic generated by adding a new node to the ring must be carefully reviewed as Edos has more than 4 millions potential clients.

Type Software

Topics Peer To Peer Wp4

{metadata}