Karl Hans Janke Kollaborativ
Heute die Welt, morgen das Sonnensystem!

feb 2010

Really simple distributed DNS

There is a project, originating within the CCC, to link hackerspaces around the world into a common VPN. Within this, we would like to provide DNS; probably under a fake TLD, say .hack.

Well, you know, we like decentralized systems…

This post is about a prototype distributed system that, give or take a few design iterations, could actually be useful for decentralized name resolution.

Desirable properties:

At the conceptual level, the network's nodes represent any kind of communications medium. I.e. anything that messages can be sent onto with the expectation that all entities also on the medium will receive them.

Concretely there are two kinds of nodes:

Messages also come in two flavors:

When a station receives a message on a low-level link, it starts unwrapping the tunneling headers and propagates the message to any neighbors it has within the respective nodes.

Given the above behaviour, it is possible to construct networks of nodes interconnected in rather arbitrary ways. For the purpose of emulating DNS, and probably many others, it is useful to think of nodes as either representing hosts or being formed by joining (federating) a number of subnodes. The federations would correspond to DNS domains.

Determining how each station's table of node neighbor connections should look is left as an exercise to the reader. ;) The attached code contains a number of such context tables for an example network, pictured below.

rsddns-proto.klein.jpg
Diagram of a hypothetical network showing federations (circles with green labels), hosts (squares), and low-level links (lines). Shown in red is the path of an example message from within a hamburg subnode to a host in cologne.

To watch the example in action, run each of the following commands in a separate terminal:

$ ghc rsddns-proto.hs -e 'mainloop 2001 laptop_ct'
$ ghc rsddns-proto.hs -e 'mainloop 2002 daddel_ct'
$ ghc rsddns-proto.hs -e 'mainloop 2003 router_ct'
$ ghc rsddns-proto.hs -e 'mainloop 2004 turing_ct'
$ ghc rsddns-proto.hs -e 'mainloop 2005 b1_ct'
$ ghc rsddns-proto.hs -e 'mainloop 2006 b2_ct'
$ ghc rsddns-proto.hs -e 'mainloop 2007 k1_ct'

Then inject the test message from an interpreter prompt:

$ ghci rsddns-proto.hs
> s <- testsocket 5555
> testsend s "127.0.0.1" 2001 $ Mtun "pesco.hh.ccc.hack" $
      Mtun "hh.ccc.hack" $ Mtun "ccc.hack" $ Mtun "koeln.ccc.hack" $
      Mtun "k1.koeln.ccc.hack" $ Mstr "hello world!"

Note the DNS-like hierarchical node IDs and how the nesting of messages reflects the path through this hierarchy from pesco.hh.ccc.hack to k1.koeln.ccc.hack.

There is a 1s delay after each line of output so it's easy to watch the messages propagate. The destination node only prints out the message in this instance, but it would be trivial to include a return address and have it send back a useful answer (e.g. the station's IP address).

You will see a lot of backscatter of messages. This is due to the fact that the stations only perform a minimal check whether they have already seen a particular message. A proper implementation should avoid more.

Appendix: implementation prototype (Haskell): rsddns-proto.hs