diff options
author | Martin Schanzenbach <mschanzenbach@posteo.de> | 2021-09-07 17:28:37 +0200 |
---|---|---|
committer | Martin Schanzenbach <mschanzenbach@posteo.de> | 2021-09-07 17:28:37 +0200 |
commit | 8153f62a68fd2fa19deb7f57944d60db388ad311 (patch) | |
tree | 727c241ad7882348efe103b4dc8b0fdf9f442c78 | |
parent | 4651a10a7458697717ef0e96d71125ff27f828ae (diff) | |
download | lsd0004-8153f62a68fd2fa19deb7f57944d60db388ad311.tar.gz lsd0004-8153f62a68fd2fa19deb7f57944d60db388ad311.zip |
update peer selection
-rw-r--r-- | draft-schanzen-r5n.xml | 45 |
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[ | ||
280 | PEER-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 | ||
294 | END | ||
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"> |