What if the routing is recursive?

[solokyo]

Hi,

I am new to the P2P storage system. and I'm still learning.
I know go-libp2p-kad-dht is based on the Kademlia paper. In the paper, Kademlia is designed to perform the routing in an iterative way and this project implemented the routing in that way. Also the libp2p Kademlia DHT specification says:

The below is one possible algorithm to find nodes closest to a given key on the DHT.

I want to know if there is any restriction so the kad-dht has to implement the routing in an iterative way. If not, what if the routing is recursive? What are the advantages and disadvantages of recursive routing?

[guillaumemichel]

There are multiple reasons to prefer iterative routing over recursive routing:

• Concurrency: go-libp2p-kad-dht is implemented with a concurrency factor, allowing multiple concurrent inflight messages for the same request. Because of the concurrent requests, the node is expected to be returned a set of more than 20 (bucket size) peers for each Hop. It selects the best peers to contact for the next Hop using this large set.
  With recursive routing and the same concurrency factor (same number of inflight messages), the lookup happens on distinct paths. Lookup over distinct paths is expected to be less efficient because if a message times out, the whole lookup path is slowed down, and each node only learns about 20 peers at each Hop.
  Centralizing the results on the requester node allows to take more informed decisions for each hop, and minimizes the impact of timeouts.
• Lookup Termination: In an iterative setting, the requester decides when the request terminates in the case they don't find the key/peer. In a recursive setting, a remote peer (probably closest to the requested key), needs to take the decision to continue the request or stop it at each Hop.
• Amplification Attacks: In an iterative setting, for each message that the requester is sending, only 1 message is generated from a remote peer: the answer to this request (if any).
  In a recursive setting, for each message sent by the requester #Hops messages are generated by remote peers in the network. Requesting for keys that don't exist will generate a lot of traffic. Therefore, in order to make one keyspace region of the DHT unreachable, requesting many forged keys in this area isn't expensive and will keep the DHT Servers of this keyspace region busy, so they will be slow to answer other legit DHT requests.