Show HN: Yggdrasil Network – compact mesh routing experiment for mesh networks
Although we&#x27;ve had a couple of mentions on HN in the past, Yggdrasil has not really had a formal introduction here - we were keen to introduce Yggdrasil as a project rather than as a couple of version point releases. With that in mind, I&#x27;d like to introduce our project - the Yggdrasil Network (<a href="https:&#x2F;&#x2F;yggdrasil-network.github.io" rel="nofollow">https:&#x2F;&#x2F;yggdrasil-network.github.io</a>) - a proof-of-concept network to explore how we can build a decentralised IP network without the traditional scaling problems that other protocols tend to face.<p>There are plenty of mesh routing schemes out in the wild that have come before us - as an example B.A.T.M.A.N was merged into the Linux kernel back in 2011 - and many of them with different design goals, but one thing that many mesh routing schemes have in common is that they often have an upper size limit on the size of the network that they can practically support. In a protocol dependent upon external subnetting, especially where subnets may not practically map to physical locations (limiting the effectiveness of route aggregation), routing tables will become unmanageably large, cumbersome to replicate and difficult to keep up-to-date across the network.<p>CJDNS experimented with the idea of using a Distributed Hash Table (DHT) to look up the location of nodes on the network, which had two primary effects. First of all, nodes could be identified by their public keys rather than relying on external subnetting, which meant that it was possible to &quot;flatten&quot; the network down into a single address space (or key space) and IP addresses could be derived using a function of the node&#x27;s public key. Secondly, nodes would not need to store entire copies of the routing table - instead they would just store small pieces of information that they care about, and the collective knowledge of the network enables two given hosts to find a path to one another. However, CJDNS is source-routed and often suffered from problems in that the network was not always capable of determining the most optimal paths - nodes on the path were not able to use a better route or take shortcuts if available. This eventually lead to the introduction of &quot;supernodes&quot;. These supernodes would keep a full view of the network and allow other nodes to delegate path lookups but would require you to trust the supernodes and decreasing decentralisation in the process.<p>Inspired by CJDNS, Yggdrasil was born - a compact routing scheme implementation which would keep some of the useful features of CJDNS but attempt to solve the scalability issue without depending on supernodes. Nodes would still be identified by their public keys (and IPv6 addresses would be generated from them), a DHT would still be used to assist in locating nodes on the network but nodes on the network would be arranged onto a globally-agreed spanning tree. The &quot;root&quot; of the spanning tree is elected by a function of the node&#x27;s signing keys (although apart from being designated as the &quot;root&quot;, there are no other benefits) and all other nodes are given locators relative to the root of the node. This allows Yggdrasil to route greedily - the sending node only needs to know the locator coordinates of the remote node, and then each other node on the path can simply pass the packets on in the correct direction without being source-routed. This allows us to take shortcuts as a node on the path may know of a better route, or may know to avoid certain links as a result of congestion control. It also means that each node does not need to know much about the state of the network - they need to know their own locator and a path to the root, and other information is supplementary.<p>Around the middle of 2015, we had a barebones network simulator and eventually a prototype codebase written in Golang was released at the end of 2017. Just over a year later, we&#x27;ve released a number of alpha releases, added support for many platforms (including Linux, Windows, macOS and BSDs) and fixed a number of bugs. There are also on-going efforts to port Yggdrasil to iOS (lead by myself) and with plans to eventually support Android also. The Yggdrasil network currently sits today at around 130 nodes with a few members of our community running public services for consumption by network users. Our goal is to bring Yggdrasil to as many devices and places as possible, as ultimately what we need is to be able to test at scale, identifying and fixing problems if and when they arise.<p>Anyone is able to download Yggdrasil and join the network, and we welcome anyone who would like to join us in our channels or who would like to test or contribute.<p>- Our channels: #yggdrasil:matrix.org on Matrix or #yggdrasil on Freenode<p>- Our blog with some more interesting posts: <a href="https:&#x2F;&#x2F;yggdrasil-network.github.io&#x2F;blog.html" rel="nofollow">https:&#x2F;&#x2F;yggdrasil-network.github.io&#x2F;blog.html</a><p>- Our latest builds from CircleCI: <a href="https:&#x2F;&#x2F;yggdrasil-network.github.io&#x2F;builds.html" rel="nofollow">https:&#x2F;&#x2F;yggdrasil-network.github.io&#x2F;builds.html</a>