FreenetWiki: Tree-based passive requests

Tree-based passive requests

We have to solve coalescing problems here, that is what makes it so complicated. Failure modes are what this is all about: normal operation is easy, it's what happens when you lose a connection, you get a better route etc, that matters.

The basic principle here is that the passive request metastructure is a tree. Each node on the tree knows the path to the current root. Not in terms of actual nodes, but in terms of UIDs which are generated at random and are different for each node on the passive request metastructure. Note that there may also be metastructure that isn't tree-form: we will happily accept offers of data through the other structures, if we need it, but it doesn't matter for routing purposes. And data, when found, will go up as well as down the tree, and sometimes perhaps sideways.

After = closer to the root (end of a request)

Before = closer to the branches (beginning of a request)

If we lose a node:

Before it:

The previous node, which loses the connection, is responsible for rerouting.

It temporarily takes root. It notifies all downstream nodes of this action. So the upstream root is no longer accessible, the node in question is now the root.

It then reroutes. The main risk here is eating our tail. If we route to a node which is already subscribed, we will normally become subscribed to it and allow it to take root. A reroute request will be rejected if the node it comes from is known to be on our path-to-root i.e. if we have a circle. However, if the root hasn't been updated yet, it may be accepted. If we then get an update, we have to send a rejection. The node must be ready for a late (possibly indefinitely late) rejection, and reroute to a different node if it gets one.

After it:

We send a LostDownstream message towards the old root. Each node on the path evaluates whether or not it needs to still be subscribed. If it doesn't, it unsubscribes from upstream; the root may end up abdicating and dissolving this end of the network. In which case, if rerouting reaches us, we will have to re-establish it. Therefore it may make sense to have a cooldown time to allow rerouting to reach the old root.

If we find a better route:

If because of swapping our upstream root is no longer the ideal route, we can again take the root, tell upstream we are no longer subscribing to them (triggering a cooldown period after which it will dissolve if we haven't gone back to it), and reroute. The same logic for safe rerouting applies.

Note that due to the likely level of churn on the network, we may need some inertia here.

Problems:

What if we end up routing to the ideal node, but it happens to be a very slow, very small, not well connected or malicious node?

Well, the data may be found further down the tree. In which case, we propagate it across as much of the tree as we can get to (we should know if there are possible sideways links - these don't affect routing or rerouting but can be useful data conduits as with ULPRs).

Also, routing should be biased such that lower capacity nodes get requests for a proportionately smaller part of the keyspace: RoutingCapacityBias.

Fundamentally Freenet is not 100% reliable. If an attacker can monopolise a specific part of the keyspace then he can censor keys in that area, and there isn't much we can do about this: rerouting only works well for either very popular keys, or for nodes trying to block keys that aren't exclusively their territory. Applications of passive requests will be subject to unreliability just like the rest of Freenet, and the standard solutions are available: FEC!

Lets take an example of an audio stream: The stream is divided into frames. The top level metadata for a frame consists of 4 SSK data blocks and 2 SSK check blocks. We put these back together to get 4KB of metadata. This 4KB of metadata gives us around 60 CHKs to fetch, so each frame is 40*32K = 1.2MB - around 10 seconds for a 1 megabit video stream, or 100 seconds for a 100 kilobit audio stream. A listener would subscribe to all six blocks for a given frame. SSK blocks cannot be reinserted, so the listener would have to cancel his subscription for the remaining blocks.

Cost of storage:

What is the ongoing cost of a subscription? Must we require a node to regularly renew their subscription in order to prevent this being used as a DoS?

Clearly there is limited space for subscriptions, although it's not *that* limited, we can handle many thousands of subscriptions without too much difficulty.

A client, or node, should be able to unsubscribe explicitly. It also unsubscribes automatically on shutting down. Apart from that, if a passive request falls off the end, we can tell it that it has been unsubscribed; it can then reroute, if it's important. This is essentially a load management question, so it requires a load management solution: maybe some form of token passing?

Fortunately this is a relatively easy problem. Each node knows what its capacity is for storing and rerouting passive requests. It can divide that maximum capacity up, according to:
- Fairness. If each node wants the full amount, each node gets the same number. But if some nodes don't use their allocation, the surplus can be - temporarily! - given to other nodes.
- Quid pro quo. Badly performing nodes may be penalized by reducing their quota.
- Priority. Local subscriptions may trump remote ones (although this may be dangerous so may be optional), and the declared priority may matter.
- Trust status. Darknet nodes may get more subscription capacity.

When the node needs to reduce the quota, it can tell the node explicitly, and kill the least important (according to priority given) requests until it is down to the right level.

A malicious node could clearly deprioritise other people's requests - but then it could just sabotage them by accepting them, not routing them and never relaying any data. As explained above, freenet will never be 100% reliable, and it won't function efficiently if a large proportion of the network is hostile cancer nodes; I don't think there's anything we can do about this.

Dynamic cost