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: signature.asc Type: application/pgp-signature Size: 189 bytes Desc: Digital signature URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20061128/f6edb9de/attachment.pgp>
