# Building Something Like BitTorrent Part 2: The Router

## The Router Construction

The **Router** is the fundamental data structure in Kademlia. It's a graph, stored locally by each peer, that contains the contact information of other peers. Kademlia is similar to the Chord protocol in that each peer should not store the contact information (i.e., the endpoint for RPC calls) for all other peers in the DHT; instead, if the total number of the peers in the DHT is $O(N)$, each peer only stores the contact information for $O(log N)$ peers in the DHT.

The Router is a binary tree where each node of the tree is labeled by a **prefix**: a bit string with $\leq K$ bits (recall that $K$ is the number of bits in a Key). The router can be defined recursively with 4 rules (we'll assume that the peer that stores this router has the Key $B_1B_2...B_K$, where each $B_i \in \{0, 1\}$; I'll refer to this peer as the "local peer"):
- the root node of the tree has the empty prefix
- for a node with a prefix $C_1C_2...C_l$
- if $C_l \neq B_l$, then the node is a leaf
- if $l = K$, then the node is a leaf
- otherwise, add children to the node: its left child has the prefix $C_1C_2...C_l0$ and its right child has the prefix $C_1C_2...C_l1$

Essentially, at each fork node in the tree (starting from the root), we create two children nodes, each with a prefix gotten by adding either a 0 or a 1 to its parent's prefix. The child with the prefix that still "matches up" with the local peer's key will continue to recurse downwards (until we terminate when the node's prefix is just the local peer's entire key). The child with the prefix that does not "match up" will terminate as a leaf.

Here's an example of such a Router, where the local peer's key is $011$, and the prefix of each node is the $\leq K$ bits that are not marked with an X.

digraph hierarchy {
    nodesep=1.0

    node [color=Black,fontname=Courier,shape=box] //All nodes will this shape and colour
    edge [color=Black] //All the lines look like this

    "XXX"->{"0XX" "1XX"}
    "0XX"->{"00X" "01X"}
    "01X"->{"010" "011"}
}

At each of the leaves, we store a **kbucket**: a finite list of maximum size $k$ (not to be confused with the $K$ bits in a Key) that stores peers' contact information. The invariant that we set for the Router is that the **kbucket at the node with prefix $B_1B_2...B_l$ stores all Keys that match the first $l - 1$ bits of the local peer's Key** (i.e., bit $l$ is the lowest bit (starting from the leftmost bit of the Key) that is different between the Keys of the local peer and the non-local peer).

For example, a peer with Key $001$ would be stored at node $00X$ in the above router, since this non-local peer matches the first 2 - 1 = 1 bits of the local peer's key $011$.

There's exactly one kbucket that satisfies this constraint for a peer with an arbitrary key. At each level $l$ of the tree there's exactly one kbucket corresponding to the prefix that differs from the local peer's Key at bit $l$ (we'll ignore the kbucket on level $K$ that has the whole prefix equal to the local peer's Key). So, if $l \in \{1,...,K\}$ is the lowest bit that is different between the two peers' Keys, then the single kbucket at level $l$ is the kbucket where we will store the peer's contact information. [1] [2]

## Peer Distance
**The big picture:** Kademlia uses this peculiar router structure to prioritize storing the contact information of "closer" peers.

The metric used to compare the "closeness" of peers is the XOR of their Keys (or more coarsely, the longer the matching prefix between two Keys, the closer they are). We can demonstrate this with an example where the local peer's Key is $111$. We can visualize where all possible Keys in the Key-space end up being placed in the Router:

digraph hierarchy {
    nodesep=1.0

    node [color=Black,fontname=Courier,shape=box] //All nodes will this shape and colour
    edge [color=Black] //All the lines look like this

    A [label="XXX"]
    B [label="0XX\n{000, 001, 010, 011}"]
    C [label="1XX"]
    D [label="10X\n{100, 101}"]
    E [label="11X"]
    F [label="110\n{110}"]
    G [label="111"]
    
    A->{B,C}
    C->{D,E}
    E->{F,G}
}

The Key-space is partitioned very unevenly among the buckets, and this is intential: as the total number of peers in the system increases beyond the capacity of the Router ($k * K$), half of the entire Key-space is still limited to $k$ slots in the kbucket at level 1, while the remaining half get the remaining $k * (K - 1)$ slots (and this half of the Key-space is similarly split between $k$ and $k * (K - 2)$ slots, and so on).

Take a non-local peer with a key that has a prefix that matches the first $l - 1$ bits of the local peer's key. If the total number of peers in the system is $\alpha * 2^K$ for $\alpha \in [0, 1]$, then the non-local peer will be "fighting" against about $\alpha * 2^{K - l}$ other peers for $k$ slots; i.e., the change of getting placed in the Router is proportional to

