CSC 2231 Review of Pastry

Pastry is a general overlay substrate for p2p applications with a
large number of peers. It achieves good routing scalability by bounded
number of query hops, and takes into account network proximity to reduce
routing latency.

Compared with Chord, Pastry considers network proximity, and thus its
routing table is more complex. The basic idea of Pastry routing is prefix
matching, i.e., the query is forwarded to a node with the maximum length
of common prefix with the target. Like the finger table of Chord, its leaf
set can provide fine grain information about nodes close in logical space.
The routing table favors nodes in good network proximity. In addition, an
independent neighborhood set is used to keep tracking of nodes close in
network proximity. However, the proximity maintenance of Pastry depends on
some inaccuracy inference, such as triangulation inequality. Maybe some
probing techniques can be used to leverage the accuracy of its network
proximity information.

Pastry shares some similar limitations with Chord. First, there is a
tradeoff between the size of the routing table and the expected number of
routing hops. With a large base b, the maximum number of routing hops
becomes small, but the size of routing entries will increase, which
means more information need to be updated during nodes arrivals,
departures, failures. Second, it assumes the node and
key identifiers are random. This may not always hold if there are some
hotspots in specific applications, and thus load imbalance could happen.
Third, Pastry is not able to resist group malicious attacks.

In sum, Pastry is a good overlay substrate, and it has some existing
applications. But I am not sure why it is not used in practical till now.
The author of BitTorrent said "Simply figuring out which peers have what
parts of the file and where they should be sent is difficult to do without
incurring a huge overhead." So, BitTorrent simply uses a file to tracking
the location of the files. But I think this phenomenon may be due to the
lack of a good application.
Received on Sun Nov 06 2005 - 18:18:40 EST