diff options
| author | Jesper Jensen <jesper@slashwin.dk> | 2021-06-22 22:16:02 +0200 |
|---|---|---|
| committer | Jesper Jensen <jesper@slashwin.dk> | 2021-06-22 22:16:24 +0200 |
| commit | de3bec63c63b0c30a5a4e1d9b4a5478984b888e9 (patch) | |
| tree | ef2eb9ede1a2fd3c21197f4aaf57d1d7e2d70e2f /src | |
| parent | bc10650887822d214a178a16fe7948d0977aa81c (diff) | |
Move the comment into routing
Diffstat (limited to 'src')
| -rw-r--r-- | src/main.c | 26 | ||||
| -rw-r--r-- | src/routing.c | 24 |
2 files changed, 25 insertions, 25 deletions
@@ -11,30 +11,6 @@ #include <stdbool.h> #include <string.h> -// The DHT routing table has a keyspace of 0 -- 2^160 split into buckets of 8. -// When a bucket becomes full, we split it in half. As we further expand the -// routing table we only continue to split the buckets on the side we fall on. -// -// Initially, this may sound like a binary tree (because we split it in two), -// but looking at it as a flat array leads to some interesting intuitions. -// Since we only expand one half of the "tree", the total size is bounded by -// the depth of the tree log2(2^160) == 160. -// -// As a flat array we notice the intrinsic properties of the routing table. -// With a bucket size of 8, the routing table contains 160 * 8 == 1280 nodes. -// As the node ids get less similar to our own our grouping of them becomes -// less detailed. While the bucket we are in contains node very close to us, -// the nodes furthest away from us are grouped in buckets with nodes they -// barely resemble. -// -// +----------------------------+ -// | n1 | n2 | n3 | ... | n1280 | -// +----------------------------+ -// More Less -// <--------Similarity--------> -// <----------Detail----------> -// - void dbgl_id(struct nodeid* id) { for(uint8_t i = 0; i < 5; i++) { @@ -68,7 +44,7 @@ int main(int argc, char** argv) { } struct entry *found[10]; - size_t nfound = rounting_closest(&b, 10, found); + size_t nfound = routing_closest(&b, 10, found); for(size_t i = 0; i < nfound; i++) { dbgl_id(&found[i]->id); diff --git a/src/routing.c b/src/routing.c index d4eaa3f..ff7eadc 100644 --- a/src/routing.c +++ b/src/routing.c @@ -6,6 +6,30 @@ #include <stdbool.h> #include <stdlib.h> +// The DHT routing table has a keyspace of 0 -- 2^160 split into buckets of 8. +// When a bucket becomes full, we split it in half. As we further expand the +// routing table we only continue to split the buckets on the side we fall on. +// +// Initially, this may sound like a binary tree (because we split it in two), +// but looking at it as a flat array leads to some interesting intuitions. +// Since we only expand one half of the "tree", the total size is bounded by +// the depth of the tree log2(2^160) == 160. +// +// As a flat array we notice the intrinsic properties of the routing table. +// With a bucket size of 8, the routing table contains 160 * 8 == 1280 nodes. +// As the node ids get less similar to our own our grouping of them becomes +// less detailed. While the bucket we are in contains node very close to us, +// the nodes furthest away from us are grouped in buckets with nodes they +// barely resemble. +// +// +----------------------------+ +// | n1 | n2 | n3 | ... | n1280 | +// +----------------------------+ +// More Less +// <--------Similarity--------> +// <----------Detail----------> +// + #define IDBITS 160 #define BUCKETSIZE 8 // The 3 here is log2(BUCKETSIZE), since the final bucket will contain all those combinations |
