commit 5814d45f30017bde86f3750f30a57ec395c98b66
parent 7be344025a81e38dc3316489db4c8669bcfb4dc4
Author: Christian Grothoff <christian@grothoff.org>
Date: Thu, 11 Jul 2024 23:26:26 +0200
explain local minima issue better
Diffstat:
1 file changed, 27 insertions(+), 16 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -152,11 +152,11 @@
DHT designs often assume that the IP protocol provides the
peers of the overlay with unrestricted end-to-end pairwise
connectivity. However, in practice firewalls and network
- address translation (<xref target="RFC2663"/>) make it
+ address translation (NAT) <xref target="RFC2663"/> make it
difficult for peers operating on consumer end-devices to
directly communicate, especially in the absence of core
network infrastructure enabling NAT traversal via protocols
- such as ICE (<xref target="RFC5245"/>).
+ such as interactive connectivity establishment (ICE) <xref target="RFC5245"/>.
</t>
<t>
Furthermore, not all peer-to-peer networks consistently
@@ -350,22 +350,33 @@
<section numbered="true" toc="default">
<name>Restricted-route topologies</name>
<t>
- Restricted-route topologies emerge when a connected underlay topology prevents
- (or restricts) direct connections between some of the nodes.
- This commonly occurs through the use of NAT.
- Nodes operated behind a NAT cause common DHT routing algorithms such
- as Kademlia to exhibit degraded performance or even to fail.
- While excluding such nodes is an option, this limits load distribution
- and is ineffective for some physical networks.
+ Restricted-route topologies emerge when a connected underlay
+ topology prevents (or restricts) direct connections between
+ some of the nodes. This commonly occurs through the use of
+ NAT (<xref target="RFC2663"/>). Nodes operated behind a NAT
+ cause common DHT routing algorithms such as Kademlia <xref
+ target="Kademlia"/> to exhibit degraded performance or even
+ to fail. While excluding such nodes is an option, this
+ limits load distribution and is ineffective for some
+ networks, such as MANETs.
</t>
<t>
- Nodes which in terms of a classical distance metric such as XOR
- would be considered close may not be reachable, for example due to a firewall
- or NAT.
- This leads to multiple (local) minima with respect to where data may be
- stored or where data can be retrieved.
- From a particular fixed location in the network, a node may only be able to
- find and and store data in the context of its local minimum.
+ In general, nodes may not be mutually reachable (for example
+ due to a firewall or NAT) despite being "neighbours"
+ according to the routing table construction algorithm of a
+ particular DHT. For example, Kademlia uses the XOR metric
+ and would generally connect nodes that have peer identities
+ with a small XOR distance. However, the XOR distance between
+ (basically randomly assigned) peer identities is completely
+ divorced from the ability of the nodes to directly
+ communicate. DHTs usually use greedy routing to store data
+ at the peer(s) closest to the key. In cases where a DHT
+ cannot connect peers according to the construction rules of
+ its routing algorithm, the topology may ends up with
+ multiple (local) minima for a given key. Using canonical
+ greedy routing from a particular fixed location in the
+ network, a node may then only be able to publish and
+ retrieve data in the proximity of its local minima.
</t>
<t>
R<sup>5</sup>N addresses this problem by prepending a random walk before a
