The problem with this is that it will quite happily route almost all requests to an ubernode... Hence we need a second mechanism to ensure some level of fairness. One thing that was proposed was that we have separate token buckets for this purpose.
That goes something like this: The below is incomplete. We need to check whether there is a request to be sent not only when we get a token, but also when we get a request. We calculate the median node speed. Any node which is faster than this, we limit to the median speed. Any node slower than it gets full speed. How to implement? A token bucket. No matter how many tokens the node has actually granted us, we don't let a request be forwarded unless it has a balancing token as well. Each node has a bucket of balancing tokens (this is just a counter), the same size as its outgoing requests bucket. We add tokens to these buckets, considered as a whole, at the same rate as tokens come in overall. But we add them in proportion to the desired speed distribution above. So we use floating point counters, and add a fraction to each counter when a request token comes in, perhaps... Problem with the below: How many tokens do we start with? If not full, then the one picked will be filled by the add-to-fullest-non-full-bucket algorithm. But if full, won't they all be able to send as many requests as they want to? No, it depends on how many are in flight... How many should be in flight? No idea. Seems we may need some simulations after all. Worthwhile specifying this as much as possible though, will make a start on the wiki after specing opennet. Another possibility would be to simply impose an arbitrary limit; we won't forward a request to a node unless it's in the top 2 or 3 choices for it. On Wed, Sep 27, 2006 at 05:01:40PM +0100, toad wrote: > TOKEN PASSING LOAD LIMITING > --------------------------- > > Each node has a maximum limit N on the number of running requests. > > Each node has a bucket for each of its peers, containing tokens. A token > is simply a UID; a counter which is incremented each time we create a > new token. The token is effectively a permit to send a request. A > request will include a token. If the token isn't recognized by the node > it sends back a specialized message indicating no such token. Otherwise > the node is required to accept it unless there is a serious problem > (such as looped requests). It then removes the token in question from > that node's allocation. Using UIDs for tokens prevents any race issues > that might otherwise happen. > > When nodes are first added, they are given some tokens. Tit-for-tat can > be implemented later on by scaling the maximum size of the token bucket > and biasing the decision on whom to give tokens to. When a request > completes, a new token is created an allocated to a node. There are two > obvious strategies for adding tokens: > - Reward requestors by adding to the least full bucket. > - Reward non-requestors by adding to the most full non-full bucket. > I prefer the latter option (it does impose some limits though; there > need to be enough tokens initially that a node not using its tokens > doesn't prevent everyone from requesting). Obviously we would use a > random tiebreaker in the case that two nodes have the same number of > tokens. > > What else remains? How do we integrate this with routing, that is the > remaining question. All we have to do here is keep requests in some sort > of pending state, and when we get a token from a node, send the request > most specialized for that node. This means we will have some misrouting, > but not much, and nodes which send us few tokens will get only the > requests closest to their specializations. We can perhaps improve on > this by "simulated queueing", but I don't see why the basic mechanism > shouldn't work, albeit at a slight latency cost. > > I'm rather inclined to implement this without waiting for simulations. > Any objections? > _______________________________________________ > Devl mailing list > Devl at freenetproject.org > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 189 bytes Desc: Digital signature URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20060927/d008afc8/attachment.pgp>
