Price of Structured Routing and Its Mitigation in P2P Systems under Churn
Joseph S. Kong, Vwani Roychowdhury · 2007
We study the resilience of structured peer-to-peer (P2P) networks in the presence of churn. Using the lifetime-based failure assumptions, we first show that a realistic churn model has an equivalent uniform failure model in the steady state. We then determine via percolation analysis and simulation the gap between the size of the connected component and the reachable component of a randomly picked node for symphony and chord. This gap represents the price of structured routing: the size of the set of nodes that are reachable by any unstructured routing method (e.g. broadcast on the unstructured overlay) from a randomly picked surviving node, but are not reachable using structured routing on the structured overlay. As an illustration, for 24- minute average node lifetime with 1-minute average node-search delay, the gap is around 12 thousand nodes or 1.2% in a chord network of around 1 million nodes. We finish by discussing potential techniques to mitigate the price of structured routing.