[lsd0004] branch master updated: various

[gnunet]

This is an automated email from the git hooks/post-receive script.

martin-schanzenbach pushed a commit to branch master
in repository lsd0004.

The following commit(s) were added to refs/heads/master by this push:
     new a231f20  various
a231f20 is described below

commit a231f2087141c0729dc66d3eb3c1267e13c12eac
Author: Martin Schanzenbach <schanzen@gnunet.org>
AuthorDate: Mon Jan 3 15:16:39 2022 +0100

    various
---
 draft-schanzen-r5n.xml | 163 ++++++++++++++++++++-----------------------------
 1 file changed, 65 insertions(+), 98 deletions(-)

diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
index 41428d0..b6ca63c 100644
--- a/draft-schanzen-r5n.xml
+++ b/draft-schanzen-r5n.xml
@@ -479,18 +479,12 @@ see how we can offer even the most minimal protections 
against node
      <section anchor="routing_table">
        <name>Routing Table</name>
        <t>
-         R5N stores the information of all connected nodes in a a set of lists
-         similar to the k-buckets data structure of <xref target="Kademlia"/>.
-         The size of this set is determined by the number of connected nodes.
-         A k-bucket contains a list of connected node IDs which share the same
-         bit prefix length with the local <tt>nodeID</tt>.
-         This number is called the <tt>index</tt> of the k-bucket.
-         The index which determines in which of the k-buckets to add a given
-         node is calculated using the <tt>FindBucket</tt> procedure.
-       </t>
-       <t>
-         In order to select nodes from the routing table which are suitable
-         destinations for sending messages, R5N uses a hybrid approach:
+         A R5N implementation must store the information on connected nodes.
+         The data structure for managing connected nodes and their
+         metadata may be implemented using the k-buckets concept of
+         <xref target="Kademlia"/>.
+         In order to select nodes which are suitable destinations for
+         routing messages, R5N uses a hybrid approach:
          Given an estimated network size N, the node selection for the
          first N hops is random. After the initial N hops, node selection
          follows an XOR-based node distance calculation.
@@ -505,78 +499,44 @@ see how we can offer even the most minimal protections 
against node
          case, any node which is in the bloomfilter for the respective message
          is not included in the node selection process.
        </t>
-       <!-- Fixme: We may want to propose our modified, optimized XOR metric 
here or reference Kademlia -->
        <t>
