commit 64b24d05f08e6bdd2aaa49aec54799b18ea21604
parent 2c58b5bddaa6ee4f18baf84c3962709d8bd40a11
Author: Christian Grothoff <christian@grothoff.org>
Date: Fri, 12 Jul 2024 09:58:53 +0200
justify 1024 bits
Diffstat:
1 file changed, 85 insertions(+), 55 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -866,70 +866,100 @@ Connectivity | |Underlay| |Underlay| | Underlay | ...
<section anchor="find_peer">
<name>Peer Discovery</name>
<t>
- Initially, implementations depend upon either the underlay providing at
- least one initial connection to a <em>neighbor</em> (signalled through
- <tt>PEER_CONNECTED</tt>), or the <em>application</em> or even end-user providing at
- least one working <tt>HELLO</tt> which is then in turn used to call <tt>TRY_CONNECT</tt>
- on the underlay in order to trigger a subsequent <tt>PEER_CONNECTED</tt> signal
- from the <em>underlay interface</em>.
- This is commonly achieved through the configuration of hardcoded bootstrap peers
- or bootstrap servers either for the underlay or the R<sup>5</sup>N implementation.
- While details on how the first connection is established <bcp14>MAY</bcp14>
- depend on the specific implementation, this <bcp14>SHOULD</bcp14> usually be done
- by an out-of-band exchange of the information from a <tt>HELLO</tt> block.
- <xref target="hello_url"/> specifies a URL format for encoding HELLO
- blocks as text strings. The URL format thus provides a portable, human-readable, text-based serialization
- format that can, for example, be encoded into a QR code for dissemination.
- HELLO URLs <bcp14>SHOULD</bcp14> be supported by implementations for both import and export
- of <tt>HELLO</tt>s.
+ Initially, implementations depend upon either the underlay
+ providing at least one initial connection to a
+ <em>neighbor</em> (signalled through
+ <tt>PEER_CONNECTED</tt>), or the <em>application</em> or
+ even end-user providing at least one working <tt>HELLO</tt>
+ which is then in turn used to call <tt>TRY_CONNECT</tt> on
+ the underlay in order to trigger a subsequent
+ <tt>PEER_CONNECTED</tt> signal from the <em>underlay
+ interface</em>. This is commonly achieved through the
+ configuration of hardcoded bootstrap peers or bootstrap
+ servers either for the underlay or the R<sup>5</sup>N
+ implementation. While details on how the first connection
+ is established <bcp14>MAY</bcp14> depend on the specific
+ implementation, this <bcp14>SHOULD</bcp14> usually be done
+ by an out-of-band exchange of the information from a
+ <tt>HELLO</tt> block. <xref target="hello_url"/> specifies
+ a URL format for encoding HELLO blocks as text strings. The
+ URL format thus provides a portable, human-readable,
+ text-based serialization format that can, for example, be
+ encoded into a QR code for dissemination. HELLO URLs
+ <bcp14>SHOULD</bcp14> be supported by implementations for
+ both import and export of <tt>HELLO</tt>s.
</t>
<t>
- To discover peers for its routing table, a peer will initiate <tt>GetMessage</tt> requests
- (see <xref target="p2p_get"/>) asking for blocks of type <tt>HELLO</tt> using its own peer identity
- in the <tt>QUERY_HASH</tt> field of the message.
- The <tt>PEER_BF</tt> is initialized and set using the peers own peer identity as well as the identities
- of all currently connected <em>neighbors</em>. <!-- note: we mean the identities here! FIX with terminology... -->
- These requests <bcp14>MUST</bcp14> use the <tt>FindApproximate</tt> and <tt>DemultiplexEverywhere</tt>
- flags. <tt>FindApproximate</tt> will ensure that other peers will reply
- with results where the keys are merely considered close-enough, while <tt>DemultiplexEverywhere</tt>
- will cause each peer on the path to respond. The combination of these flags is thus likely to yield
- <tt>HELLO</tt>s of peers that are useful somewhere in the routing table.
- The <tt>RECOMMENDED</tt> replication level to be set in the <tt>REPL_LVL</tt> field is 4.
- The size and format of the result filter is specified in <xref target="hello_block"/>.
- The <tt>XQUERY</tt> <bcp14>MUST</bcp14> be empty.
+ To discover additional peers for its routing table, a peer
+ <bcp14>MUST</bcp14> initiate <tt>GetMessage</tt> requests
+ (see <xref target="p2p_get"/>) asking for blocks of type
+ <tt>HELLO</tt> using its own peer identity in the
+ <tt>QUERY_HASH</tt> field of the message. The
+ <tt>PEER_BF</tt> <bcp14>MUST</bcp14> be initialized to
+ filter the peer's own peer identity as well as the peer
+ identities of all currently connected
+ <em>neighbors</em>. These requests <bcp14>MUST</bcp14> use
+ the <tt>FindApproximate</tt> and
+ <tt>DemultiplexEverywhere</tt>
+ flags. <tt>FindApproximate</tt> will ensure that other peers
+ will reply with results where the keys are merely considered
+ close-enough, while <tt>DemultiplexEverywhere</tt> will
+ cause each peer on the path to respond if it has relevant
+ information. The combination of these flags is thus likely
+ to yield <tt>HELLO</tt>s of peers that are useful somewhere
+ in the initiator's routing table. The <tt>RECOMMENDED</tt>
+ replication level to be set in the <tt>REPL_LVL</tt> field
+ is 4. The size and format of the result filter is specified
+ in <xref target="hello_block"/>. The <tt>XQUERY</tt>
+ <bcp14>MUST</bcp14> be empty.
</t>
<t>
- In order to facilitate the above,
- the underlay is expected to provide the implementation with one or more
- addresses signalled through <tt>ADDRESS_ADDED</tt>. Zero addresses <bcp14>MAY</bcp14> be
- provided if a peer can only establish outgoing connections and is otherwise unreachable.
- An implementation <bcp14>MUST</bcp14> advertise its addresses periodically to its
- <em>neighbors</em> through <tt>HelloMessage</tt>s.
- The advertisement interval and expiration should be configurable or chosen at the discretion
- of the implementation based on external factors such as expiration of DHCP leases.
- The specific frequency of advertisements <bcp14>MAY</bcp14> depend on available bandwidth,
- the set of already connected neighbors, the workload of the system and other factors which are at the discretion of
- the developer, but <bcp14>SHOULD</bcp14> be a fraction of the expiration period.
- Whenever a peer receives such a <tt>HELLO</tt> message from another peer that is
- already in the routing table, it must cache it as long as that peer remains in its routing table
- (or until the <tt>HELLO</tt> expires) and serve it in response to
- <tt>GET</tt> requests for <tt>HELLO</tt> blocks (see <xref target="p2p_get_processing"/>).
- This behaviour makes it unnecessary to initiate dedicated <tt>PutMessages</tt> containing
- <tt>HELLO</tt> blocks by the implementation.
+ In order to facilitate peers answering requests for
+ <tt>HELLO</tt>s, the underlay is expected to provide the
+ implementation with one or more addresses signalled through
+ <tt>ADDRESS_ADDED</tt>. Zero addresses <bcp14>MAY</bcp14> be
+ provided if a peer can only establish outgoing connections
+ and is otherwise unreachable. An implementation
+ <bcp14>MUST</bcp14> advertise its addresses periodically to
+ its <em>neighbors</em> through <tt>HelloMessage</tt>s. The
+ advertisement interval and expiration <bcp14>SHOULD</bcp14>
+ be configurable or chosen at the discretion of the
+ implementation based on external factors such as expiration
+ of DHCP leases. The specific frequency of advertisements
+ <bcp14>MAY</bcp14> depend on available bandwidth, the set of
+ already connected neighbors, the workload of the system and
+ other factors which are at the discretion of the developer,
+ but <bcp14>SHOULD</bcp14> be a fraction of the expiration
+ period. Whenever a peer receives such a <tt>HELLO</tt>
+ message from another peer that is already in the routing
+ table, it must cache it as long as that peer remains in its
+ routing table (or until the <tt>HELLO</tt> expires) and
+ serve it in response to <tt>GET</tt> requests for
+ <tt>HELLO</tt> blocks (see <xref
+ target="p2p_get_processing"/>). This behaviour makes it
+ unnecessary for peers to initiate dedicated
+ <tt>PutMessages</tt> containing <tt>HELLO</tt> blocks.
</t>
</section>
<section anchor="routing_bloomfilter">
<name>Peer Bloom Filter</name>
<t>
- As DHT <tt>GetMessage</tt>s and <tt>PutMessage</tt>s traverse a random path through the network for the
- first <tt>L2NSE</tt> hops, a key design objective of R<sup>5</sup>N is to avoid routing loops.
- The peer Bloom filter is part of the routing metadata in
- messages to prevent circular routes. It is updated at each hop where the hops
- peer public key is added to it.
- It is constant in size at <tt>L=1024</tt> bits (128 bytes) and
- sets <tt>k=16</tt> bits per element.
- For the next hop selection in both the random and the deterministic
- case, any peer which is in the peer Bloom filter for the respective message
+ As DHT <tt>GetMessage</tt>s and <tt>PutMessage</tt>s
+ traverse a random path through the network for the first
+ <tt>L2NSE</tt> hops, a key design objective of
+ R<sup>5</sup>N is to avoid routing loops. The peer Bloom
+ filter is part of the routing metadata in messages to
+ prevent circular routes. It is updated at each hop where the
+ hop's peer identity derived from the peer's public key is
+ added to it. It is constant in size at <tt>L=1024</tt> bits
+ (128 bytes) and sets <tt>k=16</tt> bits per element. (At
+ this size, the Bloom filter reaches a false-positive rate of
+ approximately fifty percent at about 200 entries; with 5
+ peers per bucket 200 entries would be enough for 40 buckets
+ which corresponds to an overlay network size of
+ approximately 1 trillion peers.) For the next hop selection
+ in both the random and the deterministic case, any peer
+ which is in the peer Bloom filter for the respective message
is excluded from the peer selection process.
</t>
<t>
