An analytical study on optimizing the lookup performance of distributed hash table systems under churn
Publication in refereed journal

CUHK Authors
Author(s) no longer affiliated with CUHK

Times Cited
Web of Science5WOS source URL (as at 27/05/2020) Click here for the latest count
Altmetrics Information

Other information
AbstractThe phenomenon of system churn degrades the lookup performance of distributed hash table (DHT) systems greatly. To handle the churn, a number of approaches have been proposed to date. However, there is a lack of theoretical analysis to direct how to make design choices under different churn rates and how to configure their parameters optimally. In this paper, we analytically study three important aspects on optimizing DHT lookup performance under churn, i.e. lookup strategy, lookup parallelism and lookup key replication. Our objective is to build a theoretical basis for designers to make better design choices in the future. We first compare the performance of two representative lookup strategies-recursive routing and iterative routing-and explore the existence of better alternatives. Then we study the effectiveness of lookup parallelism in systems with different churn rates and show how to select the optimal degree of parallelism. Owing to the importance of key replication on lookup performance, we also analyze the reliability of the replicated key under two different replication policies, and show how to perform proper configuration. Besides the analytical study, our results are also validated by simulation, and Kad is taken as a case to show the meaningfulness of our analysis. Copyright (c) 2007 John Wiley & Sons, Ltd.
All Author(s) ListWu D, Tian Y, Ng KW
Journal nameConcurrency and Computation: Practice and Experience
Volume Number19
Issue Number4
Pages543 - 569
LanguagesEnglish-United Kingdom
Keywordschum; distributed hash table (DHT) system; lookup performance
Web of Science Subject CategoriesComputer Science; Computer Science, Software Engineering; COMPUTER SCIENCE, SOFTWARE ENGINEERING; Computer Science, Theory & Methods; COMPUTER SCIENCE, THEORY & METHODS

Last updated on 2020-28-05 at 03:27