---
# System prepended metadata

title: Kademlia optimization

---

# Kademlia optimization
## 1. Content hit probability.
Assume that the lookup request has arrived and the nearest k-bucket index is ${r}$. Suppose that only one content provider may exist in a k-bucket whose entry number is ${k}$. If the provider is hit by ${i}$-th hop, ${i}$ is ranged from 0 to ${r}$. The content hit probability starting from ${r}$-th k-bucket, i.e., ${P_{query}(r)}$ is defined as
\begin{eqnarray}
P_{query}(r) = \sum_{i=0}^r{\prod_{k=1}^{i-1} \left(1-\frac{1}{k}\right)\frac{1}{k}}. 
\end{eqnarray}
## 2. Expected iteration count
Let define the number of lookup concurrency as ${\alpha}$, and the maximum lookup iteration is ${\frac{k}{\alpha}}$. The lookup hit probability within one iteration is 
\begin{eqnarray}
\alpha P_{query}(r). 
\end{eqnarray}
Thus, the probability that the provider is not found within one iteration is 
\begin{eqnarray}
1-\alpha P_{query}(r). 
\end{eqnarray}
The content hit probability by 2nd iteration is 
\begin{eqnarray}
\left(1-\alpha P_{query}(r)\right)\alpha P_{query}(r).
\end{eqnarray}
The expected iteration count is defined as 
\begin{eqnarray}
E_{ite}(r) = \sum_{i=0}^{\frac{k}{\alpha}}\left\{{i\times \left(1-\alpha P_{query}(r)\right)^{i-1}\alpha P_{query}(r)}\right\}
\end{eqnarray}
Thus, we can? derive the optimal $k$ and $\alpha$ using ${E_{ite}(r) =1}$. 