Kistree: A Reliable Constant Degree DHT

Kistree: A Reliable Constant Degree DHT
일판 유섭김수현
DHT; Overlay Routing; Peer-to-peer Systems; Distributed Hash Table
Issue Date
International Conference on Networks Protocols
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 selfconfigurability and ability to route messages even under a high rate of churn.
Appears in Collections:
KIST Publication > Conference Paper
Files in This Item:
There are no files associated with this item.
RIS (EndNote)
XLS (Excel)


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.