A couple of questions about the protocol

[m1kc]

Hi there!

I learned about the Yggdrasil project only recently (I've used cjdns, Zeronet, I2P in the past). I've tried it out, and it works very well — if someone's interested, I get sub-200 ms latency for most sites and highest bandwidth I've seen was ~30 Mbits/s, which is very good in my eyes.

So, right now I'm trying to learn a bit more about its architecture and how it actually works. I've read the whitepaper, some old Readme and a couple of articles on other websites, and while they provided me with a good initial overview, some things remain unclear to me:

1. As far as I understood, Ygg logically organizes all network nodes into a spanning tree with an arbitrary root, chosen as the node with lowest ID. If that's correct, does every node store the whole tree locally? Or they only store a path to the root? Or some other subset?
2. Again, as I understood that: when the root node sends a beacon to its children, every subsequent node adds its own ID and some number carrying information about measured bandwidth to the previous node, which is called a metric, and the sequence of metrics is called network coordinates. Did I get the whole thing correct? ('Cause the whitepaper describes these things somewhat vaguely, so I'm, like, very not sure.)
3. What is the DHT used for? As I understood, it's used to look up nodes' private public keys — and it's also used to look up node's network coordinates... is this correct or not?
4. Assuming I somehow got all the above concepts right (which I probably didn't, who am I kidding), could you explain in more detail how is the actual routing done - like, when a packet arrives, how does a node determine its next hop? The whitepaper says that:

Traffic is forwarded using a greedy routing scheme, where each node forwards the packet to a one-hop neighbor that is closer to the destination (according to this distance metric) than the current node. In particular, when a packet needs to be forwarded, a node will forward it to whatever peer is closest to the destination in the greedy metric space used by the network, provided that the peer is closer to the destination than the current node.

Assuming that I got the above parts right, node's network coordinates are essentially a N-length vector of bandwidth measurements directed towards the root node - how is this information useful for routing? Or does the forwarding follow the tree topology, sending traffic first to the nearest common ancestor and then back down?

---

Thanks in advance for your patience, I know that such stuff is a pain to explain.

[chpio]

im also new to this...

As I understood, it's used to look up nodes' private keys

Nah, that one certainty not. Maybe the pubkey of the node (that then is used for the encryption) (but im just guessing).

and it's also used to look up node's network coordinates

Yes, that's the main use case for the DHT.

vector of bandwidth measurements directed towards the root node

I think this is only used to built/organize the tree then the tree is used for the actual routing.

Or does the forwarding follow the tree topology, sending traffic first to the nearest common ancestor and then back down?

I think this is how it's done. + if there's a direct peer on that path that has a shorter path to the destination then it takes that shortcut.

---

What are the consequences of the root node going offline? Does it involve re-organization of the whole network to a new root? Does it make the whole network vulnerable to a DDoS on the root node?

[Arceliar]

Good questions, let me see if I can provide some clarification:

1. As far as I understood, Ygg logically organizes all network nodes into a spanning tree with an arbitrary root, chosen as the node with lowest ID. If that's correct, does every node store the whole tree locally? Or they only store a path to the root? Or some other subset?

It's actually the highest ID, but that's otherwise the right idea. A node doesn't need to store the whole tree. At the tree level (in switch.go), you store the path from the root to yourself, and the path from the root to each of your peers (plus the 1 extra hop to yourself, in case you wanted to switch to using that peer as a parent in the tree). The per-peer information we get basically for-free as part of the spanning tree protocol.

2. Again, as I understood that: when the root node sends a beacon to its children, every subsequent node adds its own ID and some number carrying information about measured bandwidth to the previous node, which is called a metric, and the sequence of metrics is called network coordinates. Did I get the whole thing correct? ('Cause the whitepaper describes these things somewhat vaguely, so I'm, like, very not sure.)

There's no bandwidth measurement happening to build the tree. It's based on latency, and then bandwidth comes in when we make forwarding decision later (question 4). But that's otherwise basically the right idea: the root sends a beacon to each peer letting them know that the root is still alive and what the path from the root to them is. The peers update their own local state with that info and then forward this message to each of their peers, and in each case they append a little info about how to get from themself to that peer, so now the next generation of nodes has a path from the root to their parent and then to themself, and this keep going until the whole network gets an update from each of their peers.

3. What is the DHT used for? As I understood, it's used to look up nodes' private public keys — and it's also used to look up node's network coordinates... is this correct or not?

That's pretty much right. Without going into too much detail about how things are implemented internally, the DHT basically lets you look up an IPv6 address and get back 2 things: a public key and "coords". Your node then checks that the public key matches the IPv6 address (the address is a specially truncated sha512sum of the public key), and the are a path from the root to that destination node (encoded in the format the network uses to forward packets).

4. Assuming I somehow got all the above concepts right (which I probably didn't, who am I kidding), could you explain in more detail how is the actual routing done - like, when a packet arrives, how does a node determine its next hop? The whitepaper says that:

Traffic is forwarded using a greedy routing scheme, where each node forwards the packet to a one-hop neighbor that is closer to the destination (according to this distance metric) than the current node. In particular, when a packet needs to be forwarded, a node will forward it to whatever peer is closest to the destination in the greedy metric space used by the network, provided that the peer is closer to the destination than the current node.

Assuming that I got the above parts right, node's network coordinates are essentially a N-length vector of bandwidth measurements directed towards the root node - how is this information useful for routing? Or does the forwarding follow the tree topology, sending traffic first to the nearest common ancestor and then back down?

So you're very close. The coords are a vector of next-hop info from the root to the destination. Coords that look like [1 3 3 7] would mean "the root's 1st peer's 3rd peer's 3rd peer's 7th peer", basically. The important thing is, if another node's coords are [1 2 3 4] then you know that the worst case scenario path between these two nodes is [1 3 3 7] -> [1 3 3] -> [1 3] -> [1] -> [1 2] -> [1 2 3] -> [1 2 3 4], a path with 7 nodes going through 6 network hops, if the packet was routed on the tree.

In the real world, we can find shortcuts. In the above example, lets suppose that [1 2 3] and [1 3 3] are peers with eachother. Then the packet could start forwarding along the path above, but [1 3 3] sees a shortcut. If there are no other shortcuts, and the network isn't congested, then the actual path of the packet would be [1 3 3 7] -> [1 3 3] -> [1 2 3] -> [1 2 3 4] with only 4 nodes and 3 network hops.

You'll note that I said if "the network isn't congested" -- when a packet arrives at [1 3 3], and no links are currently busy sending a different packet, the they'll forward along the shortest path. if the [1 3 3] -> [1 2 3] link is already buys, and [1 3 3] -> [1 3] is idle, then they'll forward on the idle link rather than delay sending the packet. If both are busy, then they'll buffer the packet, and forward to whichever one becomes idle first. The rules for how things get buffered are kind of complicated, but basically, priority is given to streams of traffic that consume less bandwidth, so low-latecy low-traffic applications (e.g. games) don't get crowded out by big downloads.

The intent with load balancing as we forward is that, when traffic is low, things tend to follow the lowest hop count (often lowest latency) path available, and then tend to settle onto higher latency (or at least higher hop count) but higher bandwidth paths for large downloads.

What are the consequences of the root node going offline? Does it involve re-organization of the whole network to a new root? Does it make the whole network vulnerable to a DDoS on the root node?

Each node independently selects the root as "the best node that's sent a new announcement out recently". If the root is idle for too long (1 minute), then everyone tries to make themself the root instead, and the next best node wins (almost immediately). But yes, a malicious node could do things like repeatedly connect and disconnect to "flap" the network, or use the same key on two different (and disconnected) nodes to confuse the network. In that 2nd case, I'm pretty sure they'd just split the network in 2, with nodes joining whichever one has a closer root, although there'd be some weirdness for nodes at the boundary between trees. The intent is that, if the root is unreliable (either because they're evil or they're just malfunctioning), then there are at least 2 obvious fixes:

1. People connected to the root disconnect from it, because they see that it's a problem. If they don't, then the peers of those people could disconnect from them instead.
2. Or, there are enough honest users that they can spend the CPU power for somebody to find a better key and replace the root.

[neilalexander]

Closing this due to inactivity.