commit a0a342721153f57ce2c1a7000d7c956beadb86a7
parent 00a6cf89ee9b162389e8e09e65f2443cdcb30f15
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Mon, 30 Oct 2023 00:10:23 +0900
changes
Diffstat:
4 files changed, 41 insertions(+), 29 deletions(-)
diff --git a/IETF118/R5NRoutExample.drawio b/IETF118/R5NRoutExample.drawio
@@ -1 +1 @@
-<mxfile host="Electron" modified="2023-10-28T14:32:03.568Z" agent="5.0 (Macintosh; Intel Mac OS X 13_2_1) AppleWebKit/537.36 (KHTML, like Gecko) draw.io/14.6.13 Chrome/89.0.4389.128 Electron/12.0.7 Safari/537.36" etag="QwHVmxX8AlCfQby0nb5K" version="14.6.13" type="device"><diagram id="tL_J0fyiPHFeeB-L7Xh7" name="Page-1">7V1bl6I4EP41/dgekkAIj9OX6T5nLttnZnZn52kPSlS20biI3fb++g03IRcRUUB77RclQAj1famqVKrsK3Q7Wz+E7mL6hXk0uIKGt75Cd1cQAsu2+Ufc8pa2OI6RNkxC38suKhq++//SrDG/bOV7dClcGDEWRP5CbByx+ZyOIqHNDUP2Kl42ZoH41IU7oUrD95EbqK0/fS+aZq3YMosTj9SfTPNHA+ykZ2ZufnX2Ksup67HXUhO6v0K3IWNR+m22vqVBLL1cMOl9H7eczUa2jN7yseYjCuk8qtPD3f1k+uPB/kk+GejrL/LH4+iv62sAlX5Dtpp7NL7JuEI3LIymbMLmbvCZsQVvBLzxbxpFbxl67ipivGkazYLsLF370Z+l77+yruLvd+vywVt+MI/Ct/gWY2Dlh7/yHuKD4rbkKL9vGblh9CHGnTeMAne59Ed580c/yAekSiqXJluFI1olnoyDbjihUcV1OL2OegK9MhweKJtRPmx+QUgDN/JfRLa5GWknm+sKFPmXDMh9QCUKqPHIvmeHczbnHzft4JwCWAPps8QZnhbOab8vbrDKnmTwPxX7IOD6M4b8depH9PvCTWTxylW4CKi7XKRKdeyvY2LcjLlsb1nAwqQjhE0bEzsRfMieaekMAibiOpLfweZRqX2c/FVB80LDiK4rhZmdtXLNmtkWMz9+LTQ1yZqmJR2dtx1d/FAVPwCqnn4n4iemKH6IexY/cM5My5WMW196Dp+nnsP9IV3XbzEwErEmu8BOjp5o6HMh0VDHgOzFyvAbB8Fv1oQfnBT8pqJnwTs2cwiLetay+taz9kXP7jvRrLNcN1g6f/LdOjSISA5N3/4kVvUcaFP8nkvJeKQTPx4ROjySmLEhidno223XmI7T1md9a7M8OrdTnTknpc7guYVBTsBwkZpImyeFNNFpznfrIQJpJW6hnjWqo/oNrRqufsVvIlH8ttm3g252queMsp6r1HKnY5jISamrfNjiivbsPT0oBWgx6XtiqAFyVcZzT2VomfWNNiz2DyXVCfzwsXZq5K2as6aEr6XBN2+rPbmyJzwxn79ZEf+XzJ4p8yZ97+yugjpqR47UEZI6SgWjdJRwcPPaB/ilqr28gjiIMrN1FW9v5xMU/7OKN4w52Mgw0t2doglP4s9vbBXRRLx8dvujyGfzvDs+vLTH9EqF/PHc9kfcBrhDGjyxpZ/cjO6GLIrYjN+RX/Ah8CfxiYhJmmc5dRdxZ7P1JM4IGAxdPoMGYz6TponNidysy2vTUvUStbgvY+j00k26ldWuIcfOwCISFeyBgRStBTWsBpY5cA5XXGj2+NsznUytx/HUnUwAWLz+2CxRBYf2pLeWFKlrsNkKhG3a+gnZgeHQy18j6pPYcKjpUTUzWlptXwvHAzU7JGQAiQltAE3bxJyOoh/hgIENLBsS2+KLHRs3U/vILncDHYjEp4DyIGzDassm6BmHOmVcEZ9ogXMDjKEY1nBsZ5fDpNsM642QHP6BUfqDAlM2C759GWgCOHBwqVuJ55AMEHCKv04ZiLplYFnngfZ03u6QWl2SNcsiqjDvx2ctqWSt1ZC1trSs2+ThdEXMbsMbLRrj/ZIbmxGz0p+sl/dxdGJajmjfgejtyWdRQ55akhcpu4ct89SEitN+WdY1W9YdtJqARFnWIc2CosU1nXZqITWN5c6NXN7y9PsP9R0b5HIjdRtEImDBkZxt8YnrZaITP/ALoLlYq1QsWpKhYncW02U+XC6Sk9kDoRFr4JB/PtO3tDsDAJHZyWCGYanjWoTmZIgkggrMymxAmYZZk5sxfMQFG/uVCvVnvucF21bQolFRQaoGuv6GjpTyQ7R01fBVDlwdbQGM1FSQY1Pp4f5/T6Udaq6CXduTpCUqAc3mVGtU0g9YpdKdz32k+Yguj6P2doZTG3LVS0+mkbf3wLfd5LK2ELO26rI1ez7d8s1UY6dHpUOaEncBPwZb2kiBGrsFHA348gryeODrdvyOCj64gC8tr/KZb/cO/s4F2IGGwEhckAv4EEoT39LkdHaMPWrdCbhgn1tuCXzQIfj6yEvLHqABzlPrN1pfWNXgS8HgDdC9gW+17e+d6cxvAXzTEsFHGme/Y/Db9vcu4G+cfVnta8plurX5SC2Y+eLP/ZmrvnCDsIKpxms/M44Jb5rFT1nNFAbkUXN+VcBW0Ra8SgRZlDa8s5tKe+ByWH1suMhwFV7FYfU7WxtWz/YW6jsDeAt9tsebgMgKrFsF6ELtrSV9mmq86YKbWs0vJbHr4oTd4oZsBbdPrkdngZ/skcQ/r7NlWhsv/tIf5mBWT3W9FdEYkS0UGQd0nW353jRLHd5VzSWnbluUeKaOPAQOEcYbklRuFFdKvF5ZV19pv/Jyw5btSe38L2uLqupofxirBqVNmu1MfOmaaH0RCMt1vk0TYQhyBkVyFrHFdIMNTzvKIjdVffnNnXtsxj1brzVVqdtiPgKHZYtJRnSkrVcZEitehTSpRmrK3lzQNauReiuPkIPxTbMUgdQRbo/YWorpgjm9Umyfwt7WSUZ65Zi024eaqlLlR06cbjmmqcBrg2Q1bGqRkY0JEoiWJU1vryHnBw0ypg+j35bsg27oRyRXUCncqp2IbUs+pczjtumnhq3KtjvP3NUY6z2iGvonqzGTnrRrDapWyK4vCppS/HujEfcuQpQW4GbXGlB1Hy9E2KdmSfaSZPzqlyVJHXWcXg9acumb1aA1N6BH9tIq9fZxf0+2N29OWhgrhR21dZkhFJ5gsaypxYWxvthBJbRgXNFRDKm2iPv9rIQrJXviK2HOOLEOSiz0tJr+bgCU3E8MuiV27jGcDuXq10q1Trle18UIVFbeNV2mIDmk07GPiGAnhGvJyLdYEHoYVff6cdDeKC0rUZHSjWPocgSpY29Xs6t/ofQOSve4cVOiIEAiBRvHt3vbxtHvPat+5AONR/u2f3mMftuxhtfQVsEov+dZMznq/hrZjiymCnluzXtwpLAL1OSrEEulNJBpcbQUNqzGAlMCfGXZieNHAXENw94WJ9YHBImaEALvyGSHuwkBdAVMLTJCl8veWkSmp0SBvbC6JApo6cQPi/8nll5e/Fs2dP8f</diagram></mxfile>
-\ No newline at end of file
+<mxfile host="Electron" modified="2023-10-29T14:26:52.389Z" agent="5.0 (Macintosh; Intel Mac OS X 13_2_1) AppleWebKit/537.36 (KHTML, like Gecko) draw.io/14.6.13 Chrome/89.0.4389.128 Electron/12.0.7 Safari/537.36" etag="CtW8lDny125xKnP8W0Up" version="14.6.13" type="device"><diagram id="tL_J0fyiPHFeeB-L7Xh7" name="Page-1">7V1bk9o4Fv41vExVKEuyJfkxnZ5JqiaZTU2yOztPUwYb8LbBjHGn6f31I4MN1sXGGEuiu+mXBvnKOZ/OXToj9GG5/ZgF68WXNIySEXTC7QjdjyAEACD2rxh53o9g398PzLM4LE86DnyL/x+Vg045+hiH0YY7MU/TJI/X/OA0Xa2iac6NBVmWPvGnzdKEf+o6mEfSwLdpkMijf8RhvihHseceD3yK4vmiejTA5Q9cBtXZ5U/ZLIIwfaoNoZ9H6EOWpvn+03L7IUoK6lWE2V/3S8PR8s02+XP1rtUbZdEq5578I97Ek+qs9rve/zxffP9I/qC/Oui3P+l/Pk3/evcOQOlZWfq4CqPiImeE7tIsX6TzdBUkn9N0zQYBG/xflOfPJUeDxzxlQ4t8mZRHo22c/7e8vPj8Z+3z/bb+5bn6ssqz590lYwJINbC7buwjWg0cL959q67e5EGWvy8QwQamSbDZxNNq+Jc4ObxWcdHXKIuXUR5l5bUyYSvip4/ZNGqjXAnZIJtHect53v68KOTQWLLoY5Syt8me2QlZlAR5/IMHZ1BifH4478hg9qHk8Tn8phK/izf7Vn5dpSv2724wCIA6BMZeRxDUAQCGYb5+PsPr4nMpHoLksRIO7E/mfZIwcVuw/GkR59G3dbCjxROT+DxDg816L4Nn8bYAxt2M0fZDmqTZ7kYIuwRTsiN8lj5EtSMIuIiJVHZFuspr47PdXxtrfkRZHm1biVke9SpxWKoit/r+dBTstBxa1ER6NTY4+aFMfqYwXyv5qcuTH2LL5Af+C5Ny5VU25Rx+kXLOU8m5VzvREBUmmm05hyXyA6CT/GEQ0dlURX48pdFkIDJjRyCzY1udWLTaXqLNRjvKMnxVsoyqJtOrtdmAYDR4yPIk8xU22+tVJS7iyU9c2zaba1TGdQ9O6PcwnY7iil6VuKpeuy6vtNpeZpQ/FHxJTM1NDLT89K+HaL7wPs0WwXwOwPrp+zuooPN1O5MSsRUsaaQ/cYk1vaCkP0LWjC8whGDq63Eqhc1gMbQWqF8g0MpLv6Yxe8WjrqPO2Kn9QV7zeQJy9j+nvEc9oC7clgiS4hCFqm60/73SjXYoPPy6C4BpRmOeCzMwOsMVOF8d94Nlq2TtFsMfHJaECPhxYU8gerzIdEVZqBmIGEtAHM5OG2Pi1cExdhiZOiaTvHOg2BXn7FnqLNIgotLvCMlLTT81kjwXjAnwCKTEY5qX+DyuhKOU9MOr65Ixwkd5DLinIMcbO8g//mGzYCZm1f3YgT6Hb+zirvh2IIdwdi3VmSzVDH1F1MaklQAFj9gTpWhXeGNYnybERdxtIaFjSF1IAHSJy457ZuFtNpR4TIcM5mj3izkOac3aNRtggxSuzFlHKcLPBTGiLndbJlnGCNSkslnUWkzodRTGGkyNoc2KwaGIAS8yXdJTZFLcZncgVBeZTLwio+Ajihj8VYDvSgSmNYXtc7CoStnUcpDSnsoctdmq0AfM5qqFFszaqkQRBXxZyryfiDOJMuS0ogwMgzLMC1IoClLdQDIU41SHIodzzM8LoA6oX7tmnPXoYdF1Oejl86Vdq+tCrbouxGyGsDuOjNR0mXVdNOHUE3Dq9MWp24pT3y5O5XCoXq2MMDorQnpFkc7hIYYHEoWukN1BIlZ1o8hQHFKv7KqFOfkoPiIn6mSNxxoNhtmhmPnBfUHq8XIQerx1ipVi0hSCTYcaHZfHGKa+LjlYC8L7BPBTh7ingvAtS5EGQTfsiG49AUoX+8oEziHfjsbIa4wkdoa+YPMiUdBrRjc1GxXiEuQn1hhwuC5fpA5qDsACeE/J/WgVyjOGDeqxV7suStADZIrRuA5UMSrpjatowNngJWSMyfHGQrAd+v6YurWwklnBTc2Gla4k2l5DdvkLj7DWkkEa3qwAdb+H+DyoPM5WgA7oB10+uymG6vnsJoZmcQuvHrd6SlK0IPeykimoBeGeEIwVUp9CFgn3Qzglrcko11QySklXJK94u48ZIFbTaCOzdaBdApC8NmIEccIesqsE5qYc/vsxrQ682+zm0Ht2AnTX2+NB9mle/A/3B/f1zPsbTrLqYDXCXnb/lGpYmON5tM1HQslivXC5nBP1KudyKEji+aqYWoxghR1+V1Qux9MgeV8eWMZhWDxGWVLNCxKZ+O38675QRohoEEVB+mGFWr0iGgkG8WCV/9VSEV1w2KfZbswvmO0LiSFFNTzwFcwXa5GHY768tcDAzAc35pdegrDc91AwbI/5ULMicArT+MZ8dkSY+J5iDbJh3iPtRsCN95XmFpgPDDJfafe7mi1AB7xMqX9iqVsLHpqZLySeDoy2xnxPt733Qme+Bua7QoYcKYx9w8zXbe/dmH8w9kWxr9jexazOR0Ri/q9BGC2TOGCjX4t9EAeIOahxp4CdAIfNIlgXH2dJtC0DYOr8xMUlaOJKdC+ioSvBjx2hcIIw7hZza6V43wqdGlQ8BVKqsYuLIgXPRERg52UGYkWQ4cJH7BqF2cn0mmmg2QIQFney6rsImyJ/XMujET4irLFoR+0jyfLy92AVpkumC0NtolLeOGgQDAtYnNFpNFVuvzGhXmG3NCSrRxeW4LYSuneqzQzMPTF85/aEORBuJFVOapaTKvfPKsTO2XNRO8ioVYwJ+QHUV5Qi4UYH8BrCGJA9jbrwrLbtUEhLhVA9S4ACeR9DS/DuANUW2tmCoFgr27ue0ROKulzTEJT19w0IZy3JE9SUyL/OskiokMWG99YBmmyqfhVM53sFmtRkq9wedit1a+pU8EykXZ06yzKH23UK81WwppcTQBnQnHJFTYr0Yu8EXp3tOKh70krtK3dPGAr5jdH4dVS9d0CBQnhIWoSje2c0VcLietwVu5Cz6qwg0LoVn1iy1NlcEP1sw3YjgkYAp0nxa9wh8jKoeh0NBmwV0qIQ5SHdO7ApuvWGLWBXU2T8NUPaYjS9BkGAeAj2Djpai62rE4KyHfkxKt72eZjKZ3V+qIMlUaWSPweTKPmabuI8TouU8iTN83SpyDXnxUIDLotdzqPldl702htPAjZtxuyaB8WE6boL9okEdQuNm2vShPAMVBQkUk+GORChMlh1ApZjhntQ/JY2AuDSaGG1qsUGJrYXBJP6AAKfKFKEpwEBVLXpGhGhKlPUFrmxlNE9i1e3jO4la8pkM+j3iPEunuZVRrdDn87z0rlm9w+5sh6N5+O+YtHJxWtUUVujPrHBmhu8sUbraxpr3qjVpNhzp1GD2Gzd2MJ7g70bbVLfZudG9fu+8c6NGqWf33W7TrvSz5c9Lr0tHW3OP5sNHVtBcn0dHTVQ32afRzX1Zd9FbwtAm9S32QBQTX3Z1NfbAdAm9W32/1NT3zOq+bvngK9Gfys2Q2qRItb0t6In8KvV31fXLNCXfUe9zQJtUv/qWgX69vo0X3urQEORG79hVcutg6Cyck9hW946tw2rtd2OyKV6kHvr6MZQDs2ali+o55Upk7ShzPHWCqsHmg07SlaavlyISz2y9E20ggGOofTji+sFcyEmUVdZ2eD03HrEdEKv4fatnQH24tNHnXW9Jvy+id4xwDHdNOG6mscM4WwND73X0lMGOIbS66+rqYwhxa8pAvA2ms0og9y3fhzXVVmiKQzwVvt0AGCobecrbHgwRIDBRC1VQ1T31gdBTjN/iVfxMpBZ3V6Crd75Ry4F+ZxOg+K6ZfGUxyX7NEuzUXHzamNLx/mpvsulMDGrNQfsLkn6WJxyIvO6rhkq5UU120XMw0Yg9CIyUuRhfUxQcFxXcHpjuIqynbcrFmt4kaKWBEBNiVg1/+TdIyX+ie0mbuxs2HsFqHoO6GJng6LrMx8BsMnBmRMgJ1Bx8O6eFOX8+21ya+N7E2LUsWCihdnNJXdisb3JidrAWblg5cbZ8zkrbjR44KJFzsoLKTroUGCRsUPVMvVhIIW8DQdUG38bZqC84PrGwOaCWjFI6Fln4GERfH3tYhCGbCiJVw9NlvLFi+YBNBuL6eWXQh/xkRYf06G807xXd992Jg5YaWTEJz04hK/TKW1gFpRmnDQTdG0NsEr/2jwvJ2misFh0bhFQIrRZswmCUaXZ2tala5CLHbYIeGtc8sQt2xTqSxeX1OpWdvnug3zXduLf35tU13ldLVV7fA7R2eQ4sntVHCwLaKwmm/XuYPlA6BTqr7CeHqJnrvfd8XZvoiOm24DqRqyKfVKwIkAxVEdM9jVLC3Yc9UQxm7+kYVSc8Q8=</diagram></mxfile>
+\ No newline at end of file
diff --git a/IETF118/ngi.png b/IETF118/ngi.png
Binary files differ.
diff --git a/IETF118/nlnet.png b/IETF118/nlnet.png
Binary files differ.
diff --git a/IETF118/r5n.tex b/IETF118/r5n.tex
@@ -10,8 +10,9 @@
\usepackage{multirow}
\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}}
+\author{\textbf{Martin Schanzenbach~$\spadesuit$}, Christian Grothoff~$\clubsuit$, Bernd Fix~$\diamondsuit$}
+%\institute{\hfill\includegraphics[trim={0cm 1.5cm 0cm 0cm},clip,width=6em]{gnunet}\url{https://gnunet.org}}
+\institute{$\spadesuit$~Fraunhofer AISEC \url{https://aisec.fraunhofer.de}\\$\clubsuit$~Berner Fachhochschule \url{https://bfh.ch}\\$\diamondsuit$~GNUnet e.V. \url{https://gnunet.org}}
\begin{document}
\metroset{block=fill,sectionpage=progressbar,numbering=counter}
\maketitle
@@ -49,25 +50,22 @@ Restricted-Route Networks'' by Evans et al.:
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 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).
+ \item However, on the modern Internet the proportion of hosts with unrestricted communication capabilities is increasingly 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{frame}{Implications of restricted-route environments}
+ Problem:
\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.
- \end{itemize}
- \item Solution:
+ \end{itemize}
+ 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}
\begin{frame}{Example: PUTting some data}
@@ -105,12 +103,19 @@ Restricted-Route Networks'' by Evans et al.:
\end{center}
\end{frame}
-\begin{frame}{Route recording}
+\begin{frame}{Route recording for source routing}
Consider the following problem:
\begin{itemize}
- \item Another peer is very close to our own in the routing space.
- \item We should be directly connected, but cannot (e.g. firewall).
- \item Solution: TODO
+ \item Two peers want to use a communication channel.
+ \item They cannot establish a direct link due to underlay restrictions.
+ \item Assumption: Other peers are happy to provide relay services.
+ \item Payload transmission via PUT and GET would be inefficient.
+ \end{itemize}
+ $\Rightarrow$ Discover a route through the overlay:
+
+ \begin{itemize}
+ \item Peer adverstises existence of service via DHT PUT with route recording.
+ \item Client discovers service provider via DHT GET with valid route of GET/PUT message path.
\end{itemize}
\end{frame}
@@ -124,33 +129,40 @@ Restricted-Route Networks'' by Evans et al.:
\end{itemize}
\end{frame}
-\begin{frame}{Result filtering}
- R5N supports filtering results for no longer interesting values:
+\begin{frame}{Result filtering via mutated Bloom filter}
+ Queries could have a unique or multiple results depending on the application.
\begin{itemize}
- \item Allows us to "pause" queries and resume later w/o having to process all results again.
- \item Reduces traffic by aborting result forwarding early.
- \item Realized using a \textit{Bloom filter}.
+ \item We provide capability to abort query forwarding early if unique answer has been found.
+ \item We probalistically filter results already known to the client to reduce traffic.
+ \item To address false positives when using Bloom filters we use mutation.
\end{itemize}
\end{frame}
-\begin{frame}{Routing loop prevention}
+\begin{frame}{Optimization: Routing loop prevention}
+ Repeatedly visiting the same peer in GET or PUT operations is inefficient.
\begin{itemize}
- \item Routing loops are a common issue in DHT routing algorithms.
- \item R5N uses a \textit{Bloom filter} in request/response messages to prevent/identify routing loops.
+ \item Visiting new peers increases the chance of finding previously undiscovered results.
+ \item Visiting new peers drives us away from the starting point and towards more distant local minima.
\end{itemize}
+ $R^5N$ uses a \textit{Bloom filter} in GET/PUT messages to prevent routing loops.
\end{frame}
\begin{frame}
\begin{center}
- The R5N DHT\\
+ The $R^5N$ DHT\\
\url{https://datatracker.ietf.org/doc/draft-schanzen-r5n/}\\
- \vspace{1cm}
- DISPATCH: Are there any WGs interested in adopting/working on this?\\
+ \vspace{1em}
+ \centering Funded by\\
+ \includegraphics[width=2cm]{ngi.png}\qquad\includegraphics[width=2cm]{nlnet.png}
+ %\vspace{1cm}\\
+ %DISPATCH: Are there any WGs interested in adopting/working on this?\\
+ \vspace{2em}
+ \\Contacts:\\
\vspace{1em}
{\tiny
- \texttt{schanzen@gnunet.org}\\
- \texttt{3D11~063C~10F9~8D14~BD24~D147~0B09~98EF~86F5~9B6A}\\
+ Martin Schanzenbach \texttt{schanzen@gnunet.org}\\
+ Christian Grothoff \texttt{grothoff@gnunet.org}
}
\end{center}
\end{frame}
