lsd0004

commit 919274449c8c73970d3e5e3b54447d3061cbfd94
parent c244759655e2b9df21f0088852c9bbf02739a798
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date:   Wed, 29 Dec 2021 19:32:33 +0100

start routing

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

1 file changed, 28 insertions(+), 37 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -489,7 +489,7 @@ see how we can offer even the most minimal protections against peer
          R5N stores the information of all connected peers in a a set of lists
          similar to the k-buckets data structure of <xref target="Kademlia"/>.
          The index which determines in which of the k lists to add a given peer
-         is calculated using the FIND-BUCKET procedure (see <xref target="find-bucket"/>.
+         is calculated using the <tt>FindBucket</tt> procedure.
        </t>
        <t>
          The buckets serve implicitly as a routing table for messages:
@@ -515,42 +515,33 @@ PEER-SELECT(key, bloomfilter)
 END
          ]]></artwork>
      </figure>
-       <t>
-         The procedure to determine if we are the closest know peer for a given
-         message key and bloomfilter is defined as follows:
-       </t>
-       <figure anchor="find-bucket">
-         <artwork name="" type="" align="left" alt=""><![CDATA[
-FIND-BUCKET(peerID, key, kbuckets)
-  N := MATCHING-BITS (peerID, key)
-  return Nth bucket FROM kbuckets
-END
-          ]]></artwork>
-      </figure>
-      <t>The FIND-BUCKET Procedure.</t>
-      <figure>
-         <artwork name="" type="" align="left" alt=""><![CDATA[
-AM-CLOSEST-PEER(key, peerID, bloomfilter, buckets)
-  closestPeersBucket := FIND-BUCKET (myPeerID, key, buckets)
-  IF key == myPeerID
-    return TRUE
-  END
-  myDistance := XOR(peerID, key)
-  FOR EACH p IN closestPeersBucket
-    IF XOR(p, key) < myDistance
-      return FALSE
-    END
-    XOR(p, key) == myDistance
-      return TRUE
-    END
-  END
-  return TRUE
-END
-         ]]></artwork>
-     </figure>
-     <t>The AM-CLOSEST-PEER Procedure.</t>
-
-
+     <t>
+       R5N requires the following procedures for its routing table:
+     </t>
+     <dl>
+       <dt><tt>FindBucket(PeerID, Key) -> k-bucket</tt></dt>
+       <dd>
+           The <tt>FindBucket</tt> procedure determines how many low
+           order bits succesively match between a <tt>PeerID</tt> and a
+           <tt>Key</tt> starting from the first bit. The procedure returns
+           the k-bucket for this index. It contains all connected nodes which
+           share the same prefix length with <tt>PeerID</tt>.
+       </dd>
+       <dt><tt>GetDistance(NodeKey_A, NodeKey_B)</tt></dt>
+       <dd>
+         FIXME: We do NOT do XOR here. We do some kind of
+         fancy calculation. See get_distance()
+       </dd>
+       <dt><tt>AmClosestNode(NodeID, Key, Bloom) -> true | false</tt></dt>
+       <dd>
+         This procedure 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>.
+       </dd>
+     </dl>
      </section>
    </section>
    <section anchor="p2p_messages" numbered="true" toc="default">