[lsd0004] branch master updated (3e58a5b -> a139d3c)

[gnunet]

This is an automated email from the git hooks/post-receive script.

martin-schanzenbach pushed a change to branch master
in repository lsd0004.

    from 3e58a5b  more routing
     new b3a4e43  routing
     new a139d3c  hello wire format

The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.


Summary of changes:
 draft-schanzen-r5n.xml | 108 +++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 91 insertions(+), 17 deletions(-)

diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
index 519fb60..7b60cb6 100644
--- a/draft-schanzen-r5n.xml
+++ b/draft-schanzen-r5n.xml
@@ -361,7 +361,45 @@ peer-public-key := [A-HJ-NP-Z1-9]+
        The following is a non-normative example of a HELLO containing three
        HELLO URIs:
      </t>
-     <!-- FIXME peer id type | length | id payload | 0-terminated strings for 
addresses -->
+     <figure anchor="figure_hello">
+       <artwork name="" type="" align="left" alt=""><![CDATA[
+0     8     16    24    32    40    48    56
++-----+-----+-----+-----+-----+-----+-----+-----+
+|   TYPE    |   SIZE    |         NODEID        /
++-----+-----+-----+-----+   (variable length)   /
+/                                               /
++-----+-----+-----+-----+-----+-----+-----+-----+
+|                   ADDRESSES                   /
+/               (variable length)               |
++-----+-----+-----+-----+-----+-----+-----+-----+
+         ]]></artwork>
+     </figure>
+     <dl>
+       <dt>TYPE</dt>
+       <dd>
+         is the type of HELLO. A 16-bit number in network byte order.
+         This value determines the type of the NODEID field.
+       </dd>
+       <dt>SIZE</dt>
+       <dd>
+         is the SIZE of the following fields NODEID and ADDRESSES in bytes.
+         In network byte order.
+       </dd>
+       <dt>NODEID</dt>
+       <dd>
+         is the Node ID of the peer which has generated this HELLO.
+         The length content of the NODEID is determined by the TYPE field.
+         Usually, this is a cryptographic public key which allows the
+         Underlay to uniquely identify and authenticate the node.
+       </dd>
+       <dt>ADDRESSES</dt>
+       <dd>
+         is a list of strings which can be used as addresses to contact the
+         node. The strings MUST be 0-terminated.
+         FIXME: Examples? Format determined?
+       </dd>
+     </dl>
+     <!-- FIXME peer id type | length | id payload | 0-terminated strings for 
addresses
        <figure>
          <artwork name="" type="" align="left" alt=""><![CDATA[
 Y924NSHMMZ1N1SQCE5TXF93ED6S6JY311K0QT86G9WJC68F6XVZ0 \
@@ -371,7 +409,7 @@ Y924NSHMMZ1N1SQCE5TXF93ED6S6JY311K0QT86G9WJC68F6XVZ0 \
         tor+onionv3://rasdflkjasdfliasduf.onion/
          ]]></artwork>
      </figure>
-
+     -->
 
      <!--
        1) The current API is always fire+forget, it doesn't allow for flow
@@ -465,8 +503,37 @@ see how we can offer even the most minimal protections 
against peer
 
    <section anchor="routing" numbered="true" toc="default">
      <name>Routing</name>
-     <section anchor="peer_selection" numbered="true" toc="default">
-       <name>Peer selection</name>
+     <section>
+       <name>Distance Metric</name>
+       <t>
+         The distance between two keys <tt>KeyA</tt> and <tt>KeyB</tt> is
+         calculated relative to their shared prefix.
+         The prefix length is determined by the number of low order bits
+         that succesively match between <tt>KeyA</tt> and <tt>KeyB</tt>
+         starting from the first bit.
+       </t>
+       <t>
+         Relative to the (identical) bits in the shared prefix, differences
+         in the lower bits must count stronger than higher bits.
+         The resulting distance value is a FIXME: I think we wanted to
+         move to a 512-bit distance value. And I think we may have decided
+         to use a "regular" xor.
+       </t>
+     </section>
+
+
+     <section anchor="routing_table">
+       <name>Routing Table</name>
+       <t>
+         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 size of this set is determined by the number of connected peers.
+         A k-bucket contains a list of connected node IDs which share the same
+         bit prefix length with the local <tt>PeerID</tt>.
+         This number is called the <tt>index</tt> of the k-bucket.
+         The index which determines in which of the k-buckets to add a given
+         peer is calculated using the <tt>FindBucket</tt> procedure.
+       </t>
        <t>
          In order to select peers from the routing table which are suitable
          destinations for sending messages, R5N uses a hybrid approach:
@@ -486,13 +553,8 @@ see how we can offer even the most minimal protections 
against peer
        </t>
        <!-- Fixme: We may want to propose our modified, optimized XOR metric 
here or reference Kademlia -->
        <t>
-         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 <tt>FindBucket</tt> procedure.
-       </t>
-       <t>
-         The buckets serve implicitly as a routing table for messages:
+         The buckets serve implicitly as a routing table for messages by
+         calculating the shortest distance from a message key to node ID.
          In order to select a peer for a given message key and bloomfilter,
          the <tt>PEER-SELECT</tt> is used (see <xref target="peer-select"/>.
        </t>
@@ -516,16 +578,16 @@ END
          ]]></artwork>
        </figure>
        <t>
-         R5N requires the following procedures for its routing table:
+         Apart from the k-bucket datastructure,
+         the R5N routing component MUST implement the following functions:
        </t>
        <dl>
          <dt><tt>FindBucket(PeerID, Key) -> k-bucket as List</tt></dt>
          <dd>
-           The <tt>FindBucket</tt> procedure determines how many low
+           The <tt>FindBucket</tt> function 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>.
+             the k-bucket for this index.
          </dd>
          <dt><tt>GetDistance(NodeKey_A, NodeKey_B) -> Distance as 
Integer</tt></dt>
          <dd>
@@ -534,14 +596,26 @@ END
          </dd>
          <dt><tt>SelectClosestPeer(Key) -> NodeID</tt></dt>
          <dd>
-           This procedure determines the closest node ID to <tt>Key</tt>
+           This function determines the closest node ID to <tt>Key</tt>
            of all connected nodes using <tt>GetDistance</tt>.
            FIXME: Also has a bloomfilter. Isn't AmClosestNode simply
            !SelectClosestPeer == myID ?
          </dd>
+         <dt><tt>SelectRandomPeer() -> NodeID</tt></dt>
+         <dd>
+           This function selects a random node ID from all connected
+           nodes. FIXME find elegant way to handle bloomfilter
+         </dd>
+         <dt><tt>SelectPeer(Key, NumberOfHops)</tt></dt>
+         <dd>
+           This function selects a peer depending on the <tt>NumberOfHops</tt>
+           Parameter. If <tt>NumberOfHops &lt; NETWORK_SIZE_ESTIMATE</tt>
+           this function returns <tt>SelectRandomPeer()</tt> and
+           <tt>SelectClosestPeer(Key)</tt> otherwise.
+         </dd>
          <dt><tt>AmClosestNode(NodeID, Key, Bloom) -> true | false</tt></dt>
          <dd>
-           This procedure first determines which k-bucket contains the
+           This function 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

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