Analytical study on improving dht lookup performance under churn

The phenomenon of churn degrades the lookup perfor-mance of DHT-based P2P systems greatly. To date, a num-ber of approaches have been proposed to handle it from both the system side and the client side. However, there lacks theoretical analysis to direct how to make design choices under different churn levels and how to configure their parameters optimally. In this paper, we analytically study three important aspects on improving DHT lookup performance under churn, i.e., lookup strategy, lookup par-allelism and lookup key replication. Our objective is to build a theoretical basis for DHT designers to make better design choices in the future. We first compare the perfor-mance of two representative lookup strategies- recursive routing and iterative routing, and explore the existence of better alternatives. Then we show the effectiveness of par-allel lookup in systems with different churn levels and how to select the optimal degree of parallelism. Due to the im-portance of key replication on lookup performance, we also analyze the reliability of replicated keys under two different replication policies, and discuss how to make configuration in different environments. Besides analytical study, our re-sults are also validated by simulation, and Kad [1] is taken as a case to show the meaningfulness of our analysis.