Review: Proximity Neighbor Selection in Tree-Based Structured Peer-to-Peer Overlays
Miguel Castro, Peter Druschel, Y. Charlie Hu and Antony Rowstron, "Proximity Neighbor Selection in Tree-Based Structured Peer-to-Peer Overlays,", Microsoft Technical Report, MSR-TR-2003-52
Structured P2P networks route queries based on the randomly assigned node IDs. Therefore, the path a query takes is short in terms of the node ID space, but not necessarily in the network delay space. The ratio of the network latency a message experience in a DHT-based routing to the actual delay between the source and destination is called stretch and it is generally larger than 1 in DHT-based overlays. In order to reduce the stretch in the queries, proximity neighbor selection (PNS) was suggested, which makes sure the entries in the routing table of a node are closer to the node in terms of network latency. However strict PNS generally results in high overhead.
This paper proposes a heuristic for PNS in Pastry based on constrained gossiping, called PNS-CG. PNS-CG refines the original Pastry node join and routing table maintenance. It also provides an intelligent algorithm for nearest seed selection for node joins (which was done by expanding ring search in the original Pastry).
In the new protocol, a new node joining the Pastry overlay gossip with the nodes on the way to the final join, so that the new node can fill the rows in its routing table from the information received from each node on the way. Also the new node advertises itself to those nodes so that they can update their routing tables. The other major part of the PNS-CG is to periodically gossip with one random node from each row in the routing table, to update its routing table with more suitable (proximity wise) and alive nodes.
The paper compares this heuristic with perfect PNS and shows that the performance of the new heuristic is very much comparable.
Structured P2P networks route queries based on the randomly assigned node IDs. Therefore, the path a query takes is short in terms of the node ID space, but not necessarily in the network delay space. The ratio of the network latency a message experience in a DHT-based routing to the actual delay between the source and destination is called stretch and it is generally larger than 1 in DHT-based overlays. In order to reduce the stretch in the queries, proximity neighbor selection (PNS) was suggested, which makes sure the entries in the routing table of a node are closer to the node in terms of network latency. However strict PNS generally results in high overhead.
This paper proposes a heuristic for PNS in Pastry based on constrained gossiping, called PNS-CG. PNS-CG refines the original Pastry node join and routing table maintenance. It also provides an intelligent algorithm for nearest seed selection for node joins (which was done by expanding ring search in the original Pastry).
In the new protocol, a new node joining the Pastry overlay gossip with the nodes on the way to the final join, so that the new node can fill the rows in its routing table from the information received from each node on the way. Also the new node advertises itself to those nodes so that they can update their routing tables. The other major part of the PNS-CG is to periodically gossip with one random node from each row in the routing table, to update its routing table with more suitable (proximity wise) and alive nodes.
The paper compares this heuristic with perfect PNS and shows that the performance of the new heuristic is very much comparable.
posted by Unknown at
3:05 PM
0 Comments:
Post a Comment
<< Home