DChord: An Efficient and Robust Peer to Peer Lookup System.
Kim, Chul-Su, and Lee, Sanghwan, and Han, Jae-Il, and Lee, Yong-Joon, and Park, Jong-Hyun, (2010) DChord: An Efficient and Robust Peer to Peer Lookup System. Malaysian Journal of Computer Science, 23 (1). pp. 37-48. ISSN 0127-9084
Official URL: http://ejum.fsktm.um.edu.my/ArticleInformation.aspx?ArticleID=876
Electronics and Telecommunications Research Institute, South Korea
Kookmin University, South Korea
Dynamic Hash Tables (DHTs) are distributed systems that maintain key-value pairs and provide efficient lookup services. Traditional DHTs usually rely on a random ID distribution of the keys to achieve such efficiency. Uniformly random hash functions are typically used to create uniformly random ID distributions from non-random key distributions. However, there are many cases where such random hash functions cannot be applied. For example, those systems that provide range queries over the keys cannot apply random hash functions on the keys, otherwise, the range query is very difficult to support. In this paper, we present a new lookup system called DChord, which does not depend on the randomness assumption to achieve its performance. To show the performance of the proposed system, we provide mathematical analysis and extensive simulation results in a highly non-random USN (Ubiquitous Sensor Network) metadata identifier space. To be specific, we show that DChord has high regularity in terms of in-degree and out-degree distributions. Thus, the system is robust against random node failures. We also show that query processing load is well balanced among nodes and the lookup speed is deterministic in such a way that the number of nodes to visit for a query is at most log2(N).
|Additional Information:||This work was partly supported by the IT R&D program of MIC/IITA [2006-S022-02, Development of USN Middleware Platform Tech] and research program 2009 of Kookmin University in Korea. Sanghwan Lee is the corresponding author of this paper.|
|Keywords:||Lookup, USN, Deterministic, DHT, DChord|
|Subjects:||Q Science, Computer Science|
Repository Staff Only: item control page