[lsd0004] branch master updated: improve bloom, more bcp14

[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 f077893  improve bloom, more bcp14
f077893 is described below

commit f0778931876779e542970d5f2b5e288478280443
Author: Martin Schanzenbach <schanzen@gnunet.org>
AuthorDate: Sun Jul 14 10:15:09 2024 +0200

    improve bloom, more bcp14
---
 draft-schanzen-r5n.xml | 56 +++++++++++++++++++++++++++-----------------------
 1 file changed, 30 insertions(+), 26 deletions(-)

diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
index a806a42..2eeffef 100644
--- a/draft-schanzen-r5n.xml
+++ b/draft-schanzen-r5n.xml
@@ -859,7 +859,7 @@ Connectivity | |Underlay|  |Underlay|  | Underlay | ...
           Implementations <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.
+          if the respective <tt>k</tt>-bucket has empty slots.
         </t>
       </section>
       <section anchor="find_peer">
@@ -929,11 +929,12 @@ Connectivity | |Underlay|  |Underlay|  | Underlay | ...
           implementation, it is <bcp14>RECOMMENDED</bcp14> to choose external
           factors such as expiration of DHCP leases to determine the values.
           The specific frequency of advertisements
-          <bcp14>MAY</bcp14> depend on available bandwidth, the set of
-          already connected neighbors, the workload of the system and
-          other factors which are at the discretion of the developer,
-          but <bcp14>SHOULD</bcp14> be a fraction of the expiration
-          period.  Whenever a peer receives such a <tt>HELLO</tt>
+          <bcp14>SHOULD</bcp14> be a fraction of the expiration
+          period.
+          It <bcp14>MAY</bcp14> additionally depend on available bandwidth,
+          the set of already connected neighbors, the workload of the system 
and
+          other factors which are at the discretion of the developer.
+          Whenever a peer receives such a <tt>HELLO</tt>
           message from another peer that is already in the routing
           table, it must cache it as long as that peer remains in its
           routing table (or until the <tt>HELLO</tt> expires) and
@@ -954,9 +955,25 @@ Connectivity | |Underlay|  |Underlay|  | Underlay | ...
           filter is part of the routing metadata in messages to
           prevent circular routes. It is updated at each hop where the
           hop's peer identity derived from the peer's public key is
-          added to it.  It is constant in size at <tt>L=1024</tt> bits
-          (128 bytes) and sets <tt>k=16</tt> bits per element.  (At
-          this size, the Bloom filter reaches a false-positive rate of
+          added to it. 
+          The peer Bloom filter follows the definition in <xref 
target="bloom_filters"/>.
+          It <bcp14>MUST</bcp14> be <tt>L=1024</tt> bits
+          (128 bytes) in size and <bcp14>MUST</bcp14> set <tt>k=16</tt> bits 
per
+          element.
+          The set of elements <tt>E</tt> consists of of all possible 256-bit 
peer
+          public keys and the mapping function <tt>M</tt> is defined as 
follows:
+        </t>
+        <t>
+          <tt>M(e) -> SHA-512 (e) as uint32[]</tt>
+        </t>
+        <t>
+          The element <tt>e</tt> is the peer public key which is hashed using 
SHA-512.
+          The resulting 512-bit peer identity is interpreted as an array of 
k=16
+          32-bit integers in network byte order which are used to set and 
check the bits
+          in <tt>B</tt> using <tt>BF-SET()</tt> and <tt>BF-TEST()</tt>.
+        </t>
+        <t>
+          At this size, the Bloom filter reaches a false-positive rate of
           approximately fifty percent at about 200 entries. For peer
           discovery where the Bloom filter is initially populated with
           peer identities from the local routing table, the 200
@@ -964,32 +981,19 @@ Connectivity | |Underlay|  |Underlay|  | Underlay | ...
           peers per bucket, which corresponds to an overlay network
           size of approximately 1 trillion peers. Thus,
           <tt>L=1024</tt> bits should suffice for all conceivable
-          use-cases.) For the next hop selection in both the random
+          use-cases.
+        </t>
+        <t>
+          For the next hop selection in both the random
           and the deterministic case, any peer which is in the peer
           Bloom filter for the respective message is excluded from the
           peer selection process.
-        </t>
-        <t>
           Any peer which is forwarding <tt>GetMessages</tt> or 
<tt>PutMessages</tt>
           (<xref target="p2p_messages"/>) thus adds its own peer public key to 
the
           peer Bloom filter.
           This allows other peers to (probabilistically) exclude already
           traversed peers when searching for the next hops in the routing 
table.
         </t>
-        <t>
-          The peer Bloom filter follows the definition in <xref 
target="bloom_filters"/>.
-          The set of elements <tt>E</tt> consists of of all possible 256-bit 
peer public keys.
-          The mapping function <tt>M</tt> is defined as follows:
-        </t>
-        <t>
-          <tt>M(e) -> SHA-512 (e) as uint32[]</tt>
-        </t>
-        <t>
-          The element <tt>e</tt> is the peer public key which is hashed using 
SHA-512.
-          The resulting 512-bit peer identity is interpreted as an array of 
k=16
-          32-bit integers in network byte order which are used to set and 
check the bits
-          in <tt>B</tt> using <tt>BF-SET()</tt> and <tt>BF-TEST()</tt>.
-        </t>
         <t>
          We note that the peer Bloom filter may exclude peers due to 
false-postive
          matches.  This is acceptable as routing should nevertheless

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