Review: Handling Churn in DHT
Sean Rhea, Dennis Geels, Timothy Roscoe, and John Kubiatowicz, "Handling Churn in a DHT", Proceedings of the USENIX Annual Technical Conference, June 2004.
This paper analyzes the impact of churning of the participating peers in a structured overlay based P2P system. Three aspects of the DHT-based systems are considered for this analysis: (a) the means of maintenance of the routing table; (b) deciding the optimal time-out for queries; and (c) effectiveness of different proximity-based neighbor selection algorithms under churning.
The paper recommends periodic route maintenance over proactive updates. Under proactive update, as soon as a node finds out a neighbor is failed, it informs all of its other neighbors immediately. While this helps to keep the routing tables strictly upto date, in systems under high churning it results in high overhead. In those conditions, the paper observes, periodic updates performs much better.
Time-out for search queries have to be optimal: low values can results in unnecessary duplicated requests while high values increase the collective response time of the system. There are few methods used in literature to calculate the optimal time out: TCP-style time-outs uses past history values of the delays between nodes to estimate the future time-outs; virtual coordinates-based time-outs uses the virtual coordinates assigned to the nodes to estimate the delay and times out if the current value differ too much from the predicted value. The paper founds the TCP-style time out performs better than the other.
It is accepted in the existing literature that it is better to have entries in the routing tables which point to nodes that are closer to the current node. The paper explore different techniques to find such proximity neighbors for routing table entries when the system nodes are under churning. The paper presents the performance of mechanisms such as global sampling, neighbor's neighbors, neighbors' inverse neighbors, and their variations and combinations. It concludes the a combination of global sampling with any of the other mechanism is the best candidate.
Even though the techniques and algorithms presented in this paper is not very much new, it does look novel for its work on analyzing these techniques under churning. We need more of these works to fully understand the impact of churning in P2P systems. Read more!
This paper analyzes the impact of churning of the participating peers in a structured overlay based P2P system. Three aspects of the DHT-based systems are considered for this analysis: (a) the means of maintenance of the routing table; (b) deciding the optimal time-out for queries; and (c) effectiveness of different proximity-based neighbor selection algorithms under churning.
The paper recommends periodic route maintenance over proactive updates. Under proactive update, as soon as a node finds out a neighbor is failed, it informs all of its other neighbors immediately. While this helps to keep the routing tables strictly upto date, in systems under high churning it results in high overhead. In those conditions, the paper observes, periodic updates performs much better.
Time-out for search queries have to be optimal: low values can results in unnecessary duplicated requests while high values increase the collective response time of the system. There are few methods used in literature to calculate the optimal time out: TCP-style time-outs uses past history values of the delays between nodes to estimate the future time-outs; virtual coordinates-based time-outs uses the virtual coordinates assigned to the nodes to estimate the delay and times out if the current value differ too much from the predicted value. The paper founds the TCP-style time out performs better than the other.
It is accepted in the existing literature that it is better to have entries in the routing tables which point to nodes that are closer to the current node. The paper explore different techniques to find such proximity neighbors for routing table entries when the system nodes are under churning. The paper presents the performance of mechanisms such as global sampling, neighbor's neighbors, neighbors' inverse neighbors, and their variations and combinations. It concludes the a combination of global sampling with any of the other mechanism is the best candidate.
Even though the techniques and algorithms presented in this paper is not very much new, it does look novel for its work on analyzing these techniques under churning. We need more of these works to fully understand the impact of churning in P2P systems. Read more!
posted by Unknown at
12:05 AM
|
0 comments