-         The buckets serve implicitly as a routing table for messages by
-         calculating the shortest distance from a message key to node ID.
-         In order to select a node for a given message key and bloomfilter,
-         the <tt>node-select</tt> is used (see <xref target="node-select"/>.
-       </t>
-       <figure anchor="node-select">
-         <artwork name="" type="" align="left" alt=""><![CDATA[
-node-SELECT(key, bloomfilter)
-  nodes := <Select all known peers NOT in message bloomfilter>
-  IF hops >= N
-    dist := MAX_VALUE
-    FOR EACH p IN nodes
-      IF XOR(p, key) < dist
-        dist := XOR(p, key)
-        target := p
-      END
-    END
-  ELSE
-    r := rand()
-    target := nodes[r]
-  END
-END
-         ]]></artwork>
-       </figure>
-       <t>
-         Apart from the k-bucket datastructure,
-         the R5N routing component MUST implement the following functions:
+         The R5N routing component MUST implement the following functions:
        </t>
        <dl>
-         <dt><tt>FindBucket(NodeID, Key) -> k-bucket as List</tt></dt>
-         <dd>
-           The <tt>FindBucket</tt> function determines how many low
-           order bits succesively match between a <tt>nodeID</tt> and a
-           <tt>Key</tt> starting from the first bit. The procedure returns
-             the k-bucket for this index.
-         </dd>
-         <dt><tt>GetDistance(NodeID_A, NodeID_B) -> Distance as 
Integer</tt></dt>
+         <dt><tt>GetDistance(A, B) -> Distance as Integer</tt></dt>
          <dd>
-           FIXME: We do NOT do XOR here. We do some kind of
-           fancy calculation. See get_distance()
+           this function calculates the binary XOR between A and B.
+           The resulting distance is interpreted as an integer where
+           the leftmost bit is the most significant bit.
          </dd>
-         <dt><tt>SelectClosestNode(Key) -> NodeID</tt></dt>
+         <dt><tt>SelectClosestNode(K, B) -> N</tt></dt>
          <dd>
-           This function determines the closest node ID to <tt>Key</tt>
-           of all connected nodes using <tt>GetDistance</tt>.
-           FIXME: Also has a bloomfilter. Isn't AmClosestNode simply
-           !SelectClosestnode == myID ?
+           This function selects the connected node <tt>N</tt> from our
+           routing table with the shortest XOR-distance to the key <tt>K</tt>.
+           This means that for all other nodes <tt>N'</tt> in the routing table
+           <tt>GetDistance(N, K) &lt; GetDistance(N',K)</tt>.
+           Nodes in the bloomfilter <tt>B</tt> are not considered.
          </dd>
-         <dt><tt>SelectRandomnode() -> NodeID</tt></dt>
+         <dt><tt>SelectRandomNode(B) -> N</tt></dt>
          <dd>
-           This function selects a random node ID from all connected
-           nodes. FIXME find elegant way to handle bloomfilter
+           This function selects a random node <tt>N</tt> from all connected
+           nodes.
+           Nodes in the bloomfilter <tt>B</tt> are not considered.
          </dd>
-         <dt><tt>Selectnode(Key, NumberOfHops)</tt></dt>
+         <dt><tt>SelectNode(K, H, B) -> N</tt></dt>
          <dd>
-           This function selects a node depending on the <tt>NumberOfHops</tt>
-           Parameter. If <tt>NumberOfHops &lt; NETWORK_SIZE_ESTIMATE</tt>
-           this function returns <tt>SelectRandomnode()</tt> and
-           <tt>SelectClosestnode(Key)</tt> otherwise.
+           This function selects a node <tt>N</tt> depending on the
+           number of hops <tt>H</tt> parameter.
+           If <tt>H &lt; NETWORK_SIZE_ESTIMATE</tt>
+           this function MUST return <tt>SelectRandomNode()</tt> and
+           <tt>SelectClosestnode(K)</tt> otherwise.
+           Nodes in the bloomfilter <tt>B</tt> are not considered.
          </dd>
-         <dt><tt>AmClosestNode(NodeID, Key, Bloom) -> true | false</tt></dt>
+         <dt><tt>IsClosestNode(N, K, B) -> true | false</tt></dt>
          <dd>
-           This function first determines which k-bucket contains the
-           closest node IDs to <tt>Key</tt>.
-           Any node IDs which match the bloom filter are not considered.
-           If there is a node ID <tt>NodeID'</tt> in the k-bucket where
-           <tt>GetDistance(NodeID, Key) > GetDistance(NodeID', Key)</tt>,
-           then <tt>false</tt> is returned, otherwise <tt>true</tt>.
-           FIXME: Currently, GDS_am_closest_node checks for longer matching
-           bits. Not GetDistance. Why?
+           checks if <tt>N</tt> is the closest node for <tt>K</tt>
+           (cf. <tt>SelectClosestNode(K)</tt>).
+           Nodes in the bloomfilter <tt>B</tt> are not considered.
          </dd>
        </dl>
      </section>
@@ -591,8 +551,8 @@ END
           node IDs along the route.
           A Bloom filter "bf" is initially empty, consisting only of zeroes.
           There are two functions which can be invoked on the Bloom filter:
-          BF-SET(bf, e) and BF-TEST(bf, e) where "e" is an element which is to 
added
-          to the Bloom filter or queried against the set.
+          BF-SET(bf, e) and BF-TEST(bf, e) where "e" is an element which is to
+          be added to the Bloom filter or queried against the set.
           Any bloom filter uses k=16 different hash functions each of which is
           defined as follows:
         </t>
@@ -685,7 +645,8 @@ END
        <dt>PATH_LEN</dt>
        <dd>
          is a 16-bit number indicating the length of the PUT path recorded
-         in PUTPATH. As PUTPATH is optiona, this value may be zero.
+         in PUTPATH.
+         As PUTPATH is optional, this value may be zero.
          In network byte order.
        </dd>
        <dt>EXPIRATION</dt>
@@ -696,7 +657,7 @@ END
        </dd>
        <dt>BLOOMFILTER</dt>
        <dd>
-         A bloomfilter (for node identities) to stop circular routes.
+         A bloomfilter (for node IDs) to stop circular routes.
        </dd>
        <dt>KEY</dt>
        <dd>
@@ -723,42 +684,46 @@ END
        </t>
        <ol>
          <li>
-           The EXPIRATION field is evaluated. If the message is expired,
-           it MUST be discarded.
+           The <tt>EXPIRATION</tt> field is evaluated.
+           If the message is expired, it MUST be discarded.
          </li>
          <li>
-           If the BTYPE is not supported by the implementation, no validation
-           of the block payload is performed and processing continues at (4).
+           If the <tt>BTYPE</tt> is not supported by the implementation,
+           no validation of the block payload is performed and processing
+           continues at (4).
            Else, the block MUST be validated as defined in (3).
          </li>
          <li>
            The block payload of the message is evaluated using according
-           to the BTYPE using the respective <tt>ValidateBlockStoreRequest</tt>
-           procedure.
+           to the <tt>BTYPE</tt> using the respective
+           <tt>ValidateBlockStoreRequest</tt> procedure.
            If the block payload is invalid or does not match the key,
            it MUST be discarded.
          </li>
          <li>
-           The sender node ID SHOULD be in the BLOOMFILTER. If not, the
-           implementation MAY log an error, but MUST continue.
+           The sender node ID SHOULD be in <tt>BLOOMFILTER</tt>.
+           If not, the implementation MAY log an error, but MUST continue.
          </li>
          <li>
-           If the <tt>RecordRoute</tt> flag is set in OPTIONS, the local node 
ID
-           MUST be appended to the <tt>PUTPATH</tt> of the message.
+           If the <tt>RecordRoute</tt> flag is set in OPTIONS,
+           the local node ID MUST be appended to the <tt>PUTPATH</tt>
+           of the message.
          </li>
          <li>
-           If the local node is the closest node (<tt>AM-CLOSEST-NODE</tt> is 
true) or the
-           <tt>DemultiplexEverywhere</tt> options flag ist set, the message 
MUST
+           If the local node is the closest node
+           (cf. <tt>IsClosestNode</tt>) or the <tt>DemultiplexEverywhere</tt>
+           options flag ist set, the message MUST
            be stored locally in the block storage.
          </li>
          <li>
-           Given the value in REPL_LVL, the number of nodes to forward to
-           MUST be calculated (NUM-FORWARD-nodeS). If there is at least one
+           Given the value in <tt>REPL_LVL</tt>, the number of nodes to
+           forward to MUST be calculated. If there is at least one
            node to forward to, the implementation SHOULD select up to this
            number of nodes to forward the message to. The implementation MAY
            forward to fewer or no nodes in order to handle resource constraints
            such as bandwidth.
-           The message BLOOMFILTER MUST be updated with the local node ID.
+           Finally, the local node ID MUST be added to the
+           <tt>BLOOMFILTER</tt> of the forwarded message.
          </li>
        </ol>
      </section>
@@ -797,8 +762,7 @@ END
            </dd>
            <dt>MTYPE</dt>
            <dd>
-             is the 16-bit message type. This type can be one of the DHT 
message
-             types but for put messages it must be set to
+             is the 16-bit message type. It must be set to
              the value 147 in network byte order.
            </dd>
            <dt>BTYPE</dt>
@@ -851,7 +815,7 @@ END
        <section anchor="p2p_get_processing">
          <name>Processing</name>
          <t>
-           Upon receiving a <tt>GetMmessage</tt> from a connected node an
+           Upon receiving a <tt>GetMmessage</tt> from a peer an
            implementation MUST process it step by step as follows:
          </t>
          <ol>
@@ -869,19 +833,22 @@ END
            </li>
            <li>
              <t>
-               If the local node is the closest node (AM-CLOSEST-NODE) or the
+               If the local node is the closest node
+               (cf. <tt>IsClosestNode</tt>) or the
                <tt>DemultiplexEverywhere</tt> options flag is set, a reply
                MUST be produced:
              </t>
              <ol>
                <li>
-                 If OPTIONS indicate a <tt>Findnode</tt> request, FIXME the 
node selection
+                 If <tt>OPTIONS</tt> indicate a <tt>FindNode</tt> request,
+                 FIXME the node selection
                  foo from buckets that probably needs fixing. Take into account
                  <tt>REPLY_BF</tt>
                </li>
                <li>
-                 Else, if there is a BLOCK in the local Block Storage which is
-                 not already in the RESULT_BF, a RESULT message MUST be sent.
+                 Else, if there is a block in the local Block Storage which is
+                 not already in the <tt>RESULT_BF</tt>,
+                 a ResultMessage MUST be sent.
                  FIXME link to how the result is sent?
                </li>
              </ol>

-- 
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.