 امروز سه شنبه ، ۱۴۰۱/۰۳/۰۳

# 3.3 کادملیا: | 3.3 Kademlia:

The basic principle of Kademlia  is to successively find nodes that are half the distance to the target node.

Kademlia differs from Pasty and other such overlays in mainly two different aspects.

One difference is a new notion of node closeness based on XOR of the node identities.

The other difference is Kademlia nodes contain lists of entries, referred to as buckets, which are used to send parallel requests.

The lookup algorithm uses a XOR-based closeness to reduce the lookup space.

The intuition behind the XOR based closeness is that node IDs that are different at higher order bits matter more than node IDs that are different in lower order bits and hence, the XOR dis- tance would be higher.

Using this XOR metric, Kademlia’s topology orders nodes as a tree where subtree nodes are closer together than other subtrees.

Routing table and key lookup: Routing tables contain separate lists for each bit in the node ID.

Hence if a network uses 128 bits for node IDs each node will have 128 lists (called buckets in Kademlia).

Each list corresponds to a particular distance to nodes.

Distance is measured in matching bits in the node IDs.

Nodes in the nth list have a differing nth bit from the current node’s ID whereas the first n − 1 bits match those of the current node’s ID.

To define distance between nodes, Kademlia uses XOR metrics.

Here the result of the XOR operation applied to two node IDs (returning 0 for identical bits and 1 for differing bits) is the distance between two nodes.

Like Chord, Kademlia nodes know about more nodes near to them and fewer nodes further away.

Figure 4 shows a routing table for a node with ID 000..00.

Note that there are k-buckets, each of which covers an address space based on the XOR metric of node IDs.

Each of these buckets is a list that may contain multiple contacts for a given subtree.

Maintenance of these buckets is straightforward though highly unbalanced trees are handled separately.

Maintenance of the nodes in the lists could be depen- dent on the applications.

A Kademlia lookup node first finds the k-closest nodes to the given node ID.

Kademlia recursively picks a subset, l, of these k-closest nodes and sends a request to all the l nodes.

In the next recursive step, the Kademlia lookup node again picks a subset of nodes from the nodes it learned about from the previous request.

Intu- itively, each of these recursive reduces the XOR metric distance by 1/2 and results in the smaller size k-buckets.

The concurrent lookup provides a trade off between bandwidth and lookup latency.

Node join and leave: Node joins mirror node lookups.

That is, a node, u, that wishes to join adds a previously known contact, w, to its bucket and performs a node lookup.

It fills up its routing table based on the responses and inserts itself into the k-buckets of the other nodes in the system.

There is no specific mechanism for node departures as other nodes may discover through the PING mechanism.