commit 00a6cf89ee9b162389e8e09e65f2443cdcb30f15
parent 25550ba0ab49062169204d0377bd6d9d5335bc7f
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Sun, 29 Oct 2023 22:32:43 +0900
update
Diffstat:
1 file changed, 20 insertions(+), 14 deletions(-)
diff --git a/IETF118/r5n.tex b/IETF118/r5n.tex
@@ -8,8 +8,8 @@
\usepackage{blkarray}
\usepackage{amsmath}
\usepackage{multirow}
-\title{The R5N Distributed Hash Table --- \url{https://datatracker.ietf.org/doc/draft-schanzen-r5n/}\\\small{IETF118}}
-\date{XX/11/2023}
+\title{The R5N Distributed Hash Table\\\small{IETF118}}
+\date{06/11/2023}
\author{\textbf{Martin Schanzenbach}, Christian Grothoff, Bernd Fix}
\institute{\hfill\large{GNUnet} \includegraphics[trim={0cm 1.5cm 0cm 0cm},clip,width=4em]{gnunet}}
\begin{document}
@@ -21,7 +21,7 @@
\begin{frame}{The R5N DHT I-D}
\url{https://datatracker.ietf.org/doc/draft-schanzen-r5n/}\\R5N is a DHT with the following distinguishing properties:
\begin{itemize}
- \item \textbf{Open access}.
+ \item \textbf{Open participation peer-to-peer routing}.
\item Works in \textbf{restricted-route environments}.
\item Supports \textbf{route path recording}.
\item In-band \textbf{request (and response) validation}.
@@ -29,7 +29,7 @@
\end{itemize}
\end{frame}
-\begin{frame}{Open, peer-to-peer routing}
+\begin{frame}{Open participation peer-to-peer routing}
\begin{itemize}
\item Access control requires authentication (and trust) and leads to centralization.
\item RELOAD (RFC 6940): ``RELOAD's security model is based on each node having one or more
@@ -42,25 +42,31 @@
\begin{frame}{Support for restricted-route environments}
- From ``R5N : Randomized Recursive Routing for
+ From ``$R^5N$ : Randomized Recursive Routing for
Restricted-Route Networks'' by Evans et al.:
\begin{itemize}
- \item ``Restricted-route topology'' refers to a connected underlay topology which prohibits (restricts) direct
-connections between some of the nodes.
+ \item ``Restricted-route topology'' refers to a connected underlay topology which does not support direct
+ connections between some of the nodes (e.g. wireless mesh networks, NAT or firewalls).
\item Common DHT routing algorithms (e.g. Kademlia) show diminished performance or even arrant failure when operating over a restricted-route underlay.
- \item A common solution is to restrict participation in the DHT to peers that are not encumbered by NAT or firewalls.
- \item However, this solution limits load-distribution for P2P applications and does not work at all for
- physical networks or friend-to-friend networks.
- \item For these types of networks, some other method of routing must be employed to cope with restrictions on direct communication.
+ \item A common solution is to prevent participation in the DHT to peers that are not encumbered by such restrictions.
+ \item However, on the modern Internet the proportion of hosts with unrestricted communication capabilities is limited (e.g. CG NAT).
\end{itemize}
\end{frame}
\begin{frame}{Support for restricted-route environments}
+ So, what are the implications if we have to deal with restricted routes?
\begin{itemize}
+ \item Problem:
+ \begin{itemize}
\item Some peers, which from the distance metric (XOR) may be close, may not be reachable (e.g. firewall).
\item This leads to multiple (local) minima with respect to where data may be stored/can be retrieved.
- \item Solution: Randomized routing before XOR-metric-based routing. "Escape" local minimum sink.
- \item When we have a small world topology, such a random walk will cause us to land in a random spot in the network and we will find a random local minimum.
+ \end{itemize}
+ \item Solution:
+ \begin{itemize}
+ \item Random walk before greedy decent to ``escape'' local minima.
+ \item Assuming we have a small world topology, the random walk will cause us to land at a random peer in the network from where the greedy descent will find a random local minimum.
+ \item Replication at multiple local minima combined with the birthday paradox provides reasonable availability.
+ \end{itemize}
\end{itemize}
\end{frame}
@@ -110,7 +116,7 @@ connections between some of the nodes.
\begin{frame}{In-band response validation}
- DHT values can be corrupted or invalid. R5N addresses this with pluggable, extensible block types:
+ DHT values can be corrupted or invalid. $R^5N$ addresses this with pluggable, extensible block types:
\begin{itemize}
\item Given a key and a block type, it is possible to verify the integrity of the value.
\item The verification should be possible for all hops on path, improving caching performance.
