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.

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.

Untitled

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

https://i.imgur.com/Pnq2KRn.png