In this paper, the scalability of the experimental Yggdrasil routing scheme regarding its logic, hop limit, CPU usage, and memory footprint is discussed. Experiments with the routing daemon are conducted on large- and small-scale topologies using meshnet-lab and coreemu-lab environments. The experiments show Yggdrasil to significantly outperform in hop limit other widely used mesh routing protocols, such as OLSR and Babel, give an insight into system resources usage trends, as well as reveal several caveats of Yggdrasil-based networks and a potential way of mitigating them. Taking into account the carried out research, Yggdrasil can be considered a valid and promising basis for the deployment of large-scale decentralized mesh networks of independent nodes as an alternative to traditional centralized hierarchical networking.
Nowadays centralized software-defined networking is becoming increasingly popular with Internet service providers (ISP) due to its remarkable benefits in automated remote hardware configuration, That said, the mentioned benefits come with a trade-off at the cost of network reliability and disruption resilience, as centralization inevitably adds singular points of failure to the system. A consequence of this is the relatively recent infamous Kyivstar network collapse that occurred on December 12, 2023, resulting in several days of downtime with a complete lack of customer connectivity. Numerous services throughout Ukraine relied on Kyivstar and could not function until the damage was eventually mitigated.
This incident shows how unreliable centralized hierarchical communication systems may be and calls for a different approach mesh networking, where the line between routing and terminating (end) devices becomes blurry. The idea of this paradigm lies in every node of the network being able to function independently from any other, establishing connections with other nodes nearby (peering), and collaborating in an effort to route traffic for each other, rather than relying on a central authority for this.
While the concept of mesh networking is not new and a number of routing protocols have been
developed (OLSR, Babel, B.A.T.M.A.N. and its derivatives) and successfully used (e.g. the Freifunk
local networks and do so efficiently, as in use the least amount of system resources needed for
functioning, so that it could be deployed on relatively low-cost low-power devices. Another
network and potentially eavesdropped on by intermediate nodes [
Most research in the field of large mesh network routing focuses on its implementation for IoT and
wireless sensory networks in particular, optimizing energy consumption and range at the cost of
throughput and security. For example, a CottonCandy [
The described approach has a number of additional advantages: nodes generate addresses for
themselves independently; transparent asymmetric end-to-end encryption; source/destination
verifiability with cryptographic keys used for addressing. Network congestion is managed
automatically at each node using a form of fair packet queuing, which attempts to balance traffic
traffic does not always take the shortest possible path, introducing higher latency, which can,
however, be accounted for. Link quality is also not considered outside of priorities between
multiple peerings to the same. Every node of the network only holds in memory a 1KB bloom filter
for every on-tree link as well as 32B keys of its direct peers and their ancestors on the path to the
links and the distance from the current root. As for CPU usage, notable spikes are expected on the
transmitting and receiving nodes due to encryption and decryption taking place respectively, as
well as some positive correlation with the number of links. Due to the Yggdrasil routing scheme
cover or even mention it.
testbed network as a NAT traversal tool for the purposes of remote control, but no scalability
testing of the routing scheme itself. Another work [
The purpose of large-scale benchmarking is to determine the performance of Yggdrasil on large networks (50 nodes and above) while recording the system resource (CPU and memory) usage of . Such testing is meant to give an idea of technical specifications of hardware needed for an Yggdrasil network, as well as to show its hop limit if there is one. Scaling of system resource usage and convergence time with network size is also important when deciding on the viability of the routing scheme.
The tests were conducted using the meshnet-lab environment due to its flexibility, the
possibility of emulating large-scale topologies with Linux network namespaces [
Prepare a topology with pre-generated JSON files included in meshnet-lab, and limit link bandwidth to 100 Mbit/s. Launch routing daemons on nodes. Launch the system resource monitoring script (records CPU and resident memory usage of routing daemons every second). Wait 30 seconds for nodes to discover each other.
Over the next 30 seconds send out a total of N unique random pings with a minimum hop count of 2 and a deadline of 30 seconds, where N is the number of links in the topology. Wait 15 seconds. Repeat steps 5-6 five more times.
Launch the node information collection script (requests Yggdrasil-specific information, such as public keys and tree views, from the routing daemons; needed to determine the root node in result processing). Stop the routing daemons and resource monitoring scripts, and clear the network. Repeat the procedure on a bigger topology until less than 40% of the pings arrive or more than 750 nodes are to be simulated.
The described procedure was conducted on random tree and line topologies (Figure 1) as a more realistic and worst-case scenario respectively. On larger topologies, it was needed to increase the number of iterations in step 7 for the network to reach convergence. Additionally, for the purpose of looking into the memory usage trend on a converged network, prolonged experiments were conducted on the largest viable topology.
A topology is considered viable if it ends up reaching convergence indicated by 100% ping arrival. Another experiment on a random tree topology of 50 nodes with no bandwidth limitation showed the difference in CPU usage for transmitting, receiving and intermediate nodes, as well as nodes not taking part in the transmission.
Traffic was generated for 10 seconds between two distant nodes (001e and 0032, see Figure 1) using the iperf3 utility. Lastly, an experiment on a 750 nodes line topology with imperfect slow links showed Yggdras silience to such conditions. Link parameters applied here were 10 Mbit/s bandwidth with a 10±5 ms latency. Traffic was generated between the first and last node using the standard ping utility.
The last two tests were performed manually. The benchmarking procedure was automated with
-lab. Resulting data was
analysed and plotted using pandas, seaborn and Matplotlib Python libraries [
The purpose of smallcomplicated scenarios than a large static network. Due to this, the testing process was more exploratory in nature. Overall, we needed to see how exactly the Yggdrasil spanning tree is arranged, what paths the traffic takes, and how tolerable node mobility is. This information is important in that it exposes potential caveats and flaws of the routing scheme. For this, a tree topology with a known root would be built.
After launching Yggdrasil routing daemons on it, additional links were introduced. The resulting network would then be analysed by querying the routing daemons about their views of the tree and launching various one-sided traffic flows to see the paths they end up taking. Node mobility tests were done by having one roaming node jump between static peers while pinging another node.
Of particular interest here were the cases of a node choosing a new parent upon losing the current one and the network having a roaming root node.
The tests were conducted in the coreemu-
with automated testing and node monitoring functions [
Node movement can also be automated with mobility scripts. Another useful feature of CORE is the visualization of throughput on wired links and wireless interfaces, allowing for traffic flow tracing. The provided Docker image was modified to include the Yggdrasil routing daemon. The following tests are run with pre-generated keys for every node for better control over the Yggdrasil spanning tree.
The results of memory benchmarking on the random tree topology are presented in Figures 2 and 3.
Figure 2 confirms the assumption about the memory usage of a node being positively influenced by the number of its links. Figure 3 shows that, despite the increase in overall network size, memory usage for the absolute majority of nodes stays roughly within the same range. Packet arrival for random tree topology stays at an all-time 100%.
Figures 4 and 5 depict the results of the same benchmark conducted on a line topology. Because on line topology every node except the first and the last one has only two links, the hue and size of
Comparing Figures 3 and 5 confirms the assumption about memory usage being positively influenced by network length. This is also confirmed by peak memory usage per topology presented in Table 1.
This trend is much more noticeable on linear topologies, although for network sizes beyond 300, it stops being as consistent. It is also clear that on eith necessarily result in higher memory usage. In fact, due to nodes keeping in memory only their and mory usage can be seen on the nodes further away from the root. That said, outliers are also present, like nodes far from the root with lower memory usage and the other way around, as well as nodes with a lower link count, but higher memory usage. This can be partially attributed to the randomness of pings. Overall, even on a 750 node line the memory footprint of the routing daemon did not exceed 33 MB, and, following the observed trend, it is expected to rise fairly slowly beyond that. length and is greater the closer to the middle of the line a particular node is. Furthermore, the root node seems to always divide the line into two parts, for which length and middle points are considered separately. This is especially clear on 700 and 450 node lines, where the root node happened to be closer to the middle. On the former, there are significantly fewer nodes to the left of the root than to the right of it, resulting in a massive CPU usage difference while still keeping the trend of middle nodes having a greater CPU usage for both sides. The 450 node topology has a similar case, exce overall CPU usage than the smaller 400 node network. This observation leads to the conclusion that it is more beneficial to keep the root of the network closer to its actual center, as in keeping the number of nodes on every branch roughly similar. One of the ways this can be achieved is
Note: CPU usage is recorded with the standard Linux ps utility, in which, according to its
manual page [
Figure 7 features the packet arrival ratio over time on a line topology for different network sizes. Line points are slightly shifted on the time axis due to pings having a longer round-trip time on longer topologies. The 700 and 750 node networks never quite reach 100% packet arrival. Upon meshnet-lab environment on long topologies it needs to wait significantly longer for the initial packet to arrive because of node lookup taking place. This leads to it sometimes sending a second ion, we can consider packet arrival above 95% to signify a converged network and find out the approximate convergence time presented in Table 2. It should be noted that the measurements were recorded at least 60 seconds apart from each other, so these numbers should not be taken at face value. They can, however, be used to build a convergence time plot shown in Figure 8. The resulting plot suggests a linear relation between network length and convergence time.
For comparison, the same experiment on a line topology was conducted with different routing protocols (OLSR, Babel) and showed their inability to handle long networks packet arrival goes below 80% at 150 nodes and below 40% at 450 (see Figure 9).
Extended experiments were also conducted and showed packet arrival to never increase for these protocols.
Memory usage over time on a 750 node line topology is presented in Figure 10. The lines have decreased opacity to indicate a general trend, which suggests constant memory usage after the network reaches convergence. The results of CPU usage measurement on a 50 node random tree topology without bandwidth limitations are featured in Figure 11.
The plot suggests receiving and transmitting nodes to have the greatest and second greatest CPU usage respectively, with intermediate nodes following them and the rest of the nodes not taking part in the transmission, which confirms the assumption mentioned in section 3.1. The CPU usage measurements rise while the transmission is ongoing, and then gradually fall off due to the specifics of the ps utility implementation mentioned earlier.
The experiment on a 750 node line topology with slow links showed 749 hop communication to be possible still, albeit with a considerable latency of 18 to 20 seconds, which calls for delay tolerant applications to be used with such a network.
The results of large-scale tests demonstrated the lack of observable hop limit with linear scaling of convergence time to network length. Memory usage also scales with network length instead if its overall size, staying within acceptable margins. CPU usage was shown to be influenced by root node placement, opening up a way of optimizing it. Thus, Yggdrasil is confirmed to be viable for use in large mesh networks.
The first small-scale experiment was conducted on a 9 node line topology with node n1 establishing links with several nodes in said line. The network and the corresponding sequence of actions are shown in Figure 12. Purple arrows indicate the structure of the Yggdrasil spanning tree in th child being its child. Then, peerings with n2 and n7 are established in this exact order. When n1 n5 link gets severed, n1 consistently chooses n2 as its parent as the link with the longest uptime, despite n7 being closer to the root. While this logic might seem inefficient, it keeps the network more stable by eventually leaving only the most stable links in the spanning tree and thus making network. It also becomes clear how exactly the spanning tree is built the keys only matter in the choice of the root node, which becomes the point of reference for the rest of the network. The spanning tree is arranged around the root based on the links that are brought up first and taken down last.
The next experiment was conducted on a 13 node network featured in Figure 13. Here, wired links are used for the majority of nodes with unidirectional traffic flows between nodes n1 and n2. Due to greedy routing, these traffic flows end up taking different paths. Off-tree links n12 n14 and n13 n15 allow the traffic to skip two nodes and are thus taken. While this feature of traffic flows between two nodes taking different paths may not have been intentional, it is beneficial in providing more bandwidth and mitigating congestion. However, greedy routing has its disadvantages, mainly in only considering single link paths. An example of this is can be seen at the bottom of Figure 13. The network is the same as in the previous example, except nodes n14 and n15 are swapped places. As a result, links n12 n14 and n13 n15 no longer provide any immediate benefit f view, thus not being taken. This results into both traffic flows taking the same longer path through the root node. Two experiments regarding node mobility were conducted, one with a leaf node being the roaming one and one with a roaming root on a bigger network. The former involved node n1 constantly jumps between leaf nodes in the network presented in Figure 14.
Such behaviour did not impact the connectivity within the network besides node n1 itself. Indeed, constantly changing peers means constantly changing tree coordinates, thus preventing any prolonged traffic flows to the roaming node or disrupting them with node lookups. Traffic originating in node n1 has a better time reaching its destination given that the destination is a static node, as its tree coordinates do not change after the lookup and throughout the transmission. To successfully receive traffic, a roaming node has to maintain at least one constant peer for the duration of the transmission, otherwise it would be interrupted with a node lookup. Thus, Yggdrasil tolerates node mobility but does not encourage it and requires nodes to maintain their coordinates for bidirectional data exchange.
A roaming root node, however, is an entirely different case. Figure 15 features a network similar to the previous example, except this time the root node n9 is constantly jumping between pairs of leaf nodes with a period of 10 seconds. This causes the nodes it comes into contact with to change their tree coordinates and propagate this change throughout the network as they should, however, by that time the root comes into contact with different peers, causing a conflicting reordering to propagate as well. This results into nodes having different views on the spanning tree, which, in turn, is the reason of various traffic anomalies seen in Figure 15. On such a small scale the traffic between n18 and n26 takes the correct route for the majority of time, only sometimes being disruptions in a larger network, especially when new root node candidates pop up in completely different parts of the network. This can be considered a potential attack vector. A possible way to mitigate it is the previously mentioned low key mining, allowing for a constant root to be set up with a pre-generated considerably low key, to the point of mining for a lower one becoming unreasonable and detrimental. It would also make sense to set up several potential roots like this for the sake of redundancy.
Small-scale testing exposed the logic behind spanning tree arrangement and traffic routing, which strives for using the most stable links for the spanning tree and taking shortcuts where possible with the lowest effort from intermediary nodes. Mobility tests showed Yggdrasil to require at least one stable peering for the receiving node during transmission, while otherwise roaming leaf nodes only affect their own availability with eventual reestablishment of it after mobility events cease. Root node mobility was found to be a potential attack vector with deterministic root placement available as a means of mitigation. Thus, Yggdrasil is shown to be fitting for semi-stable networks with no requirement of uninterruptible transmission during mobility events.
In this paper the scalability of the experimental Yggdrasil routing scheme in regards to its logic, hop limit, CPU usage and memory footprint of the routing daemon was discussed. The computational complexity of node lookup/routing was evaluated as linear to the number of on-tree links/peers of a given node. A number of experiments were conducted on both large- and smallscale topologies using meshnet-lab and coreemu-lab environments. The results of the experiments showed Yggdrasil to significantly outperform in hop limit other widely used mesh routing protocols, such as OLSR and Babel. The experiments also showed the typical convergence time, as well as memory and CPU usage trends of Yggdrasil and confirmed their scaling with the depth of the network rather than the overall size of it. The memory footprint of the routing daemon never exceeded 33 MB. This makes Yggdrasil a valid and promising basis for the deployment of largescale decentralized mesh networks of independent nodes as an alternative to traditional centralized hierarchical networking used in ISP networks.
Testing also discovered several caveats in Yggdrasil-based networks, such as increased CPU usage on longer spanning tree branches and traffic anomalies introduced by a roaming root node. Preemptive low key mining for deterministic root node placement was suggested as a means of mitigation for these problems.
Before planning and constructing a real prototype network based on Yggdrasil, a number of
other topics have to be researched, like preferred underlying link and physical layer technologies,
required hardware, deployment on common hardware, user adoption, etc. Another question of
rather significant importance is security, especially with Yggdrasil being an open network as any
node is reachable by any other (in contrast to Carrier-grade NAT employed by ISPs [