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.
-------------- 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/644a178b/attachment.pgp>