$$k * (\alpha * 2^{K - l})^{-1} = C * 2^l$$

So, the probability of a Key being located in the router is an **exponential** function of $l$ (here recall that the longer the matching prefix, the closer the Keys).

## Introduction to the Search Algorithm

The motivation for a router structure with this probability property can be seen with an informal example (that will ultimately lead us to a rough outline of the final Kademlia search protocol).

Let's suppose we have a local peer with a key of all ones ($11..1$) and it finds itself in its worst-case scenario: it needs to contact a peer with the key of all zeros ($00.0$).

Since the search key matches the first 0 bits of the local peer's key, the probability of the local peer storing the key is proportional to $2^0$.

However, while the probability of locally storing this peer's key is very low, what if we ask the peers that we do store; namely the ones whose keys start with $1$? If we select a peer with a prefix of $1$ ($P_1$) and ask them to perform the algorithm, the probability of $P_1$ storing the key is proportional to $2^1$.

If again $P_1$'s search fails, it can reference its own Router to find a peer with a prefix of $11$ ($P_2$), and the probability of $P_2$ storing the key is proportional to $2^2$ .

And so on, until eventually we hit a peer that stores the key (or can confidently tell us that the key does not exist). This search algorithm is **binary search over the Key-space**: on each iteration we halve the input space by asking a peer with enough relevant granularity in its Router to continue the binary search algorithm. This algorithm clearly helps us find any other peer in the system, but Kademlia uses it more generally to find any entity associated with a Key in the system. Ultimately, this algorithm will be how we find a chunk in the DHT when we want to perform a lookup to the DHT.

The benefits of an algorithm like this are apparent: we can now find a Key in $O(logN)$ time while storing $O(logN)$ peers, as opposed to storing all peers locally, which would allow us to find a key in $O(1)$ time while storing $O(N)$ peers. Additionally, recall that Kademlia is built on the assumption that our system has a few long-lived peers ("founders") and is mostly short-lived peers ("transients"). We'll now see how Kademlia combines this assumption and $O(logN)$ local space usage to determine which peers to store locally.

## LRU-ish kbucket Insertion/Eviction Algorithm

A Kademlia peer initially joins a DHT using the endpoint of just one other peer; however over the course of its lifetime it may "interact" (i.e. send/receive RPC calls) with any and all peers. Each time a peer interacts with another peer, it should attempt to store the contact information of the non-local peer in the router. This requires us to implement an insertion/eviction algorithm to determine which peers' information to store.

**The big picture:** Kademlia prioritizes storing the contact information of **founders over transients**.

The insertion algorithm proceeds roughly as follows:

Router::insert(Peer peer) {
    get the kbucket corresponding to peer's key
    if the kbucket is not full:
        insert the peer at the front of the kbucket
    else:
        select the LRU peer at the tail of the kbucket
        try to message the LRU peer
        if the LRU peer does not respond:
            insert the new peer at the front of the kbucket
            evict the LRU peer from the kbucket
        else:
            discard the new peer
}

This is a typical LRU cache with one key difference: if the LRU element of the kbucket is still alive then we do not evict the LRU peer. This is where founders are prioritized: as long as a founder peer is still alive it will not be evicted from non-local peers' routers. Whereas, transient peers will quickly die (or leave and return with a new assigned Key) and will be evicted as soon as they are pushed to the back of their corresponding kbucket.

-----

[1] **An implementation note:** for a large $K$ (e.g. $K = 160$), it's not necessary to immediately create the entire router with all 160 kbuckets when the router is initialized. Rather, we can gradually expand the router as peers are added. For example, we can create the router with a single leaf node corresponding to the root (empty prefix) and add all other peers to this kbucket. Once we have $k + 1$ peers in the router, we can (i) add two children as specified by the recursion rule, and (ii) transfer all peer contact information from the root node to the correct child. This is how I've implemented the router in the code reference.
The choice of whether to fully create the router or not at initialization can lead to a difference in the choice of which peers are ultimately stored; however this difference disappears once we saturate the router.

[2] The Kademlia paper applies an additional requirement onto router structure: **"Kademlia nodes [i.e., peers] keep all valid contacts in a subtree of size at least $k$ nodes."** I didn't include this requirement for 3 reasons.
- I don't understand what this requirement means specifically.
- The motivating example for this rule provided by the paper is (i) unlikely to occur, and (ii) as far as I can tell, does not have any deleterious impact on the Kademlia protocol
- This change significantly complicates our analysis of the router above (I'm not sure how I would incorporate the modification since I'm not even sure what it means or when it's applied).