Hi Matthew, Let me just make sure I've got this straight before I start writing code.
My proposal: 1) Keep track of the number of tokens available for each incoming and outgoing link 2) When a request is received, decrement the number of tokens available for the incoming link - if already zero, reject the request 3) When a request is forwarded or answered locally, generate a token and give it to a deserving incoming link 4) If a request can't be forwarded due to lack of tokens on the outgoing link, reject the request and don't generate a token 5) If a request can't be forwarded due to the bandwidth limiter, reject the request and don't generate a token Your proposal: 1) Keep track of the number of tokens available for each incoming and outgoing link 2) When a request is received, decrement the number of tokens available for the incoming link - if already zero, reject the request 3) When a request is forwarded, answered locally, or times out, generate a token and give it to a deserving incoming link 4) If a request can't be forwarded due to lack of tokens on the outgoing link, queue the request - the queue size is automatically limited by (2) 5) If a request can't be forwarded due to the bandwidth limiter, should it be rejected or queued? 6) When a token is received, if there are any requests queued for that outgoing link, send the first one For the moment let's assume no misrouting in either proposal. In my proposal, tokens are generated at the rate at which requests can be served (forwarded or answered locally). However, this rate can change due to peers connecting and disconnecting, congestion, CPU load, etc, so it's occasionally necessary to probe for available capacity. This can be done by spontaneously generating a token and giving it to a deserving incoming link. In equilibrium, the number of rejected requests will equal the number of spontaneously generated tokens, so there's a tradeoff between rejecting too many requests and failing to use available capacity. In your proposal, tokens seem to be generated at a constant rate (in the long term), because you eventually generate one token for each request you accept, regardless of its fate. It seems like this might not control load unless the source responds to rejections by slowing down, which has its own problems. So I'd like to suggest a third scheme, which is a hybrid of the first two: queue requests that can't be forwarded immediately, but don't generate tokens for requests that time out. Instead, spontaneously generate a token once in a while to probe for available capacity. What do you reckon? Michael
