出版社：University of Malaya * Faculty of Computer Science and Information Technology
摘要：Dynamic Hash Tables (DHTs) are distributed systems that maintain keyvalue 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 nonrandom 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 nonrandom USN (Ubiquitous Sensor Network) metadata identifier space. To be specific, we show that DChord has high regularity in terms of indegree and outdegree 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).
