commit 33f548fa7f713bd428f7a8f41c7a6a73788ce8d9
parent f0bd851c2605178672389b72bf14575551330d3a
Author: finwo <finwo@pm.me>
Date: Thu, 23 Jul 2020 13:38:01 +0200
Added path finding note in mesh-routing draft
Diffstat:
3 files changed, 64 insertions(+), 51 deletions(-)
diff --git a/draft/0004-mesh-routing.txt b/draft/0004-mesh-routing.txt
@@ -1,51 +0,0 @@
-idea sources:
- cjdns
- mainline-dht
-
-aims to replace wide-area-networks
-
-each node has interface count
-node's address width = interface count + 1 fitting binary number
-node with 8 interfaces has an address width of 4 bits
- 0 = invalid
- 1 = self
- 2,..9 = interfaces
-
-
-routing label usage:
- "interface to route to" is MSB (first bits on wire), to forward at "wirespeed"
- when forwarding, the "hop" adds it's receiving port in reverse to the LSB while removing it's interface from the MSB
- to respond, reverse the whole routing label to reverse the path
-
- Assuming 32-bit routing labels, sending a message from Alice to Charlie via Bob, the label would look as follows entring alice's routing core
- Entering Alice's routing core:
- 0110 110000 000001 0000000000000000
- \--/ Alice(6) -> Bob(123)
- \----/ Bob(48) -> Charlie(33)
- \----/ Charlie(1) "self"
- \--------------/ Empty space
- Received by Bob on interface 123
- 110000 000001 0000000000000000 1000
- \----/ Bob(48) -> Charlie(33)
- \----/ Charlie(1) "self"
- \--/ Alice(1) reversed "self"
- Received by Charlie on interface 33
- 000001 000000000000000 1000 1101111
- \----/ Charlie(1) "self"
- \--/ Alice(1) reversed "self"
- \----/ Bob(123) reversed
- Charlie's core registers this as (flipped) return path
- 000000000000000 1000 1101111 100001
- \--/ Alice(1) reversed "self"
- \-----/ Bob(123) reversed
- \----/ Charlie(33) reversed
-
-
-
-Hard problem to solve:
- node identifiers (look at asymmetric-diffie-hellman?)
- native encryption
- shortest path to node with ID X
- service discovery
- simply searching network for service is slow AF
- named alt-net gateways
diff --git a/draft/0004-non-interactive-key-exchange.txt b/draft/0004-non-interactive-key-exchange.txt
@@ -0,0 +1,4 @@
+signatures? https://sphincs.cr.yp.to/sphincs-20150202.pdf
+Key exchange? https://github.com/finwo/asymmetric-diffie-hellman-js/
+
+
diff --git a/draft/0005-mesh-routing.txt b/draft/0005-mesh-routing.txt
@@ -0,0 +1,60 @@
+idea sources:
+ cjdns
+ mainline-dht
+
+aims to replace wide-area-networks
+
+each node has interface count
+node's address width = interface count + 1 fitting binary number
+node with 8 interfaces has an address width of 4 bits
+ 0 = invalid
+ 1 = self
+ 2,..9 = interfaces
+
+
+routing label usage:
+ "interface to route to" is MSB (first bits on wire), to forward at "wirespeed"
+ when forwarding, the "hop" adds it's receiving port in reverse to the LSB while removing it's interface from the MSB
+ to respond, reverse the whole routing label to reverse the path
+
+ Assuming 32-bit routing labels, sending a message from Alice to Charlie via Bob, the label would look as follows entring alice's routing core
+ Entering Alice's routing core:
+ 0110 110000 000001 0000000000000000
+ \--/ Alice(6) -> Bob(123)
+ \----/ Bob(48) -> Charlie(33)
+ \----/ Charlie(1) "self"
+ \--------------/ Empty space
+ Received by Bob on interface 123
+ 110000 000001 0000000000000000 1000
+ \----/ Bob(48) -> Charlie(33)
+ \----/ Charlie(1) "self"
+ \--/ Alice(1) reversed "self"
+ Received by Charlie on interface 33
+ 000001 000000000000000 1000 1101111
+ \----/ Charlie(1) "self"
+ \--/ Alice(1) reversed "self"
+ \----/ Bob(123) reversed
+ Charlie's core registers this as (flipped) return path
+ 000000000000000 1000 1101111 100001
+ \--/ Alice(1) reversed "self"
+ \-----/ Bob(123) reversed
+ \----/ Charlie(33) reversed
+
+
+Node identifiers: see SD0004 (draft)
+
+Path discovery:
+ Broadcast every N seconds presence on network (B.A.T.M.A.N. protocol)? -> too much data in large networks
+ Broadcast "who has node X"? -> might work, still a lot of meta in large networks, includes "fastest path" detection
+ Dijkstra's path finding, adding discovered neighbours to the "unvisited" list
+ Harder, will take longer, but removes overhead on further parts of the network
+ All nodes must track RTT and IDs for all their neighbours
+ Path sharing (Charlie alreay knows a path to Fred) might speed this up but will not be the ideal path
+
+Hard problem to solve:
+ node identifiers (look at asymmetric-diffie-hellman?)
+ native encryption
+ shortest path to node with ID X
+ service discovery
+ simply searching network for service is slow AF
+ named alt-net gateways
