On Tue, Jun 20, 2006 at 09:27:43PM -0700, Ian Clarke wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > Still thinking about this - but is there any place here for the > "minimum request interval" mechanism we used in 0.5?
This supercedes the minimum request interval mechanism, by passing tokens rather than trying to determine rates. It's better - it's more precise, it reacts more accurately as well as faster. It more accurately simulates the underlying metaphor or incompressible fluid flow in a network of pipes. > > Ian. > > On 20 Jun 2006, at 17:24, Matthew Toseland wrote: > > >On Wed, Jun 21, 2006 at 12:02:45AM +0100, Michael Rogers wrote: > >>-----BEGIN PGP SIGNED MESSAGE----- > >>Hash: SHA1 > >> > >>Matthew Toseland wrote: > >>>I don't understand what you mean when you talk about token > >>>schemes. We > >>>can certainly tell our peers how many requests they can send - > >>>but so > >>>what? How does this limit load? > >> > >>We tell a peer when its bucket is empty, and it stops sending > >>requests. > >>This is more efficient than waiting for a request we know we'll > >>reject > >>anyway, then rejecting it. (But we can fall back to that if the peer > >>isn't well behaved or the messages cross on the wire.) > >> > >>>I don't see how you are propagating them either. > >> > >>There are two answers to this, depending on what you mean by > >>propagating. I've got the impression from earlier discussions that > >>you > >>mean asking the source to slow down. If that's the case then > >>here's how > >>we propagate load: > >> > >>* A peer would like to send us a request > >>* There are no tokens left in its bucket (and we've told it so) > >>* Being unable to forward the request, it has to reject it > >>* The RejectedOverload travels back to the source > > > >So let me get this straight, RejectedOverload's kill the request? > > > >>* The source slows down > > > >Okay, so the token mechanism will limit flooding; a node which spams > >requests will not receive any more tokens than any other node, and > >therefore will not be able to send more requests than any other. > > > >However, you don't solve the fundamental problem with the currently > >implemented mechanism in Freenet 0.7. Which is that we require the > >original sender to slow down in response to RejectedOverload's - > >and we > >do not require any similar reaction from any other node. This means > >that > >at a network level it may be possible to distinguish between the > >original sender and any other node - which is BAD! 0.5 did not have > >this > >vulnerability. > >> > >>On the other hand, if by 'propagating' you mean calculating how many > >>tokens to give our peers on the basis of how many tokens our peers > >>have > >>given us, here's what I'd suggest: > >> > >>* Calculate the ratio of incoming to outgoing requests (running > >>average) > >>* Work out how many requests our peers are willing to accept, in > >>total > >>* This tells us how many requests we can accept, in total > >>* Divide these requests among our peers (eg give each bucket the same > >>number of tokens, with full buckets overflowing into the fullest > >>non-full bucket) > > > >This will produce misrouting. Our nodes' locations are not necessarily > >at any given moment distributed precisely evenly across the > >keyspace. We > >have to take this fact into account. And we can't assume that we > >receive > >requests distributed randomly across the keyspace either. > > > >So we have to track what proportion of incoming (or local) requests go > >to each node. How we produce an overall number then depends on how we > >handle misrouting. > > > >We could just add up the raw numbers for possible queries relayed > >to each > >node, but this is unacceptable: If we have an ubernode, we would > >end up > >accepting far more requests than we can handle without serious > >misrouting > >(i.e. forwarding them all to the ubernode). > > > >An option that would minimize misrouting: > > > >total = min_over_all_nodes > > ( node capacity / node fraction of routing requests ) > > > >Obviously the problem here is that while it would eliminate > >misrouting, > >at least in theory, it would also be extremely vulnerable to slow > >nodes. > >So perhaps excluding the slowest few nodes would help. > > > >However, there is another option. We don't have to do this sort of > >calculations, we can simply pass the tokens on directly: > > > >Propagate the tokens, and queue. > > > >Each node has, for incoming requests: > >- A token bucket. > >- A bunch of queued or active requests, size not exceeding the current > > value of the token bucket. > > > >Every time the token bucket size changes for a node, we send a message > >to the node indicating the new size, probably piggybacked on some > >related message. > > > >When we answer a request from the store, or a request otherwise > >terminates locally, we create a token and give it to a deserving > >node's > >token bucket. If the chosen node is not the same as the node whose > >request just completed, its token bucket is reduced by 1 at the same > >time as the running request is removed from its queue. > > > >We match queued requests with output nodes: When we receive a token > >from > >a potential output node, we check whether there are any queued > >requests > >who would like to be sent to that node. If there are, we pick one, and > >forward it. Likewise if we have a surplus of tokens for a node and we > >receive a request which would like to be sent to that node, we forward > >it to that node. > > > >Requests are normally forwarded to their first choice. However, the > >first choice may change as nodes go offline etc. Misrouting can be > >introduced at this point: If the first choice node is significantly > >slower than the median, we can allow most requests that would go to > >that > >node to be sent to the second choice - perhaps by some simple > >probabilistic scheme. Alternatively we can simply exclude really slow > >nodes from routing, but that would suck. > > > >Note that the first choice is dependant on the request history as well > >as the location; the node it comes from, the nodes it has been to, and > >so on, affect the choice of next hop. > > > > > >Now, how does this limit load? > > > >Firstly, we will never start requests faster than we can physically > >handle them, except during the early bootstrapping phase. Nodes should > >limit themselves rather nicely on bandwidth. Timeouts would > >generally be > >due to bugs, transient network failures and so on. Since timeouts > >take a > >long time, by definition, if timeouts are happening due to load > >then very > >few requests are being started; so the system should balance itself. > >-- > >Matthew J Toseland - toad at amphibian.dyndns.org > >Freenet Project Official Codemonkey - http://freenetproject.org/ > >ICTHUS - Nothing is impossible. Our Boss says so. > >_______________________________________________ > >Devl mailing list > >Devl at freenetproject.org > >http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl > > -----BEGIN PGP SIGNATURE----- > Version: GnuPG v1.4.2.2 (Darwin) > > iD8DBQFEmMrCQtgxRWSmsqwRAhzsAKCAJs0+OYVeIDaV2vMSSBscwBxKHgCfafLr > pL/215FaPnjfGVHGqWDT1ok= > =QgRV > -----END PGP SIGNATURE----- > _______________________________________________ > Devl mailing list > Devl at freenetproject.org > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl > -- Matthew J Toseland - toad at amphibian.dyndns.org Freenet Project Official Codemonkey - http://freenetproject.org/ ICTHUS - Nothing is impossible. Our Boss says so. -------------- 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/20060621/83a181dc/attachment.pgp>
