commit 3a4a6dc27419141f2d59a00c2566e93976488d54
parent 311337aafa35cae0044841ece773b56899e0355f
Author: Christian Grothoff <grothoff@gnunet.org>
Date: Sun, 20 Aug 2023 16:41:28 +0200
minor edits and clarifications
Diffstat:
1 file changed, 33 insertions(+), 23 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -529,7 +529,9 @@ Connectivity | |Underlay| |Underlay| | Underlay | ...
This call tells the underlay to drop the connection to a
peer <tt>P</tt>. This call is only there for symmetry and
used during the peer's shutdown to release all of the remaining
- HOLDs. As R<sup>5</sup>N always prefers the longest-lived
+ <tt>HOLDs</tt>.
+ <!-- FIXME: are we supposed to call DROP if a peer disconnects!?? -->
+ As R<sup>5</sup>N always prefers the longest-lived
connections, it would never drop an active connection that it
has called <tt>HOLD()</tt> on before. Nevertheless, underlay implementations
should not rely on this always being true. A call to <tt>DROP()</tt> also
@@ -624,21 +626,26 @@ Connectivity | |Underlay| |Underlay| | Underlay | ...
<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
- <tt>PEER_CONNECTED</tt>, information on the new neighbor
- <bcp14>MUST</bcp14> be added to the routing table.
+ Upon receiving a connection notification from the
+ <em>underlay interface</em> through a
+ <tt>PEER_CONNECTED</tt> signal, information on the new neighbor
+ <bcp14>MUST</bcp14> be added to the routing table, except if the
+ respective bucket in the routing table is full or if meta-data
+ is present that indicates that the peer does not wish to participate
+ in routing.
Peers added to the routing table <tt>SHOULD</tt> be signalled to the
- Underlay as important connections using <tt>HOLD</tt>.
- Similarly when a disconnect is indicated by the Underlay through
- <tt>PEER_DISCONNECTED</tt> messages for all addresses of the peer it
+ underlay as important connections using a <tt>HOLD</tt> call.
+ Similarly when a disconnect is indicated by the underlay through
+ a <tt>PEER_DISCONNECTED</tt> signal, the peer
<bcp14>MUST</bcp14> be removed from the routing table.
+ <!-- FIXME: are we supposed to call DROP if we called HOLD if a peer disconnects!?? -->
</t>
<t>
- In order to achieve logarithmically bounded routing performance,
+ To achieve logarithmically bounded routing performance,
the data structure for managing neighbors and their
metadata <bcp14>MUST</bcp14> be implemented using the k-buckets concept of
<xref target="Kademlia"/> as defined in <xref target="routing_table"/>.
- Maintenance of the routing table (after bootstrapping) is
+ Maintenance of the routing table (after <em>bootstrapping</em>) is
described in <xref target="find_peer"/>.
</t>
<t>
@@ -651,7 +658,8 @@ Connectivity | |Underlay| |Underlay| | Underlay | ...
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
+ the peer selection for the first <tt>L2NSE</tt> hops is random. After the initial
+ <tt>L2NSE</tt> hops, peer selection
follows an XOR-based peer distance calculation.
<xref target="routing_functions"/>
describes the corresponding routing functions.
@@ -659,37 +667,39 @@ Connectivity | |Underlay| |Underlay| | Underlay | ...
<section anchor="routing_table">
<name>Routing Table</name>
<t>
- Whenever a <tt>PEER_CONNECTED</tt> signal is received from the Underlay,
+ Whenever a <tt>PEER_CONNECTED</tt> signal is received from the underlay,
the respective peer is considered for insertion into the routing table.
- The routing table consists of an array of k-buckets. Each
- k-bucket contains a list of neighbors.
- The i-th k-bucket stores neighbors whose peer IDs are between distance 2<sup>i</sup> and 2<sup>i+1</sup> from the local peer.
+ The routing table consists of an array of <tt>k</tt>-buckets. Each
+ <tt>k</tt>-bucket contains a list of <em>neighbors</em>.
+ The i-th <tt>k</tt>-bucket stores neighbors whose peer IDs are
+ between distance 2<sup>i</sup> and 2<sup>i+1</sup> from the local peer.
System constraints will typically force an implementation to impose some
- upper limit on the number of neighbors kept per k-bucket.
+ upper limit on the number of <em>neighbors</em> kept per <tt>k</tt>-bucket.
Upon insertion, the implementation <bcp14>MUST</bcp14> call
- <tt>HOLD</tt> on the respective connection.
+ <tt>HOLD</tt> on the respective <em>neighor</em>.
</t>
<t>
Implementations <bcp14>SHOULD</bcp14> try to keep at least
- 5 entries per k-bucket. Embedded systems that cannot manage
+ 5 entries per <tt>k</tt>-bucket. Embedded systems that cannot manage
this number of connections <bcp14>MAY</bcp14> use connection-level
signalling to indicate that they are merely a client utilizing a
DHT and not able to participate in routing. DHT peers receiving
such connections <bcp14>MUST NOT</bcp14> include connections to
- such restricted systems in their k-buckets, thereby effectively
+ such restricted systems in their <tt>k</tt>-buckets, thereby effectively
excluding them when making routing decisions.
</t>
<t>
If a system hits constraints with respect to
the number of active connections, an implementation
- <bcp14>MUST</bcp14> evict peers from those k-buckets with the
+ <bcp14>MUST</bcp14> evict <em>neighbours</em> from those <tt>k</tt>-buckets with the
largest number of neighbors. The eviction strategy <bcp14>MUST</bcp14> be
- to drop the shortest-lived connections first.
+ to drop the shortest-lived connection per <tt>k</tt>-bucket first.
</t>
<t>
- The implementation <bcp14>MAY</bcp14> cache valid HELLOs of disconnected
- peers outside of the routing table and sporadically or periodically try to (re-)establish connection
- to the peer by issuing <tt>TRY_CONNECT</tt> requests on the Underlay.
+ The implementation <bcp14>MAY</bcp14> cache valid <em>addresses</em> of disconnected
+ <em>peers</em> outside of the routing table and sporadically or periodically try to (re-)establish connection
+ to the <em>peer</em> by making <tt>TRY_CONNECT</tt> calls to the <em>underlay interface</em>
+ if the respective <tt>k</tt>-bucket has empty slots.
</t>
</section>
<section anchor="find_peer">
