commit ee23f6aea857c00b2b7c6d41944a35d8872488f0
parent 8853b99ce170e9a0154145791e542f8ed2402928
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Fri, 18 Aug 2023 19:09:46 +0200
FIXMEs. Some routing fixes.
Diffstat:
1 file changed, 26 insertions(+), 19 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -557,13 +557,6 @@ Connectivity | |Underlay| |Underlay| | Underlay | ...
<section anchor="routing" numbered="true" toc="default">
<name>Routing</name>
<t>
- In order to select peers which are suitable destinations for
- routing messages, R<sup>5</sup>N uses a hybrid approach:
- Given an estimated network size L2NSE, 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>
To enable routing, any R<sup>5</sup>N implementation must keep
information about its current set of neighbors.
Upon receiving a connection notification from the Underlay through
@@ -587,8 +580,16 @@ Connectivity | |Underlay| |Underlay| | Underlay | ...
Unlike <xref target="Kademlia"/>, routing decisions in
R<sup>5</sup>N are also influenced by a Bloom filter in the message
that prevents routing loops. This data structure is discussed in
- <xref target="routing_bloomfilter"/>. <xref target="routing_functions"/>
- describes the key functions provided on top of these data structures.
+ <xref target="routing_bloomfilter"/>.
+ </t>
+ <t>
+ In order to select peers which are suitable destinations for
+ routing messages, R<sup>5</sup>N uses a hybrid approach:
+ Given an estimated network size <tt>L2NSE</tt> retrieved using <tt>ESTIMATE_NETWORK_SIZE ()</tt>,
+ the peer selection for the first N hops is random. After the initial N hops, peer selection
+ follows an XOR-based peer distance calculation.
+ <xref target="routing_functions"/>
+ describes the corresponding routing functions.
</t>
<section anchor="routing_table">
<name>Routing Table</name>
@@ -739,7 +740,7 @@ Connectivity | |Underlay| |Underlay| | Underlay | ...
the leftmost bit is the most significant bit.
</dd>
<dt>
- <tt>SelectClosestpeer(K, B) -> N</tt>
+ <tt>SelectClosestPeer(K, B) -> N</tt>
</dt>
<dd>
This function selects the neighbor <tt>N</tt> from our
@@ -750,7 +751,7 @@ Connectivity | |Underlay| |Underlay| | Underlay | ...
filter <tt>B</tt> are not considered.
</dd>
<dt>
- <tt>SelectRandompeer(B) -> N</tt>
+ <tt>SelectRandomPeer(B) -> N</tt>
</dt>
<dd>
This function selects a random peer <tt>N</tt> from
@@ -759,14 +760,14 @@ Connectivity | |Underlay| |Underlay| | Underlay | ...
filter <tt>B</tt> are not considered.
</dd>
<dt>
- <tt>Selectpeer(K, H, B) -> N</tt>
+ <tt>SelectPeer(K, H, B) -> N</tt>
</dt>
<dd>
This function selects a neighbor <tt>N</tt> depending on the
number of hops <tt>H</tt> parameter.
If <tt>H < NETWORK_SIZE_ESTIMATE</tt>
- this function <bcp14>MUST</bcp14> return <tt>SelectRandompeer(B)</tt> and
- <tt>SelectClosestpeer(K, B)</tt> otherwise.
+ this function <bcp14>MUST</bcp14> return <tt>SelectRandomPeer(B)</tt> and
+ <tt>SelectClosestPeer(K, B)</tt> otherwise.
</dd>
<dt>
<tt>IsClosestPeer(N, K, B) -> true | false</tt>
@@ -1533,12 +1534,14 @@ BEGIN
the peer to be added to the respective k-bucket of the routing table (<xref target="routing"/>).
</li>
<li>
- Given the value in <tt>REPL_LVL</tt>, <tt>HOPCOUNT</tt> and the
- result of <tt>IsClosestPeer(SELF, BLOCK_KEY, PeerFilter)</tt> the number of peers to
+ Given the value in <tt>REPL_LVL</tt>, <tt>HOPCOUNT</tt> and
+ <tt>FALSE = IsClosestPeer(SELF, BLOCK_KEY, PeerFilter)</tt> the number of peers to
forward to <bcp14>MUST</bcp14> be calculated
using <tt>ComputeOutDegree()</tt>.
The implementation <bcp14>SHOULD</bcp14> select up to this
- number of peers to forward the message to. The implementation <bcp14>MAY</bcp14>
+ number of peers to forward the message to using the function <tt>SelectPeer()</tt> (<xref target="routing_functions"/>)
+ using the <tt>BLOCK_KEY</tt>, <tt>HOPCOUNT</tt>, an appropriate bloom filter (FIXME: PEER_BF?).
+ The implementation <bcp14>MAY</bcp14>
forward to fewer or no peers in order to handle resource constraints
such as limited bandwidth.
For each selected peer with peer address <tt>P</tt> a dedicated <tt>PutMessage_P</tt>
@@ -1766,7 +1769,11 @@ BEGIN
<tt>ComputeOutDegree()</tt>.
If there is at least one
peer to forward to, the implementation <bcp14>SHOULD</bcp14> select up to this
- number of peers to forward the message to. The implementation <bcp14>MAY</bcp14>
+ number of peers to forward the message to.
+ The implementation <bcp14>SHOULD</bcp14> select up to this
+ number of peers to forward the message to using the function <tt>SelectPeer()</tt> (<xref target="routing_functions"/>)
+ using the <tt>QUERY_HASH</tt>, <tt>HOPCOUNT</tt>, an appropriate bloom filter (FIXME: Start with PEER_BF?).
+ The implementation <bcp14>MAY</bcp14>
forward to fewer or no peers in order to handle resource constraints
such as bandwidth.
The peer Bloom filter <tt>PEER_BF</tt> <bcp14>MUST</bcp14> be updated with the local
@@ -1972,7 +1979,7 @@ BEGIN
<li>
If the <tt>BTYPE</tt> of the message indicates a <tt>HELLO</tt> block, the
peer <bcp14>SHOULD</bcp14> be considered for the local routing
- table by using the peer address computed from the block using<tt>DeriveBlockKey</tt>.
+ table by using the peer address computed from the block using <tt>DeriveBlockKey</tt>.
An implementation <bcp14>MAY</bcp14> choose to ignore the <tt>HELLO</tt>, for example
because the routing table or the respective k-bucket is already full.
If the peer is a suitable candidate for insertion, the local peer <bcp14>MUST</bcp14> try to establish a connection
