We still have to queue the requests. This will result in extra latency and extra code - both of which are undesirable.
Another suggestion, from Toast:
Estimate the latest requests rank as compared to the last n requests
(100 for example). Compare the position in this list with the current
load (using Ians method or the standard method). Decide on that. The
number 100 is not alchemy as it affects precision of routing, not
routing it's self.
We keep an LRU list of the last N (say 100) requests, and their
estimates. This is kept as 2 doubly linked lists, one for the LRU,
another kept in order of the estimates.
When we get a request:
Calculate our own estimate.
Synchronize on the lists' sync object
Find the LRU request, and remove it from both lists
Walk the list sorted by estimates, and insert ourself in the
appropriate place. Remember our position numerically - the
number of nodes before us in the list.
Insert ourselves on the new end of the LRU.
Let X = target fraction accepted.
If our rank on the list was worse than X * N, reject the request,
otherwise accept it.
On Tue, Dec 02, 2003 at 08:53:27PM +0000, Toad wrote:
> Ok. The simplest implementation would be:
>
> Queue requests until they timeout (an initial timeout of say 500ms).
>
> Once a request's timeout expires, inspect the entire queue. Accept the
> acceptRatio * queue.length nodes with the best estimates, and reject the
> rest.
>
> This suffers from chunkiness - since we save no state from one iteration
> to the next, we end up with inaccuracies especially if we are too slow.
>
> So, we adapt the below technique:
>
> Sort the queued queries by their estimates.
> Use the mechanism described below to decide how many queries to accept,
> and update the numbers.
> Accept that number of queries and reject the rest.
>
> On Tue, Dec 02, 2003 at 08:45:18PM +0000, Toad wrote:
> > Whoops.
> >
> > Solving the wrong problem!
> >
> > Not only do we want to accept a given fraction... we want to accept the
> > best queries by their estimators... hmm.
> >
> > On Tue, Dec 02, 2003 at 08:23:27PM +0000, Toad wrote:
> > > Here is how I propose to implement selective accept on NGR:
> > >
> > > We keep two numbers:
> > > int totalRequestsAccepted
> > > double totalRequestsConsideredTimesLoad
> > >
> > > We have the function targetAcceptRatio(), which tells us what proportion
> > > of requests we want to accept, based on the current estimated load (if
> > > anyone has a non-alchemical way to do this...) - one possibility is that
> > > it is 1-load, another is that we accept everything up to some value (say
> > > overloadLow) and reject everything above some value (overloadHigh), and
> > > increase linearly in between. Because of the hoped for effects, I am not
> > > sure that the first option isn't the better one.
> > >
> > > When we get a request:
> > > totalRequestsConsideredTimesLoad += targetAcceptRatio()
> > > If totalRequestsAccepted > totalRequestsConsideredTimesLoad ,
> > > we know that we have accepted too many, so reject.
> > > Otherwise, accept, and totalRequestsAccepted++.
> > >
> > > Thus, we don't need to queue requests, there is no additional latency,
> > > and the implementation is really rather straightforward, apart from
> > > calculating the target acceptance ratio. And we accept the right
> > > fraction. We need to do some maintenance to maintain accuracy (subtract
> > > the largest whole part of both numbers from both numbers periodically),
> > > and we need one lock, but that's it.
> > >
> > > I will implement this on unstable soon, unless there are any objections.
> > >
> > > It requires NGRouting...
> > > --
> > > Matthew J Toseland - [EMAIL PROTECTED]
> > > Freenet Project Official Codemonkey - http://freenetproject.org/
> > > ICTHUS - Nothing is impossible. Our Boss says so.
> >
> >
> >
> > > _______________________________________________
> > > Devl mailing list
> > > [EMAIL PROTECTED]
> > > http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
> >
> > --
> > Matthew J Toseland - [EMAIL PROTECTED]
> > Freenet Project Official Codemonkey - http://freenetproject.org/
> > ICTHUS - Nothing is impossible. Our Boss says so.
>
>
>
> > _______________________________________________
> > Devl mailing list
> > [EMAIL PROTECTED]
> > http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
>
> --
> Matthew J Toseland - [EMAIL PROTECTED]
> Freenet Project Official Codemonkey - http://freenetproject.org/
> ICTHUS - Nothing is impossible. Our Boss says so.
> _______________________________________________
> Devl mailing list
> [EMAIL PROTECTED]
> http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
--
Matthew J Toseland - [EMAIL PROTECTED]
Freenet Project Official Codemonkey - http://freenetproject.org/
ICTHUS - Nothing is impossible. Our Boss says so.
signature.asc
Description: Digital signature
_______________________________________________ Devl mailing list [EMAIL PROTECTED] http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
