Proximity Neighbor Selection in Tree-Based Structured Peer-to-Peer Overlays

Miguel Castro, Peter Druschel, Y. Charlie Hu, and Antony Rowstron

Abstract

Structured peer-to-peer (p2p) overlay networks provide a useful substrate for building distributed applications. They assign object keys to overlay nodes and provide a primitive to route a message to the node responsible for a key. Proximit neighbor selection (PNS) can be used to achieve both low delay routes and low bandwidth usage but it introduces high overhead. This paper presents a detailed evaluation of PNS and heuristic approximations. We describe a new heuristic called constrained gossiping (PNS-CG) and show that it achieves performance similar to perfect PNS with low overhead. We also compare constrained gossiping with previous heuristics and show that it achieves better performance with lower overhead.

Details

Publication typeTechReport
NumberMSR-TR-2003-52
Pages11
InstitutionMicrosoft Research
> Publications > Proximity Neighbor Selection in Tree-Based Structured Peer-to-Peer Overlays