Review: MSPastry

Miguel Castro, Manuel Costa and Antony Rowstron, "Performance and Dependability of Structured Peer-to-Peer Overlays," Technical report MSR-TR2003-94, Microsoft Research, 2003

MSPastry (probably stands for Microsoft Pastry!!) is not a new Pastry implementation, but intensively refines the routing and route maintenance techniques to makes the Pastry routing dependable. It is argued that to provide dependable routing the routing mechanism should be both consistent and reliable. consistency is defined as the guarantee to deliver a message with a key to the node that is responsible for the key, not to any other node. Reliability is defined as the guarantee for a message not to get lost on the route.

In addition to relying on the constraint gossiping proposed by the authors in a previous work (see my last blog entry), MSPastry adds some additional techniques to ensure route dependability. Obviously ensuring route dependability introduces additional overhead, but the technique proposed for MSPastry are self-tunable adjusting their overhead according to the stability of the network. That is when the system is fairly stable (not much churning), the proposed mechanism reduces their work and hence their imposed additional overhead.

MSPastry ensure a consistent routing by keeping the leaf sets consistent. "The state in the routing table is important fro performance but it is not necessary to ensure consistency." The key aspects of keeping the leaf set consistent is to (a) mark a node active (when joining) only after ensuring all the nodes in its leaf set is active by probing them; and (b) maintaining its leaf set by periodic heartbeats. However, in order to reduce the overhead of the heartbeat messages, MSPastry nodes send heartbeat messages on to its immediate left neighbors. When a node does not receive heart beat message from its right neighbor for a particular amount of time, it triggers a "suspect" routine to determine whether the right neighbor should be still in the leaf set.

The route reliability is achieved by active probing and per-hop ack messages. Under active probing, a node periodically probes each entry in its routing table to ensure they are still alive. When a route in on the way, the nodes expect to receive an ack message from the node to which the route is forwarded. If they did not receive ack, the node will reroute the message using another node from the routing table. The active probing period in MSPastry is self-tunable depending on the observed node failure rates in the network.

The paper shows by simulation and implementation that in fact MSPastry performs well in terms of dependable routing with low overhead.