Review - Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems

This paper introduces Pastry which is a generic routing and content
location system for very large overlay networks like P2P systems. Nodes
in the Pastry overlay have a nodeID and route packets according to a
message and key tuple; and use only local routing information. The
packet is routed at the application level to the neighbour that has a
nodeID closest to the key. The expected number of hops in the network is
O(log N) for N peers and the content search is definitive, meaning that
if there is a matching message in the overlay, it will be found.

The strength of the paper lies in the design of a self-organizing,
highly scalable and robust system that is generic enough to be used by
many applications in need of routing and content location services. It
uses hypercube routing based on address prefixes and partitions the
nodes evenly in the nodeID space by using cryptographic functions. It
also takes advantage of network topology at the expense of a complicated
join protocol.

On the flip side, I thought the paper was not too well written. It was
confusing and hard to read. I believe that concrete examples, like in
Chord, would have helped a lot in explaining the self-organizing and
routing aspects of the Pastry system.

This study is timely as P2P systems are very popular. Although Pastry
shows a lot of scalability, it would be interesting to see the
applications that make use of the sophisticated system to achieve this
massive scalability. It is unclear how big P2P systems are in today's
Internet or how big they need to be, but so far, the popular P2P systems
deployed have worked fairly well despite using less sophisticated
algorithms.
Received on Mon Nov 07 2005 - 10:28:08 EST