OK, Here is a possible solution that addresses most of the current issues we are currently seeing.
requests out of both ends of the queue. One end is a LIFO. This would be the default end. When a new thread becomes available, it grabs a request from this end and removes it from the queue, and sends a query accept. On the
do we actually send an explicit QA message today ? If not, we would need to for this proposal. Nothing difficult here.
other end (the FIFO end) we should check if we have previously seen that key before. If we have, send an accept and process the request. If not, mark it as such, and leave it in the queue.
Then to prevent the queue from getting to large there should be some assumed timeout, where the requesting node just assumes it was dropped if it has been more than a given amount of time without an accept. If that much time has gone by and the request is still in the queue, then drop it, but don't bother to send any message back.
My only discomfort with this approach is the rough approximation of "time" between nodes. Assume that there is always a 5 second delay between a node sending a message and the other node receiving it. Of course, it will probably average much lower than that, but do not discount the effect of this delay. If requestor times out in 15 seconds, and receiver measures 14 seconds from receive time (he cannot use a timestamp provided by requestor - their respective clocks are NOT sync'ed closely enough) before he gets to it, he may send a response that will arrive after the requestor has timed it out. The bigger the timeout period, the less likely this is to happen, but it should always remain a concern. This is wasteful, and could cause some problems that are really hard to diagnose and debug.
I'm not sure that I like reordering (thus prioritizing) the requests. Suppose they are all for valid, findable content. The newest requests would always get serviced first, at the expense of earlier requests. This could lead to bad routing time measurements by the requestor, thus confusing NGR.
Because Freenet inherently uses more outgoing bandwidth, (some of the stuff has to come from our store) as soon as that becomes saturated, or we are out
I do not see any evidence of this whatsoever. In fact, logging the bandwidth here reveals the opposite. Now, this may be due to the longstanding QR issue we are attempting to address here and now. If I had to guess, I would expect ins and outs to be equal over a medium (not too short) time span in a healthy freenet. I see the logic of your argument, but most of our outbound traffic originates in inbound traffic (we usually have to fetch in order to share). To counter my own argument, we only take IN files once, and serve them OUT from 0 to many times. Still, I stand by my intuition that in=out over time. But I can't provide a quick proof in short order.
of threads, we need to backoff our processing of requests. In that case, it would benefit the network if we let other nodes know the situation, so they can backoff, rather than just having lots of requests fall off the queue.
I think we ALL agree at this point that some feedback from the requestee to requestor is needed, we just haven't completely agreed on a common solution yet.
So when requests start falling off the queue, we should start QRing incoming requests in proportion to our % overload. So, ideally speaking we accept exactly the number that we can process in any given period of time.
Yes, an optimal solution will reject or drop as little as necessary, and this clearly requires REaction on the part of the requestor. The drawback to dropping requests, as opposed to rejecting them, is that requestee is not helping requestor to refine his NGR profile of requestee. On the other hand, if requestor is purely a consumer (from requestee's standpoint), it may not be in requestee's best interest to avoid drops. Requestee has no idea how well this requestor serves the needs of the network, so we cannot know which (drop vs reject) is in the best interest of the network either.
Now to prevent any single node, overloading you at the expense of others, we should reject incoming requests with the probability of (FractionOfCurrentlyPendingRequestsFromThisNode * Current%OfOverload). This
I read this as FractionOf*TOTAL*CurrentlyPendingRequests,FromThisNode . This does not take into account the various bandwidth capacities for each remote node, but it is still a _significant_ improvement over current.
will insure that a node that is using more of the resources will be more likely to be rejected. Also so that other nodes know how likely they are to be rejected, it would be usefull if a query reject contained these two numbers.
I'm sorry, which two numbers ?
However the problem remains that regardless of the amount of resources that any node uses they would get the same performance. To solve this, instead of simply grabbing each request from the queue, on the LIFO end, each query should have a probability of being skipped over with a probability of FractionOfCurrentlyPendingRequestsFromThisNode. This way other nodes get more
I strongly favor this consideration, of "dropping every n-th request," which is the basic behavior that would result.
of a chance. Of course if it happens to skip through all the entries in the queue, it should just start from the beginning again. That way eventually one will be selected to be processed.
You're getting ahead of us yourself, by writing code in your mind.
This solves the problem such that, even under load the average successful time is fast. If we are overloaded, we don't necessarily waste bandwidth to tell
in some cases (request), faster than others. This may discolor the estimates in the requestor's NGR profile of 'us,' the local (requestee) node.
Tom - I would greatly favor a FIFO queue over the split LIFO/FIFO queue. It is more straightforward. I may have identified a problem with LIFO above.
I am not strongly for or against this exact proposal (so I'm wishy-washy?), aside from strongly against LIFO. It all sounds clever though.
Ken
_______________________________________________ Devl mailing list [EMAIL PROTECTED] http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
