[tor-dev] Fairness between circuits

[Björn Scheuermann]

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


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