[freenet-dev] Weighted coin is better was Re: Moving to a simple coin was Re: Tunnels vs premix routing

[Michael Rogers]

Matthew Toseland wrote:
> We want to reduce the number of requests, not make the requests we do use less 
> load and therefore be less successful and contribute further to the problem, 
> surely?

Yes, good point - overloaded nodes shouldn't be counted.

> Killing the request (95% of the time) on an RNF means small darknets will 
> perform *very* badly. IMHO it is important that small networks be functional, 
> especially if we are expecting them to be merged into larger networks 
> eventually.

I'm not convinced it's possible to merge two Freenets without screwing 
up routing and caching pretty badly, but OK. :-)

There's roughly a pDrop chance of each upstream node branching when it 
gets an RNF, so forwarding an RNF isn't quite equivalent to killing the 
request. But yes, it's closer to killing the request than under the 
current system.

The alternative - branching with probability 1-pDrop - is dangerous in 
large with networks with dead-ends. Remember that if the average 
branching factor exceeds 1, every search will try to visit the entire 
network.

It seems to me that safety in large networks is more important than 
performance in small networks, where you can afford to retry the request 
if you get an RNF.

> The RNF sub-tree is not really part of the DNF tree.

You can call it two separate trees if you want, the point is that the 
number of nodes visited by the request should be finite, and that means 
each node must forward less than one copy on average (excluding rejected 
copies). If we make exceptions for dead ends we'd better be sure they're 
going to be rare, and I don't see how we can be sure of that - in fact I 
would have thought dead ends would be rather common in any real-world 
topology.

> However, if we send a request to a node, 
> and it returns an RNF, we know that it ran out of nodes - it's a dead end.

Yes, and if we search the entire network and don't find the data we can 
call that a dead end too. To paraphrase Keynes, "in the long run we're 
all dead ends". ;-) We have to limit the number of nodes visited, 
including dead ends.

> AFAICS it provides only a multiplicative effect on the total number of nodes 
> in the tree.

Not so, because every branch multiplies in the same way (and so do its 
branches, and so on).

> I was trying to understand your proposal, I'm not saying I support it. The 
> other option - for DNFs to be fatal - is much simpler.

True, and per-node failure tables would probably solve the rabbit hole 
problem. And I guess the requestHandler/Sender logic would be simpler if 
we didn't have to think about moving on to other peers, and the timeouts 
could probably be tighter.

Cheers,
Michael