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
There are still many places where there is either no internet access at all, or internet access is only provided by a single vendor that is next to useless. The hardware exists that would allow communities with limited technical knowledge to build their own networks, but I have yet to find the software.
Obviously in the civilised world we defer to our ISPs and their technical knowledge to maintain our connectivity, but why must it be like this? Why can't we just throw a bunch of old computers together along with some NICs, switches and cabling to make a self organising, self healing wide area network (an internet) that could be used by anyone.
There is plenty of old but perfectly functional hardware out there and already communities trying their best to make use of it. Maybe it could be made easy for them with a zero-conf USB bootable Linux distro that could run the nodes on one of these networks?
Add to the mix other new technologies like IPFS, and the whole of human knowledge could be made available to even the poorest communities, and there would be little to no congestion.
Am I dreaming here? Is there anything about the above that is unrealistic? Would love to hear opinions on this!
One project that comes to mind is the the OLPC project - they had a go at meshing their devices with 802.11s but, like most other routing protocols, it wouldn't scale up as far as it needs to.
Wireless meshing is something we are definitely interested in though. I am hopeful that with the iOS port that we may be able to experiment with true meshing over Multipeer Connectivity/AWDL (if Apple allow us to...) and there have also been efforts by the Toronto Mesh community to adopt and test Yggdrasil.
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?
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.
But yes, there's absolutely no reason that you couldn't stand up a whole load of VMs or containers and run Yggdrasil in each of them to play about.
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?
We have a kind of switch/router separation in the codebase where the spanning tree and locator switching is handled in the virtual switch. In our case, instead of MAC addresses, the switch deals in spanning tree locators/coordinates.