[tor-dev] Fairness between circuits

[Ian Goldberg]

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:
> >   2) 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