commit 8853b99ce170e9a0154145791e542f8ed2402928
parent f2f6d5b7d56ef7d9eca779fd5f3e69ba0abea75f
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Fri, 18 Aug 2023 18:44:11 +0200
Merge branch 'master' of git+ssh://git.gnunet.org/lsd0004
Diffstat:
1 file changed, 59 insertions(+), 41 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -29,12 +29,12 @@
<?rfc sortrefs="yes" ?>
<?rfc compact="yes" ?>
<?rfc subcompact="no" ?>
-<rfc xmlns:xi="http://www.w3.org/2001/XInclude" category="info" docName="draft-schanzen-r5n-01" ipr="trust200902" obsoletes="" updates="" submissionType="IETF" xml:lang="en" version="3">
+<rfc xmlns:xi="http://www.w3.org/2001/XInclude" category="info" docName="draft-schanzen-r5n-02" ipr="trust200902" obsoletes="" updates="" submissionType="IETF" xml:lang="en" version="3">
<front>
<title abbrev="The R5N Distributed Hash Table">
The R5N Distributed Hash Table
</title>
- <seriesInfo name="Internet-Draft" value="draft-schanzen-r5n-01"/>
+ <seriesInfo name="Internet-Draft" value="draft-schanzen-r5n-02"/>
<author fullname="Martin Schanzenbach" initials="M." surname="Schanzenbach">
<organization>Fraunhofer AISEC</organization>
<address>
@@ -131,16 +131,16 @@
<xref target="R5N"/>.
</t>
<t>
- DHTs are a key data structure for the construction of decentralized applications.
- and they generally provide a robust and efficient means to distribute the
+ DHTs are a key data structure for the construction of decentralized applications
+ and generally provide a robust and efficient means to distribute the
storage and retrieval of key-value pairs.
</t>
<t>
- The core idea behind R<sup>5</sup>N is to combine an initial randomized routing
- algorithm with an efficient, classical closest-peer algorithm.
+ The core idea behind R<sup>5</sup>N is to combine a randomized routing
+ algorithm with an efficient, deterministic closest-peer algorithm.
This allows us to construct an algorithm that is able to escape and circumvent
- restricted route environments while at the same time allow for O(log n) routing
- complexity.
+ restricted route environments while at the same time allow for a logarithmically bounded
+ routing complexity.
</t>
<t>
R<sup>5</sup>N also includes advanced features like tracing paths messages take
@@ -176,11 +176,12 @@
this document is "r5n+ip+tcp", which refers to a standard TCP/IP socket
connection. The "hier"-part of the URI must provide a suitable
address for the given addressing scheme.
- The following is a non-normative example of address strings:
+ The following are non-normative examples of address strings:
</t>
<figure title="Example Address URIs.">
<artwork name="" type="" align="left" alt=""><![CDATA[
r5n+ip+udp://1.2.3.4:6789/
+r5n+quic://example.com/
gnunet+tcp://12.3.4.5/
]]></artwork>
</figure>
@@ -189,7 +190,7 @@ gnunet+tcp://12.3.4.5/
<dd>
Applications are components which directly use the DHT overlay
interfaces. Possible applications include the GNU Name System
- <xref target="I-D.schanzen-gns"/> and the CADET transport system
+ <xref target="I-D.schanzen-gns"/> and the GNUnet CADET transport system
<xref target="cadet"/>.
</dd>
<dt>Application API</dt>
@@ -201,8 +202,9 @@ gnunet+tcp://12.3.4.5/
<dt>Block</dt>
<dd>
Variable-size unit of payload stored in the DHT
- under a <tt>Key</tt>. Commonly also called a "value" when talking
- about a DHT as a "key-value store".
+ under a <tt>Key</tt>.
+ In the context of "key-value stores" this
+ refers to "value" stored under a key.
</dd>
<dt>Block Storage</dt>
<dd>
@@ -217,9 +219,16 @@ gnunet+tcp://12.3.4.5/
Block-Types are either private or registered in the GANA block type registry (see
<xref target="gana_block_type"/>).
</dd>
+ <dt>Bootstrapping</dt>
+ <dd>
+ Bootstrapping is the initial process of establishing a connection to the peer-to-peer
+ network.
+ This initially requires an initial, non-empty set of reachable peers and corresponding
+ addresses supported by the implementation to connect to.
+ </dd>
<dt>Initiator</dt>
<dd>
- The peer that initially creates and sends a message (<xref target="p2p_hello"/>,
+ The peer that initially creates and sends a DHT protocol message (<xref target="p2p_hello"/>,
<xref target="p2p_put"/>, <xref target="p2p_get"/>, <xref target="p2p_result"/>).
</dd>
<dt>HELLO block</dt>
@@ -230,14 +239,17 @@ gnunet+tcp://12.3.4.5/
</dd>
<dt>HELLO URL</dt>
<dd>
- <tt>HELLO</tt> URLs are URL-formatted <tt>HELLO</tt> blocks.
+ <tt>HELLO</tt> URLs are <tt>HELLO</tt> blocks in a URL representation.
They can used for out-of-band exchanges of peer information and are used for
- address update signalling messages to neighbours.
+ address update signalling messages to neighbours. Example HELLO URLs and their
+ format can be found in <xref target="hello_url"/>.
</dd>
<dt>Key</dt>
<dd>
512-bit identifier of a location in the DHT. Multiple <tt>Block</tt>s can be
stored under the same key. <tt>Peer Addresses</tt> are valid keys.
+ In the context of "key-value stores" this
+ refers to "key" under which values (blocks) are stored.
</dd>
<dt>Message Processing</dt>
<dd>
@@ -341,17 +353,11 @@ gnunet+tcp://12.3.4.5/
<t>
Specifics about the protocols of the underlays providing
connectivity or the applications using the DHT are out of
- the scope of this document. However, we note that peers
- implementing disjoint sets of underlay protocols may
- experience difficulties communicating (unless other peers
- bridge the respective underlays). Similarly, peers that
- do not support a particular application will not be able
- to validate application-specific payloads and may thus be
- tricked into storing or forwarding corrupt blocks.
+ the scope of this document.
</t>
<t>
In order to establish an initial connection to a network of R<sup>5</sup>N
- peers, an initial, addressable bootstrap peer is required.
+ peers, at least one initial, addressable peer is required as part of the bootstrapping process.
Further peers, including neighbors, are then learned via a peer discovery
process as defined in <xref target="find_peer"/>.
</t>
@@ -385,11 +391,11 @@ R5N | v v
| ^ ^
| v v
-------------+------------------------------------ Underlay Interface
- | +--------+ +--------+
- | |GNUnet | |IP | ...
-Connectivity | |Underlay| |Underlay|
- | |Link | |Link |
- | +--------+ +--------+
+ | +--------+ +--------+ +----------+
+ | |GNUnet | |IP | | QUIC |
+Connectivity | |Underlay| |Underlay| | Underlay | ...
+ | |Link | |Link | | Link |
+ | +--------+ +--------+ +----------+
]]>
</artwork>
</figure>
@@ -398,15 +404,15 @@ Connectivity | |Underlay| |Underlay|
<section anchor="underlay" numbered="true" toc="default">
<name>Underlay</name>
<t>
- In the network underlay, a peer is addressable by traditional
- means out of scope of this document. For example, the peer may
- have a TCP/IP address, or a HTTPS endpoint.
+ In the network underlay, how a peer is addressable is out of scope of this document.
+ For example, the peer may have a TCP/IP address, or expose a QUIC endpoint.
While the specific addressing options and mechanisms are out of scope
for this document, it is necessary to define a universal addressing
format in order to facilitate the distribution of connectivity
information to other peers in the DHT overlay.
This format is the "HELLO" Block (described in <xref target="hello_block"/>),
- which contains URIs. The scheme of each URI indicates which underlay understands the
+ which contains sets of URIs.
+ The scheme of each URI indicates which underlay understands the
respective address given in the rest of the URI.
</t>
<!--
@@ -438,12 +444,12 @@ Connectivity | |Underlay| |Underlay|
</t>
<dl>
<dt>
- <tt>TRY_CONNECT(N, A)</tt>
+ <tt>TRY_CONNECT(P, A)</tt>
</dt>
<dd>
- A function which allows the local peer to attempt the establishment of
- a connection to another peer <tt>N</tt> using an address <tt>A</tt>.
- When the connection attempt is successful, information on the new
+ A function which allows an implementation to signal to the underlay that
+ it wants to establish a connection to another peer <tt>P</tt> using an address <tt>A</tt>.
+ If the connection attempt is successful, information on the new
peer is offered through the <tt>PEER_CONNECTED</tt> signal.
</dd>
<dt>
@@ -478,7 +484,7 @@ Connectivity | |Underlay| |Underlay|
<tt>M</tt> to a peer <tt>P</tt>.
</dd>
<dt>
- <tt>L2NSE = ESTIMATE_NETWORK_SIZE()</tt>
+ <tt>ESTIMATE_NETWORK_SIZE() -> L2NSE</tt>
</dt>
<dd>
A procedure that provides an estimate of the network size.
@@ -529,7 +535,7 @@ Connectivity | |Underlay| |Underlay|
<tt>ADDRESS_DELETED -> A</tt>
</dt>
<dd>
- This underlay signals indicates that an address <tt>A</tt> was removed
+ This underlay signal indicates that an address <tt>A</tt> was removed
from the set of addresses the local peer is possibly reachable
under. Addresses must have been added before they may be deleted.
This information is used to no longer advertise
@@ -553,7 +559,7 @@ Connectivity | |Underlay| |Underlay|
<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 N, the peer selection for the
+ 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>
@@ -570,7 +576,7 @@ Connectivity | |Underlay| |Underlay|
<bcp14>MUST</bcp14> be removed from the routing table.
</t>
<t>
- In order to achieve O(log n) routing performance,
+ In order 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"/>.
@@ -591,7 +597,7 @@ Connectivity | |Underlay| |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^i and 2^(i+1) from the local peer.
+ 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.
System constraints will typically force an implementation to impose some
upper limit on the number of neighbors kept per k-bucket.
Upon insertion, the implementation <bcp14>MUST</bcp14> call
@@ -2514,6 +2520,18 @@ BEGIN
may achieve for a given network size and topology.
</t>
<section>
+ <name>Disjoint underlay protocols</name>
+ <t>
+ We note that peers
+ implementing disjoint sets of underlay protocols may
+ experience difficulties communicating (unless other peers
+ bridge the respective underlays). Similarly, peers that
+ do not support a particular application will not be able
+ to validate application-specific payloads and may thus be
+ tricked into storing or forwarding corrupt blocks.
+ </t>
+ </section>
+ <section>
<name>Approximate Result Filtering</name>
<t>
When a FindApproximate request is encountered, a peer will try to
