summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMartin Schanzenbach <mschanzenbach@posteo.de>2021-09-07 17:28:37 +0200
committerMartin Schanzenbach <mschanzenbach@posteo.de>2021-09-07 17:28:37 +0200
commit8153f62a68fd2fa19deb7f57944d60db388ad311 (patch)
tree727c241ad7882348efe103b4dc8b0fdf9f442c78
parent4651a10a7458697717ef0e96d71125ff27f828ae (diff)
downloadlsd0004-8153f62a68fd2fa19deb7f57944d60db388ad311.tar.gz
lsd0004-8153f62a68fd2fa19deb7f57944d60db388ad311.zip
update peer selection
-rw-r--r--draft-schanzen-r5n.xml45
1 files changed, 42 insertions, 3 deletions
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
index 1d78c5b..c4e1780 100644
--- 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
251 </section> 251 </section>
252 <section anchor="routing" numbered="true" toc="default"> 252 <section anchor="routing" numbered="true" toc="default">
253 <name>Routing</name> 253 <name>Routing</name>
254 <section anchor="peer_distance" numbered="true" toc="default">
255 <name>Peer distance</name>
256 </section>
257 <section anchor="peer_selection" numbered="true" toc="default"> 254 <section anchor="peer_selection" numbered="true" toc="default">
258 <name>Peer selection</name> 255 <name>Peer selection</name>
256 <t>
257 In order to select peers from the routing table which are suitable
258 destinations for sending messages, R5N uses a hybrid approach:
259 Given an estimated network size N, the peer selection for the
260 first N hops is random. After the initial N hops, peer selection
261 follows an XOR-based peer distance calculation.
262 </t>
263 <t>
264 As the message traverses a random path through the network for the
265 first N hops, it is essential that routing loops are avoided.
266 In R5N, a bloomfilter is used as part of the routing metadata in
267 messages. The bloomfilter is updates at each hop with the hops
268 peer identity.
269 For the next hop selection in both the random and the deterministic
270 case, any peer which is in the bloomfilter for the respective message
271 is not included in the peer selection process.
272 </t>
273 <!-- Fixme: We may want to propose our modified, optimized XOR metric here or reference Kademlia -->
274 <t>
275 The procedure to select a peer for a given message key and bloomfilter
276 is defined as follows:
277 </t>
278 <figure>
279 <artwork name="" type="" align="left" alt=""><![CDATA[
280PEER-SELECT(key, bloomfilter)
281 peers := <Select all known peers NOT in message bloomfilter>
282 IF hops >= N
283 dist := MAX_VALUE
284 FOR EACH p IN peers
285 IF XOR(p, key) < dist
286 dist := XOR(p, key)
287 target := p
288 END
289 END
290 ELSE
291 r := rand()
292 target := peers[r]
293 END
294END
295 ]]></artwork>
296 </figure>
297
259 </section> 298 </section>
260 </section> 299 </section>
261 <section anchor="p2p_messages" numbered="true" toc="default"> 300 <section anchor="p2p_messages" numbered="true" toc="default">