文档介绍：1
Analytical Study on Improving Lookup
Performance of Distributed Hash Table
Systems under Churn
Di Wu, Ye Tian, Kam Wing Ng
Department puter Science & Engineering
The Chinese University of Hong Kong
Shatin, ., Hong Kong
Email: ******@
Abstract
Distributed hash table (DHT) systems can provide infrastructure supports for a wide variety of -scale
applications. However, the phenomenon of system churn (., system dynamics) degrades the lookup performance
of DHT systems and adversely impact the performance of applications built on top of them. To date, a number
of approaches have been proposed to handle the churn from both the system side and the client side, but most
of these approaches demonstrate their feasibility under certain scenarios via simulation or empirical experiments.
There lacks theoretical analysis to direct how to make design choices under different scenarios and how to configure
their parameters optimally. In this paper, we analytically study three important aspects on improving DHT lookup
performance under churn: lookup strategy, lookup parallelism and lookup key replication. Our objective is to build
a theoretical basis for DHT designers to make better design choices for practical deployment. We pare the
performance of two representative lookup strategies - recursive routing and iterative routing, and explore the existence
of better alternatives. Then we show the effectiveness of parallel lookup in systems with different churn rates and
how to select the optimal degree of parallelism. Due to the importance of key replication on lookup performance,
we analyze the expected lifetime of replicated keys under two different replication policies, and discuss how to make
configuration in different environments. Besides analytical study, our results are also validated by simulation, and
Kad [1] is taken as a case to show the meaningfulness of our analysis.
I. INTRODUCTION
In recent years, the Di