lsd0004

commit 28cea67fa6089ec0b9ba33d7aeef57664516eba9
parent fec15549407552db80575ae1f8b199da8f7e08ea
Author: Christian Grothoff <grothoff@gnunet.org>
Date:   Mon, 14 Mar 2022 01:51:57 +0100

add ComputeOutDegee() function to spec

Diffstat:
M
draft-schanzen-r5n.xml
 | 
38
+++++++++++++++++++++++++++++++++++---

1 file changed, 35 insertions(+), 3 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -948,6 +948,7 @@ bchar = *(ALPHA / DIGIT)
             <tt>ComputeOutDegree(REPL_LVL, HOPCOUNT, L2NSE) -&gt; Number</tt>
           </dt>
           <dd>
+	    <t>
             This function computes the number of neighbors
 	    that a message should be forwarded to.  The arguments
 	    are the desired replication level (<tt>REPL_LVL</tt>), the <tt>HOPCOUNT</tt> of the message so far, and
@@ -955,9 +956,34 @@ bchar = *(ALPHA / DIGIT)
 	    size estimate (<tt>L2NSE</tt>) as provided
 	    by the underlay.  The result
 	    is the non-negative number of next hops to
-	    select.
-	    <!-- FIXME: specify full function! -->
-          </dd>
+	    select.  The following figure gives the
+	    pseudocode for computing the number of neighbors
+	    the peer should attempt to forward the message to.
+	    </t>
+            <figure anchor="compute_out_degree" title="Computing the number of next hops.">
+              <artwork name="" type="" align="left" alt=""><![CDATA[
+function ComputeOutDegree(REPL_LVL, HOPCOUNT, L2NSE)
+BEGIN
+  if (HOPCOUNT > L2NSE * 4)
+    return 0;
+  if (HOPCOUNT > L2NSE * 2)
+    return 1;
+  if (0 = REPL_LEVL)
+    REPL_LEVL = 1
+  if (REPL_LEVEL > 16)
+    REPL_LEVEL = 16
+  RM1 = REPL_LEVEL - 1
+  return 1 + (RM1 / (L2NSE + RM1 * HOPCOUNT))  
+]]></artwork>
+            </figure>
+  	    <t>
+	      The above calculation may yield values that are
+	      not discrete. Hence, the result <bcp14>MUST</bcp14> be
+	      rounded probabilistically to the nearest
+	      discrete value, using the fraction
+	      as the probability for rounding up.
+	    </t>
+	  </dd>
         </dl>
       </section>
       <section anchor="pending_table">
@@ -2298,6 +2324,12 @@ gnunet+tcp://12.3.4.5/ \
         as an adversary would have to invest more resources over time
         to mount an effective attack.
       </t>
+      <t>
+	The <tt>ComputeOutDegree</tt> function limits the
+	<tt>REPL_LVL</tt> to a maximum of 16. This imposes
+	an upper limit on bandwidth amplification an attacker
+	may achieve for a given network size and topology.  
+      </t>
     </section>
     <section anchor="iana" numbered="true" toc="default">
       <name>IANA Considerations</name>