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
