First of all, we actually have two topologies at play here: a global spanning tree and a snake/line. The spanning tree is very cheap to set up. Effectively the node with the highest public key becomes the root, you derive your coordinates on the tree as the path from the root down to your node, and as long as you know the coordinates of all of your direct peers, you can route “towards” a set of coordinates without really knowing anything else. This is largely what the Yggdrasil Network does today, in case you think it’s familiar.
The problem is that if the root node changes, or any of your direct ancestors between you and the root, so does the entire coordinate system and that’s fairly catastrophic. Imagine having a TCP session open but both you and the remote side’s IP addresses change at the same time — it’s very difficult to recover from that and is therefore terrible for node mobility. But for one-off bursts, like sending the odd control messages, it’s pretty much ideal given the low cost, and the stretch factor of these routes is generally super low (below 1.1) so they are quite direct in real terms.
Then we have the snake (where the SNEK acronym came from), which is effectively a line topology where all of the nodes are sorted into a line by their public keys in sequence. The actual routing paths that we use for Matrix federation traffic are built up by nodes looking for their immediate keyspace neighbours (nodes with keys that are very close to their own), even if they aren’t direct peers. Then setup messages are sent using the coordinate routing system from the spanning tree from nodes to their keyspace neighbours. These setups take fairly direct paths thanks to the low stretch of the spanning tree routing. Intermediate nodes on the path “snoop” on these setup messages to populate their own routing tables with entries for that given key.
When a node finally wants to send a packet to a public key, we consult the routing table at each hop for entries that take us to a key that is strictly closer to the destination key and then send the packet onto the peer that the setup message came from. As paths are built up between neighbours, more and more shortcuts become available to intermediate nodes so the routes become more direct. In addition to that, we also can synthesise routes up to higher keys by looking at which peer spanning tree announcements came from, since we know that the root node has the highest key and is therefore effectively the end of the line.
We believe that the scheme should scale reasonably well because we can quite effectively limit the amount of knowledge that a node needs to have about the rest of the network and still have it function (they ultimately only need to know about their keyspace neighbours, the root node and their direct peers, a handful of transitive paths to different parts of keyspace — anything else is merely a bonus) and because we’re learning most of the routing information by snooping, we can keep the amount of protocol traffic down. (At the very least, it is not artificially increased by communicating with lots of other nodes on the network). It also responds quite well to topology changes because when a node moves, it can send new setup packets to help the network build new paths, and there’s still a reasonable chance that the old paths will be roughly helpful at getting somewhere close to where the node was/is, up until the paths expire/time out.
Ultimately it is still experimental though and an active area of research for us, so we’ll see how it goes!