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?
> 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".
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
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?
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.
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.
Cheers,
Michael
