On Wed, Jun 21, 2006 at 04:39:52PM +0100, Michael Rogers wrote: > Matthew Toseland wrote: > >And we retry after RejectedOverload, unless it's a timeout. > > OK, last question: is it the original source that retries, or does each > node in the chain retry until the next node accepts the request?
IIRC each node on the chain - at a cost of 1 HTL. But we can change this, we're making drastic enough changes as it is! :) > > >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? > > I'd prefer to do without it, but we might need it if backpressure > doesn't work as well as we hope. Well that's something for simulations. > > >Calculating rates adds extra complications relating to > >estimating in advance how many requests will be routed to each peer; > >this is bad IMHO. > > OK, let's use the one-out-one-in approach. Okay cool. > > >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. > > Nice. :-) :) I just got this yesterday... > > >>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. > > I think we might be able do it by storing tokens rather than storing > requests: if each node has a reasonably large pool of tokens, it should > be able to accommodate a burst of traffic without rejecting any > requests. Instead of the queues getting full, the buckets get empty. Without misrouting? > > >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. > > But once we've propagated a token to someone, we can't control which key > they request using that token, can we? That's why we queue requests! We allocate a token to somebody. That allows them to send us a request. Then the request remains queued until it either completes or times out. While it is queued, and not forwarded yet, it can be matched to a node which has given us a token. This destroys that token. When it completes, even if it completes from the store, or times out even, we create a new token and give it to a deserving node - and remove the token we locked for this request. > > >- 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. > > OK, so the number of tokens we give out should be based on the number we > actually use, not the number we're given. That way if we're given a lot > of unusable tokens (eg from a fast peer that's responsible for a small > region of the keyspace) we won't accept more requests than we can > actually forward. Right. When we receive a token, we try to match it with a queued request, in my scheme. If we can, we forward that request. But we don't create a new token (request a new request) until a request actually completes - and we create one even if the request is never forwarded. > > >We have to queue, and match an outgoing token to a queued request - i.e. > >an outgoing token to an incoming token. > > I think maybe we should match an outgoing token to a completed request - > not all incoming tokens are usable. Okay, that's more or less the idea; we assign a token to a node when we complete a request. But we match an outgoing token from a node to a request which *should be routed to that specific node*. This minimizes misrouting. However it does incur extra latency, and if you have a better idea which has identical or better misrouting behaviour, then I'll go with that. Thanks! > > As for misrouting, I'll make my suggestion in a separate thread. :-) > > 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/db4b89dd/attachment.pgp>
