Kistree: A reliable constant degree DHT

This paper discusses the design and evaluation of Kistree, a reliable, fault-tolerant and self-configuring constant degree distributed hash table (DHT) for peer-to-peer systems. The Kistree topology can be thought of as log(n) vertically stacked layers or levels. At each level, we divide the whole identifier space into segments to form an n-ary tree structure. The nodes and keys belong to a particular segment at a level in Kistree network depending on the node / key identifier. A node in Kistree contacts with a constant number of nodes at the next level to forward queries. A node also creates a link with a node at the topmost level to get a global view of the system. This way Kistree keeps a constant number of neighbors in the routing table and traverses a logarithmic number of nodes to route a query to its destination. An insert operation stores a key on a number of diverse nodes of a concerned segment. The lookup operation, on the other hand, retrieves a stored key efficiently and reliably. The prototype implementation of Kistree on PeerSim verifies its scalability, reliability and efficiency. The experimental results achieved with a network of 50,000 nodes confirm its self-configurability and ability to route messages even under a high rate of churn.