I agree with most of Björn's post, but disagree slightly here:
On Thu, May 12, 2011 at 10:54:06AM +0200, Björn Scheuermann wrote:
- The priority-queue-based circuit scheduling code originally
merged in Tor 0.2.2.7-alpha (starting with commit d3be00e0f).
We expect that if the bandwidth allocation to circuits is fair right from the start, the problem addessed there will no longer exist. To put it short: this mechanism is kind of a "hotfix" addressing the "symptoms", we aim to cure the root cause. :)
It might, at some point in the future, be wise to assess whether this expectation is true or whether we missed an important effect. If really necessary, then it will be easy to implement something similar in combination with our fairness mechanism. For my part, I would really like to avoid this, though - not because I don't like the mechanism, but because I firmly believe that the best solution is the simplest good solution. That is: the aim should be to get rid of the problems *and* of the high complexity of the current design.
The EWMA stuff isn't _trying_ to be fair; it's explicitly trying to prioritize circuits for which users will gain utility from lower latency, and deprioritize circuits for which users don't care about latency. That said, it's still kind of fair, as circuits with similar usage patterns will get similar service.
The main difference is that if you've got a bunch of circuits that need servicing, a fair round-robin doesn't care if you service them in the order A,B,C,D,E,A,B,C,D,E or E,B,A,C,D,E,B,A,C,D, or even E,B,D,A,C,A,E,B,C,D. All are equally fair. The observation in our CCS paper is that it _does_ matter to the user, if some of the circuits are interactive, and others are not. Indeed, if A is interactive and hasn't sent packets in a while, it might get A,A,A,C,E,B,D so that it can "catch up".
- Ian