OverNet

OverNet/Kademlia

Overnet used to be popular decentralized peer-to-peer computer network in 2006. It is based on Kademlia DHT and since there is no scientific paper that discuss about Overnet, we will discuss Kademlia instead.

Kademlia is a symmetric DHT based on XOR-based metric to perform the routing functionality. It treats nodes as leaves in binary tree; with each node position is determined by ID prefix. Kademlia ensures that every node knows of at least one node each of its subtrees. Node ID is represented as 160-bit number.

XOR metric is used to introduce the notion of distances between nodes in Kademlia. However, it doesn’t consider the actual location of the nodes since it uses the node ID to determine the “distance” between them. XOR is unidirectional.

Kademlia nodes store contact information about each other to route query message with maximum list of k. There are four RPC protocols in Kademlia: PING, STORE, FIND_NODE and FIND_VALUE. In Kademlia, the most important procedure for each participant is called node lookup, where by a node in Kademlia tries to find the k closest nodes to some given node ID. Kademlia employs recursive algorithm for node-lookup. The initiator is able to sends parallel, asynchronous FIND_NODE RPCs to the nodes that it has chosen. This parallelization is able to accelerate the lookup process although it increases the number of messages that circulating in the network. Nodes in Kademlia also need to periodically <key, value> pairs to keep them alive.

The routing table in Kademlia is in the form of binary trees. And it is always maintained to avoid unbalanced tree. And some optimization is performed in Kademlia to efficiently republish key.

Advantages

The notion of symmetriness using XOR metrics is good. The concept of learning about neighbor when receiving queries is interesting. It is resistant to certain degree of DoS attack. Disadvantages

Kademlia’s notion of distance does not consider the actual network distance. In the current era of geolocation, this distance notion can be improved by considering the actual network distance. Routing table in Kademlia is in the form of binary trees and it needs to maintain it periodically. This maintenance potentially has lots of message to exchange in the network.

Volunteer Computing Suitability

High churn rate causes lot of message overhead in Kademlia and make Kademlia is not really suitable for Volunteer Computing system. The message overhead here is caused by maintenance of binary tree and parralelization of node lookup message.

decentralized_storage_systems/overnet.txt · Last modified: 2012/04/23 00:58 by julia
 
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki