lsd0004

commit 8153f62a68fd2fa19deb7f57944d60db388ad311
parent 4651a10a7458697717ef0e96d71125ff27f828ae
Author: Martin Schanzenbach <mschanzenbach@posteo.de>
Date:   Tue,  7 Sep 2021 17:28:37 +0200

update peer selection

Diffstat:
M
draft-schanzen-r5n.xml
 | 
45
++++++++++++++++++++++++++++++++++++++++++---

1 file changed, 42 insertions(+), 3 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -251,11 +251,50 @@ see how we can offer even the most minimal protections against peer
    </section>
    <section anchor="routing" numbered="true" toc="default">
      <name>Routing</name>
-     <section anchor="peer_distance" numbered="true" toc="default">
-       <name>Peer distance</name>
-     </section>
      <section anchor="peer_selection" numbered="true" toc="default">
        <name>Peer selection</name>
+       <t>
+         In order to select peers from the routing table which are suitable
+         destinations for sending messages, R5N uses a hybrid approach:
+         Given an estimated network size N, the peer selection for the
+         first N hops is random. After the initial N hops, peer selection
+         follows an XOR-based peer distance calculation.
+       </t>
+       <t>
+         As the message traverses a random path through the network for the
+         first N hops, it is essential that routing loops are avoided.
+         In R5N, a bloomfilter is used as part of the routing metadata in
+         messages. The bloomfilter is updates at each hop with the hops
+         peer identity.
+         For the next hop selection in both the random and the deterministic
+         case, any peer which is in the bloomfilter for the respective message
+         is not included in the peer selection process.
+       </t>
+       <!-- Fixme: We may want to propose our modified, optimized XOR metric here or reference Kademlia -->
+       <t>
+         The procedure to select a peer for a given message key and bloomfilter
+         is defined as follows:
+       </t>
+       <figure>
+         <artwork name="" type="" align="left" alt=""><![CDATA[
+PEER-SELECT(key, bloomfilter)
+  peers := <Select all known peers NOT in message bloomfilter>
+  IF hops >= N
+    dist := MAX_VALUE
+    FOR EACH p IN peers
+      IF XOR(p, key) < dist
+        dist := XOR(p, key)
+        target := p
+      END
+    END
+  ELSE
+    r := rand()
+    target := peers[r]
+  END
+END
+         ]]></artwork>
+     </figure>
+
      </section>
    </section>
    <section anchor="p2p_messages" numbered="true" toc="default">