Hi all,
my group and I have recently been working on the question whether multiple circuits in Tor share the available bandwidth fairly and reasonably. What we found is: they don't. Not at all.
First, we developed an analytical model for the fairness between circuits in an anonymity overlay, and thought about how to define fairness in a setting like Tor: when can the bandwidth sharing between many circuits in a complex anonymity overlay with varying available router bandwidth be called "fair"? In short: an adaptation of the max-min fairness concept does a very good job here.
In order to overcome the existing fairness problems in Tor, we also developed a (surprisingly simple) mechanism which achieves max-min fairness without exchanging any additional data about the circuits between onion routers - the latter is clearly a nice trait with respect to privacy. We found that this approach goes very well with the recently proposed N23 congestion feedback scheme from the guys at Waterloo/Colorado/San Diego.
We implemented Tor's scheduling mechanisms, the N23 extension, and our fairness mechanism in an event-based network simulator (ns-3). Independent from the question of inter-circuit fairness, we were able to confirm the key findings in the DefenestraTor tech report with respect to N23 based on this independent implementation. Moreover, we found that N23 does not solve the fundamental fairness problems - but N23 in combination with our fairness mechanism does an excellent job in this regard.
We explain all this in much more detail in a paper:
F. Tschorsch, B. Scheuermann: Tor is Unfair - and What to Do About It http://robotik.informatik.uni-wuerzburg.de/tr481.pdf
We're hoping for feedback and vivid discussions - we would be really interested in bringing these mechanisms into Tor.
Best regards
Björn
2011/5/6 Björn Scheuermann scheuermann@informatik.uni-wuerzburg.de: [...]
We implemented Tor's scheduling mechanisms, the N23 extension, and our fairness mechanism in an event-based network simulator (ns-3). Independent from the question of inter-circuit fairness, we were able to confirm the key findings in the DefenestraTor tech report with respect to N23 based on this independent implementation. Moreover, we found that N23 does not solve the fundamental fairness problems - but N23 in combination with our fairness mechanism does an excellent job in this regard.
We explain all this in much more detail in a paper:
F. Tschorsch, B. Scheuermann: Tor is Unfair - and What to Do About It http://robotik.informatik.uni-wuerzburg.de/tr481.pdf
We're hoping for feedback and vivid discussions - we would be really interested in bringing these mechanisms into Tor.
Hi! Let me kick the discussion off by asking how your work relates (if at all!) to:
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.)
2) The priority-queue-based circuit scheduling code originally merged in Tor 0.2.2.7-alpha (starting with commit d3be00e0f).
3) Your other scheduling/bandwidth allocation work (ticket 2536)
I'd also be interested in hearing what the DefenestraTor authors think about above-linked paper and the topic in general.
yrs,
Hi Nick,
thanks for the feedback!
- 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.
- 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.
- 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
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
Hi,
I agree with most of Björn's post, but disagree slightly here:
I fully agree with what Ian said, except for one point. ;)
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".
I think this is also a question of the time scale. If the queues are excessively long due to non-working congestion control as in current Tor, then this is certainly an issue - because you can save significant time by scheduling in the right order. If the queues are short and scheduling is more fine-grained than now, then the minimal resulting time differences will not matter.
As I said in my previous mail, it is still conceivable to implement something along similar lines with our proposal. In the end, this would mean the introduction of (short-term) unfairness in order to give a (short-term) advantage to interactive traffic. This can be done without hurting the long-term fairness between circuits. However, it would increase the complexity, and thus significantly reduces our chances to understand what happens and why it happens.
It may well turn out that this is beneficial - this remains to be assessed at some point further down the road. For the moment, my guts tell me that the problem will not exist to the same extent. My guts might be wrong with that, and we should verify that once the ideas have become a bit more stable. If I am right, however, we should IMHO seize the opportunity to reduce the system complexity if it doesn't hurt performance.
Best regards
Björn
-
Björn Scheuermann -
Ian Goldberg -
Nick Mathewson