Koorde - beyond Kademlia

[Kubuxu]

Koorde is a DHT based on Chord, and the driving principle is a bit different than Kademlia.
Instead of using XOR metric Chord (and Koorde) interprets keyspace as a circle.

Connecting nodes to the next node in the circle (successor) create the basis of the network. As long as there exists this connection forward, the DHT is fully functional (albeit slow). By maintaining additional connections across the circle, Koorde achieves logarithmic lookup we expect from the DHT.

This is where Koorde and Chord diverge and where the improvement of Koorde comes in. The important benefit of Koorde is its ability to use multiple connections across the network efficiently.

By using (for example) 16 connections, instead of 2, Koorde can reduce the number of required messages (and new connections) by a factor of more than 4 (from 26 to 6.3 on average).

It is important to point out significant differences of Koorde from Kademlia:

• Koorde is a bit more fragile than Kad, mostly because it keeps such a small state. Instead of remembering 100s of nodes in k-buckets, number of connections is configuration and optimization factor of Koorde
  • The resilience of Koorde is a fully tuneable parameter by selecting nodes in succession we want to maintain. After one immediate successor fails we take over its role, and we already have a connection to the new successor.
  • While increasing the resilience of Koorde, above also increases its performance but allowing quicker correction of lookup attempts.
• Each key, in Koorde, has precisely one correct node assigned to it. It is also a major difference between Koorde and Kad; there are multiple ways to increase resilience for values. These are few ways of dealing with it:
  • Storing keys also in nodes nearby in keyspace (a bit problematic)
  • Generating multiple keys k' from k with use of hashing: k'(i) = SHA256(k || i)
• Nodes in Koorde can cooperate if one of them has to leave the network. Leaving node then transfers its key-value store to its predecessor and allows it to take over. This cooperation can also be done ahead of time to reduce key loss for unexpected failures.
• Koorde can perform with O(log(n)/log(m)) lookup complexity where n is the number of nodes in the network and m is the number of nodes across the circle we maintain connection (degree).

---

In my opinion, and in comparison with Kademlia, Koorde can function as a highly cooperative network but can resist possible failures and attacks. While it might not be a perfect fit for organized chaos type network (what we do currently with our Kademlia), I firmly believe that it can function extremely well in case of delegated routing schemes with dedicated routing network with multiple independent parties cooperating.

With metrics as low as 5.6 messages per lookup I think sub-1 second record lookup time should be possible which would be a major improvement over our current DHT.

---

I have created a toy implementation of Koorde in Go (https://github.com/Kubuxu/go-toy-koorde-dht). It currently implements the lookup algorithm, but I plan to implement the rest of the protocol there to scope out possible issues. It also provides a way to benchmark the implementation and parameters. These are the results:
https://docs.google.com/spreadsheets/d/1PgkvrYWYynu-lS-B8kjjGCuqJqol4nqnleNJzV8brcE/edit?usp=sharing

---

Koorde paper: https://www.comp.nus.edu.sg/~bleong/hydra/related/kaashoek03koorde.pdf
Chord paper: https://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf

[dirkmc]

Could you please explain a little more what you mean when you say Koorde can use 16 connections instead of 2.. are these connections to direct successor nodes in the ring, or are they connections across the ring to node n + 2^(k - 1)? Where does the number 2 come from?

Also when you say connection, do you mean a connection that is kept open (eg TCP) or do you mean that the address of a peer at that ring position is stored locally, and an RCP to it can be made (eg using UDP)

[Kubuxu]

Normal so-called degree-2 Koorde maintains a connection with a successor node and node that is before id 2*m where m is our ID (forwarding connection).

degree-N core maintains N forwarding connections. The nodes are N*m plus N-1 successive nodes.

Essentially successor nodes are used for correction of requests (linear progress), and forwarding connections are used to make exponential progress (in keyspace), but we might have to correct them (make linear progress for some time) if we jumped to close. One of the points of Koorde is showing that the linear progress will have an upper, constant limit.

Also when you say connection, do you mean a connection that is kept open (eg TCP) or do you mean that the address of a peer at that ring position is stored locally, and an RCP to it can be made (eg using UDP)

TCP vs UDP is an implementation detail, but when I say connection, I mean that we have to track those nodes closely. In the case of successor connections, we have to check if they didn't fail to maintain the stability of the network. We will also receive join requests to the network through them. They might want to hand over a key-value store to go offline etc.

In case of forwarding connections (across the circle) we will use them for every request (with equal probability), and the same story, we want to maintain them to tell when they fail so we can recover.

If something is unclear, ask.

[dirkmc]

That's clear, thank you 👍

[Stebalien]

cc @jhiesey @anacrolix

[aschmahmann]

Having more libp2p implementations of routing systems and DHTs for us to work with certainly seems like a 👍.

As was mentioned, Koorde, Kademlia, etc. have different benefits and use cases, so it could be really interesting to see if we can use the testbed to exercise performance under varying types of normal and adversarial conditions.

[zot]

We used to use Pastry in 2008, an early ring-based p2p system, and we had a great experience with it (except that it wasn't very good with NAT).

It's great to see an alternative DHT, a diversity of implementations will make libp2p stronger!