[freenet-dev] Re: What is backoff for?

[Ian Clarke]

Why use a median, rather than a mean? I'm concerned about this, it increases (yet again) the complexity of our load balancing, it hasn't been simulated, and I think there will inevitably be unpredictable results.  For example, what happens if *all* nodes have an AcceptedFrac below the median?  This mechanism will just spiral down until all nodes are hardly accepting anything. We can *not* afford to fall back into the trap of adding more and more complexity to the point that nobody understands what is going on, especially in the area of load balancing which is one of the areas that is most difficult to get our heads around. I really feel that we lack a "theory" of load balancing, a simple conceptual model through which we can think about the problem and find a solution.  Rather, we come up with idea after idea based on vague and invariably flawed notions and assumptions, layering one on top of the other until nobody understands what is happening. We must place a moratorium on all but the most trivial "improvements" to load balancing unless they have been simulated. Ian. On 9 Aug 2006, at 07:30, Matthew Toseland wrote: What is backoff for? It's not to prevent overloading nodes; nodes reject requests pre-emptively. What it is for is this: If we don't backoff slow nodes, then these slow nodes will have to reject (or occasionally timeout) the requests that we do forward to them. Those failures will be propagated back to the request senders, who will have to reduce their send rate. In other words, if we don't avoid sending requests to the slowest nodes, the requests we do send to them will be rejected, and those rejections will cause a universal slowdown in request rates. Thus, I don't think that the current mechanism is sensible. Nodes can be expected to take care of themselves, now that we have pre-emptive rejection. I don't think the ethernet analogy works 100%; we don't really have a shared medium. What we are looking at here is simply a way to ensure that requests are not forwarded to nodes who will inevitably reject them and thus cause an overall slowdown at the requester end. This is completely different to the case in 0.5, where requesters never slowed down. So what am I proposing? For each node, we track the proportion of requests which are accepted. We calculate a median. For any node above the median, all requests are forwarded to it: if most of our nodes are slow, that's not our problem, it's our peers who want to forward requests through us who have to deal with it (by not sending requests to us). For nodes below the median, we artificially narrow their specializations: While routing: public double distance(PeerNode node, double target) { double distance; if(node.acceptedFrac >= medianAcceptedFrac) { distance = rawDistance(node.location, target); } else { distance = rawDistance(node.location, target) * medianAcceptedFrac / node.acceptedFrac; } return distance; } Now, to some degree, this is alchemy, in the sense that it hasn't been simulated. However it will be some time before the new rate limiting mechanism is available, and it appears a solid argument to me: If all our peers are slow, that DOES NOT mean we shouldn't send requests to them. Because we have load propagation, it is entirely legitimate to send requests ANYWAY, and let upstream nodes deal with the slowness - either the entire network is slow, in which case we reduce all the send rates, or this particular node is slow, in which case we reduce the number of requests sent to it! Note also that slavishly following backoffs reduces our anonymity quite noticeably. Comments? --  Matthew J Toseland - [EMAIL PROTECTED] Freenet Project Official Codemonkey - http://freenetproject.org/ ICTHUS - Nothing is impossible. Our Boss says so. Ian Clarke: Co-Founder & Chief Scientist Revver, Inc. phone: 323.871.2828 | personal blog - http://locut.us/blog

PGP.sig
Description: This is a digitally signed message part

_______________________________________________
Devl mailing list
Devl@freenetproject.org
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl