[Tech] Re: Backoff considered harmful?

[toad]

On Tue, Nov 28, 2006 at 01:10:18PM +0000, Michael Rogers wrote:
> Jano wrote:
> >Is token passing explained somewhere in the wiki? From your conversation it
> >sounds like a mechanism where one issues "tickets" to neighbors, where each
> >ticket means "you can make a request from me".
> 
> Exactly - it's not documented yet I'm afraid, but see the discussions on 
> freenet-dev in March of this year.
> 
> On the output side, we keep a queue and a counter for each peer. When a 
> peer sends us a token, we send it the first search in its queue, or if 
> the queue's empty we increment the counter. When we want to send a 
> search to a peer, if the counter's at zero we add the search to the 
> queue; otherwise we send the search and decrement the counter. (A search 
> can be an insert or a request.)
> 
> In future we might consider 'misrouting' searches: if we don't have 
> tokens for the peer that ought to receive a search but we have tokens 
> for some other peer, send the search to the other peer. But we need to 
> work out how to avoid redirecting all traffic to whichever peer has 
> spare capacity, which is bad for two reasons: searches take more hops to 
> reach their destinations, and an attacker with a fast node can attract a 
> large amount of traffic (for monitoring, filtering, etc). Toad has 
> suggested not allowing any peer to handle more than (eg) twice the 
> median number of searches, which would enable us to route around a few 
> slow peers without redirecting too much traffic to fast peers.

An important corrolary is that we would have a global queue, and slow
nodes would get not only fewer requests than fast nodes, but also
requests that were *closer to their specializations*.
> 
> On the input side, we start with a certain number of tokens to hand out. 
> Let's say we divide them evenly among our peers to start with. The 
> number of searches in progress at any time is limited by the number of 
> tokens; whenever a search completes (either by getting a response or by 
> timing out), we hand out another token. (I have a feeling we should wait 
> before handing out a token if the search timed out, but I'm not sure yet.)
> 
> The question is, which peer gets the token? My proposal is to give the 
> token to a random peer, or if that peer already has its fair share of 
> tokens, give the token to whichever peer has the fewest. This is called 
> emptiest-bucket-first; the idea is to enforce fairness when resources 
> are scarce, but allow peers to use more than their fair share when there 
> are excess resources.

How does this enforce fairness? A useful mechanism would prevent and/or
contain flooding.
> 
> Toad's proposal is to give the token to a random peer, or if that peer 
> already has its fair share of tokens, give the token to whichever peer 
> out of those with less than their fair share has the most. This is 
> called fullest-non-full-bucket-first, and the idea is to reward peers 
> that send fewer searches.
> 
> I'll also explore some other possibilities, like giving the token to the 
> peer whose request just completed, and giving the token to a random peer 
> regardless.

Cool.
> 
> >About successful requests being returned: how they are currently dealt 
> >with,
> >bandwidth-wise?
> 
> All messages are subject to congestion control and bandwidth limiting, 
> but it's only searches that need flow control tokens.
> 
> Cheers,
> Michael
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://emu.freenetproject.org/pipermail/tech/attachments/20061128/f6edb9de/attachment.pgp