### Start Date: 11/30/2020

### End Date: ~May 2022

### Project proposal abstract:

We plan to develop a DHT-based routing scheme with underlay-aware lookup optimization for a large-scale overlay network. Our proposal has three technical/research objectives, (i) lookup optimization with the forwarding priority in terms of the balance between RTT and overlay hop count in Kademlia-based DHT, (ii) a naming scheme to map the content ID and peer IDs for multi-level DHT for efficient content lookup, and (iii) achieve churn resilience by adjusting the redundancy of content put/get procedures. We would evaluate these three objectives in terms of lookup time, message propagation time, and content hit rate by varying the network scale and each peerâ€™s preferences in the simulation. Then, we would implement these three functionalities with the Go language to be further incorporated into go-libp2p.

**GitHub**: click here.

## 1. Objective

DHT-based routing scheme with underlay-aware lookup optimization for a large-scale overlay network, named **KadRTT**. The objectives of KadRTT are as follows:

**1. Lookup optimization with low RTT and maintaining overlay hop count in Kademlia.**
Coordinate each k-bucket so that each ID is uniformly distributed so as not to bias a specific ID range to suppress redundant lookup hops.

- For each iterative lookup, a client tries to send requests to the next hops according to increasing order of RTT if it satisfies the logarithmic condition: $\frac{d(p_i^{RTT}, CID)}{d(p_i^{kad}, CID)}<2$ .
**2. Lifetime and popularity-based replication priority for churn resilience.**

As for the evaluation, we develop both simulations and a real-world module. Simulations are based on OverSim and testground, and the real-world module is the one for go-libp2p.

## 2. Basics and assumption

libp2p uses iterative routing in Kademlia, and then the total lookup time can be bounded as follows:

${ }$

$T_{query}^{kad} (p_x ,CID,D_{all} ) \le \sum\limits_{\scriptstyle i \le \log \left( {d(p_{r,0} ,CID,)} \right), \atop \scriptstyle p_x \in D_{all} } {t_{x,i}^{RTT} }$,
where ${ }$$p_x$ is a lookup client, CID is Content ID, $p_{r,0}$ is a peer in $r$-th entries of k-bucket on $p_x$ in the following figure.

For a more detailed lookup, it is shown in the following figure, where CID hit with $r$-th k-bucket on the client peer.