[tor-dev] Fairness between circuits

[Björn Scheuermann]

Hi Nick,

thanks for the feedback!

>   1) This other work on using N23 with Tor ("DefenstraTor: Throwing
> out Windows in Tor" by AlSabah, Bauer, Goldberg, Grunwald, McCoy,
> Savage, and Voelker):
>        http://www.cacr.math.uwaterloo.ca/techreports/2011/cacr2011-06.pdf
>       (IMO it's a promising sign that two groups seem to be
> independently converging on the same basic algorithm family.)

Actually, it's not independent. 

I should maybe give a bit more context here. Fairness is very closely
related to congestion control - in fact, both aspects can hardly be
separated at all in practice. When thinking about fairness and
congestion control, there's basically two (closely interrelated) key
questions to answer: 1) how to provide feedback on whether the source
should send less/more, and 2) how to determine which user is allowed to
send how much. The latter is the fairness aspect.

In order to tackle Tor's congestion problems, we started from the
fairness "side" some time ago - and, as we believe, we found a nice
solution. Such a solution doesn't help much, though, if you don't have a
feedback mechanism to throttle the sources accordingly - just like a
feedback mechanism without reasonable fairness properties is just half
as much fun.

When we saw the DefenestraTor paper, we noticed that the feedback
mechanism they proposed - using N23 from ATM in Tor - is in fact a very
nice "counterpart" to our fairness mechanism. So, "their" N23 is the
same as "our" N23 - we contribute the other "half", the fairness side.

More details on the interrelation are described in our paper.

>   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.

>   3) Your other scheduling/bandwidth allocation work (ticket 2536)

This addresses a different problem. Ticket 2536 is concerned with the
bandwidth management "within" one OR - don't read more than you are
allowed to write within a reasonable time frame. The fairness tech
report looks at it from the perspective of the network as a whole. It
addresses the question which circuit should receive which share of the
overlay's resources so that no user can gain an unfair advantage.

When, at some point, the fairness mechanisms get closer towards
deployment, it would of course be advisable to have a closer look at the
combination of these mechanisms and their interplay. After all, they
require modifications in similar parts of the code. But I don't think
that it is necessary (or particularly helpful) to do so now, due to the
different time frame: the time horizon for 2536 is certainly much
shorter than that for our fairness proposal and/or N23, because 2536 is
far less "intrusive".


Cheers

Björn


-- 
Prof. Dr. Björn Scheuermann
Chair of Computer Science VII
University of Würzburg
Am Hubland, 97074 Würzburg, Germany

Tel.: +49 931 31 85402
scheuermann at informatik.uni-wuerzburg.de
http://www7.informatik.uni-wuerzburg.de