add ComputeOutDegee() function to spec

1 files changed, 35 insertions, 3 deletions

diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
index cc59f22..d273b49 100644
--- 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>