On Wed, Jun 21, 2006 at 01:29:08PM +0100, Michael Rogers wrote: > Matthew Toseland wrote: > >>* 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? > > They don't prevent the source from restarting the request, but they kill > the current incarnation. Isn't that how they currently work?
Not exactly. If the original source gets a RejectedOverload then it will slow down its send rate (but this only applies for the first one on a given request). If it doesn't over the whole request it speeds up slightly. If we get a timeout or a local RejectedOverload, then we backoff. And we retry after RejectedOverload, unless it's a timeout. This is not necessarily optimal! > > >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. > > If I understand your proposal correctly, it's equivalent to my proposal > with the addition of queues - in my proposal, requests that can't be > forwarded immediately are rejected; in yours they're queued, but the > size of the queue is limited. Sending a token in your proposal is > equivalent to incrementing the receiver window in mine; in both cases it > means "I'm ready to accept an additional request". So why do you need to keep the current insecure behaviour which requires the original sender to behave differently from every other node? A good token passing scheme ought not to need this, surely? Also your scheme differs in that your version is based on calculating rates rather than passing tokens from the specific node that is being routed to. Calculating rates adds extra complications relating to estimating in advance how many requests will be routed to each peer; this is bad IMHO. > > Regardless of whether we use queues, we can either give a token to some > deserving node whenever a request is forwarded or answered locally, or My preferred option; it is more precise, involves less alchemy, and is less likely to result in the network seizing up because of a temporary glitch. The metaphor is the flow of an incompressible fluid: one molecule goes forward on a particular pipe, which allows us to let one in on the incoming pipe. > work out the average rate at which requests are forwarded / answered > locally and hand out tokens at the average rate. So there seem to be > three separate questions: > > 1) Queues or no queues? Queues produce extra latency. However I don't see how we can, without gross misrouting, propagate token-for-token otherwise. > 2) Propagate exactly one token per request processed, or propagate an > average of n tokens per n requests processed? > 3) How do we choose a deserving node? > > I've argued both sides of (2) in the past, and to be honest I'm not sure > it matters much either way. (1) is probably more important, because > queueing increases latency but gives better throughput due to > statistical multiplexing. We have two proposals for (3): tokens overflow > to the emptiest bucket, and tokens overflow to the fullest non-full bucket. In order to achieve near perfect routing, I think we will have to propagate exactly one token incoming for every incoming request, from the node to which we have routed the request. Why? We could just add up all the tokens we receive from nodes we could send requests to, but this would suck, because: - We would get significant misrouting, especially if there is an ubernode. Or we would have to reject a lot of requests due to not being able to route them to where we should - after having asked for them! - Not every request can be routed to every node. This complicates calculations of rates if we go that way, and it also complicates token distribution if we just allocate every token which comes in to a potential request sender. We have to queue, and match an outgoing token to a queued request - i.e. an outgoing token to an incoming token. As far as rate calculations go, apart from the above problems, passing tokens directly allows us to respond instantly to network bottlenecks... I think on balance this is a good thing. Now, it would be nice to have the lowest possible latency, but only if this does not result in misrouting or poor load limiting. Note that the queue includes currently running requests which have actually been forwarded, in my proposal. Hence: (2): Propagate exactly one token, for reasons I just explained. (1): In order to propagate exactly one token, without breaking routing, we need to queue. (3): Simulate both, but we must throttle flooders. "Tokens overflow to the fullest non-full bucket" will throttle flooders at source - giving them fewer tokens than their non-flooding fellow peers - and it will propagate load back to the sender without the need for dangerous first-node-only behaviour in response to RejectedOverload's. The first node would not need any different machinery to any other node on the network. > > I'll write an applet to help us visualise these questions, but I'm going > out for dinner tonight so it won't be done till tomorrow. Something like > this: > > A--\ /--X > \ / > B----N----Y > / \ > C--/ \--Z > > For simplicity, traffic only flows one way. A, B, C send requests to N > at different average rates. Each request is either processed locally or > forwarded to X, Y, Z with different probabilities. X, Y, Z process > requests at different average rates. The applet shows the number of > tokens in each bucket, the number of requests in each queue (if > applicable), the average latency, and the throughput. Good idea. Looking forward to getting this sorted out. We have two drastic changes to the node core to go in this summer, both will require network resets; one is the load balancing rewrite (which I am very happy for you to implement as part of your SoC if you have time, but your primary responsibility is to simulate it and be sure it can work), the other is the changes to caching which Oskar tells me will be necessary. > > Cheers, > Michael -- 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/0885217a/attachment.pgp>
