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

[Michael Rogers]

Matthew Toseland wrote:
> Two different failure modes. RNF means we ran out of nodes, DNF means we ran 
> out of HTL (randomly chose to end the request).

Right, sorry, at one stage I was thinking they should be merged if we 
switched to a weighted coin, so I lumped them together. I'm not sure 
whether I still think so (maybe RNF carries some useful information for 
the requester?) but I do think they should be treated identically in 
terms of branching (see below).

> Per node failure tables would probably be a 
> good solution: When we get a DNF, we don't route to that node the next time;

Sounds sensible.

> Firstly, why is this useful? Can't we just kill the request on getting a DNF, 
> and route differently next time?

We could - I hadn't thought of using failure tables, I was just trying 
to get as close as possible to the current search behaviour (ie limited 
branching).

> When we receive a request, we have a pDrop chance of killing it at that point. 
> If we don't, we route it.

Just to check: "at that point" means after checking the local cache and 
store, right?

> If a node gives us RejectedLoop, we move on; if a 
> node gives us a RejectedOverload, we evaluate pDrop again (we don't want to 
> keep searching for a non-overloaded node forever, do we?).

Maybe we should adjust the probability as we would with a DNF - counting 
overloaded nodes as visited will automatically adjust the load produced 
by each request to the amount of overload in the network.

> If we get a RouteNotFound, we evaluate pDrop again and continue.

So we move on without adjusting the probability? I'm not sure that's a 
good idea - an RNF visits at least one new node, so it should be counted.

> If we get a 
> DataNotFound, we drop the request unless random(1.0) < pDrop. We move on to 
> the next node, and if that also gives us a DataNotFound, we do the same.
> 
> So the probability of trying at least one peer is 1-pDrop, the probability of 
> trying at least two peers is pDrop*(1-pDrop), a third is 
> pDrop^2*(1-pDrop) ... (if we assume that almost all requests we do give 
> DNFs).

Sounds good - I think we should so the same for RejectedOverload and 
RNF, though.

Cheers,
Michael