Show HN: Yggdrasil Network – compact mesh routing experiment for mesh networks

Although we'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'd like to introduce our project - the Yggdrasil Network (https://yggdrasil-network.github.io) - 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.

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.

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 "flatten" the network down into a single address space (or key space) and IP addresses could be derived using a function of the node'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 "supernodes". 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.

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 "root" of the spanning tree is elected by a function of the node's signing keys (although apart from being designated as the "root", 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.

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'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.

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.

- Our channels: #yggdrasil:matrix.org on Matrix or #yggdrasil on Freenode

- Our blog with some more interesting posts: https://yggdrasil-network.github.io/blog.html

- Our latest builds from CircleCI: https://yggdrasil-network.github.io/builds.html

This seems to have built on top of a lot of accepted ideas that were floating around in the academic peer to peer space in the early 2000s. Glad to see some of them getting traction in the wild aside from, you know, old school music pirating networks.

Finally got around to looking at this and had a couple questions if you're still checking this thread.

Your 0.3 announcement mentioned switching from Kademlia to Chord for the DHT but doesn't go into much details. The lookups are consistently fast, and maybe consume less storage? But Kademlia seems from a topology point of view to more closely match your network and seems to have significant advantages for networks that have ephemeral nodes.

A bit less technical but is there an overall goal for the project? Was this trying to solve a specific issue (such as consistent mobility addresses?) or is this more of a project to test out a combination of findings from research papers?

It occurred to me reading the headline that you could simulate all of the nodes in a virtual environment.

So kind of a general question, but: could you or do you have a way to like, run a VM on your computer where you could ssh in have a big open area to turn on nodes and play around with various network topologies, or the software running in each node? Other people could ssh in and pretend to be a node too.

That way we could try running it on our computers and debug the stack in each node, and then if it works, we could download the stack into our own routers and devices and run it in the real world.

This looks really interesting, I'm currently at work but will check out in more depth later!

From a quick scan I can't understand, how does the tree work for routing with a fixed node address when the node is moved?

Would it be possible to embed or import the yggdrasil codebase into my own golang project, so that I could opporate my software project in its own namespace or keyspace?

I will check this out later but for now, _what_ a good name. Although I'm not sure how good the connectivity is in Helheim.