lsd0004

commit 37a234461ba26956dce7641d4d931b525eaa912b
parent 9019e66771e402aa4d4e2dcf6ebaec31fdf46331
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date:   Mon, 15 Jul 2024 13:02:44 +0200

prob rounding

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

1 file changed, 16 insertions(+), 12 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -1081,7 +1081,7 @@ Connectivity | |Underlay|  |Underlay|  | Underlay | ...
           </dt>
           <dd>
 	    <t>
-            This function computes the number of neighbors
+      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
@@ -1094,8 +1094,7 @@ Connectivity | |Underlay|  |Underlay|  | Underlay | ...
 	    </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
+ComputeOutDegree(REPL_LVL, HOPCOUNT, L2NSE):
   if (HOPCOUNT > L2NSE * 4)
     return 0;
   if (HOPCOUNT > L2NSE * 2)
@@ -1104,19 +1103,24 @@ BEGIN
     REPL_LEVL = 1
   if (REPL_LEVEL > 16)
     REPL_LEVEL = 16
-  RM1 = REPL_LEVEL - 1
-  return 1 + (RM1 / (L2NSE + RM1 * HOPCOUNT))
+    RM1 = REPL_LEVEL - 1
+    FRAC = 1 + (RM1 / (L2NSE + RM1 * HOPCOUNT))
+  return PROUND(FRAC)
 ]]></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
+          The above calculation of <tt>FRAC</tt> may yield values that are
+          not discrete.
+          The result is <tt>FRAC</tt> rounded probabilistically
+          (<tt>PROUND</tt>) to the nearest
 	      discrete value, using the fraction
-	      as the probability for rounding up.
-              This probabilistic rounding is necessary to achieve
-              the statistically expected value of the replication
-              level and average number of peers a message is forwarded to.
+          as the probability for rounding up.
+          For example, a value of <tt>3.14</tt> is rounded up to <tt>4</tt> with
+          a probability of 14% and rounded down to <tt>3</tt> with a probability
+          of 86%.
+          This probabilistic rounding is necessary to achieve
+          the statistically expected value of the replication
+          level and average number of peers a message is forwarded to.
 	    </t>
 	  </dd>
         </dl>