[Tech] Re: Backoff considered harmful?

[Michael Rogers]

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.

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.

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.

> 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