Hi,
I agree with Ken and Ed in thinking that backoff is far from optimal. Here are my, "work in process", thoughts:
I don't care whether we do linear or exponential backoff, so long as we don't wind up with extreme back off times. It looks like Toad has already fixed this significant concern (of _completely_ inappropriate time spans exceeding an hour) for now... but there is always room for improvement. I support neither type of backoff, rather a 'one-time' backoff of a sufficiently long and randomized time. Or a basic value specified by the request receiver/rejector.
results we want backoff to produce. Think the answer to this is fairly easy. We want backoff to create network conditions such that most requests are accepted.
we believe that any given node, with its unique bandwidth capacity, will have an optimum qph value, below which bandwidth is not fully utilized, and above which, it becomes overloaded (slow). The division of bandwidth between queries and trailers is THE core issue. Without putting a limit on the number of simultaneous trailers, we intuitively hope that queries are handled in such a manner that a node does not become consistently overloaded. It's not a simple task! Even with a perfectly constant qph (between 2 nodes only), the bandwidth consumed by the resulting trailers will ebb and flow.
Ultimately, sacrificing all query bandwidth for trailers is a noble action. But we are truly hoping to find that magic balance between queries and trailers, one that maximizes the bandwidth used for content delivery. The only point of reference I can offer is to examine the size of the average query to the size of the average trailer. This may provide an insight into the magnitude of this magic ratio we are seeking... It is my opinion that trailers should occupy a majority of the bandwidth... others are free to dispute this with me :) If we could reserve a fixed percentage of bandwidth for query(routing) traffic, then the challenge would be to juggle the trailers in the remaining portion of bandwidth, aiming to provide the fastest delivery time (NGR's primary goal).
So how can we do this?
We know the average queries per hour of the network (Ga). Therefore an average node
wait, is Ga computed with any measurements provided from a remote node ? Or is this 'global' number simply derived from our local traffic ? Because we can't ignore that our unique bandwidth capacity differs from others... well, we can, but we shouldn't. This is why I am such a proponent of rate control. I'll assume Ga -is- a function of our local node's traffic only.
can process a request every Gr = 3600*1000/Ga ms. For a given node if we track the first time a request was accepted (At) after a failure and the number of request that succeed (Sc) we know that the node needs Gr*Ns ms to process these requests on avg
You appear to be suggesting that the requestor measure and adjust the output rate seeking the most efficient level (for both ends). But it seems the issue is more complicated than what we are discussing; a node's ability to accept a certain rate of queries is influenced by the degree to which trailers are consuming this shared bandwidth. Your description is a good analysis of the problem we face.
average. Therefore if we get a reject we should wait until At+Gr*Ns before sending additional requests. In the event of multiple failures or if At+Gr*Ns < the current time (NOW) we should wait until NOW+Gr before sending another request.
We don't know the exact qph on the requestee node (or do we?), but our Ga could serve as a good initial guess. It can then be adjusted towards whatever is optimum for that route/requestee. For any one given route, there is an ideal rate at which we should send our queries. This ideal value will likely change over time, as the requestee gains or loses other requestors. It may also be affected by the current bandwidth consumed by trailers. Only the remote node can measure and estimate its best availability towards to a single requestor. Which means either it can cooperate with the requestor by giving hints (speed up/slow down), or the requestor can simply guess, based on the timing of QRs. The requestor is attempting to become a CONSISTENT portion of a given requestee's qph. Or maybe it would be a better goal to state that we wish to consume a relatively constant percentage of that requestee's bandwidths (in & out).
We track the ratio of 1 - accepted Request (ARc) / Total Requests (TRc) as the Search Failed Probability. Using this scheme this number tells us how close the global average (Ga) a node is. The equation Nr = Gr*TRc/ARc should estimate the rate a node is actually achieving. This all implies we should use the following for backoff
are you suggesting that we attempt to sense the requestee's overall qph value ? I'm not sure I understand this part fully.
If (NOW > At+Nr*Ns | Ns == 0) Backoff_until = NOW + Nr Else Backoff_until = At+Nr*Ns
If all nodes use this scheme loads should drop until most requests are accepted. The global info available from the LoadStats object we can determine rational bounds for the ratio ARc / TRc.
I want to believe this is true. Variable trailer behavior makes the equation harder to compute, but in principle I agree with you completely.
If we decide to gauge and manage the ratio of routing vs. trailers between a pair of nodes, connection multiplexing is likely to make that task easier. We would only need to measure and balance a single connection.
This is what your formulas lead me to contribute. You've captured a good model for us to pursue, if other people also see any benefits to this approach. Of course we do have another option at our disposal: don't attempt to mediate anything, and just cross our fingers a whole lot! Much of this has probably been discussed in Freenet's past - I must download the old mail archives sometime for a reference !!! Currently I claim 'artistic license' through my ignorance of past efforts :)
-Ken
_______________________________________________ Devl mailing list [EMAIL PROTECTED] http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
