Exit Balancing Patch

[Mike Perry]

Thus spake coderman (coderman at gmail.com):

> (also, there are only 32 nodes that are getting clipped right now at
> 1.5, so i don't see raising to 10 giving much improvement.)

[Appologies, I have to take this unintentional flamebait and go on an
extended rant. Tor performance is in my mind a very important subset
of Tor security].

It turns out this clip cuts off the load balancing of approximately
23MB/sec (as in 23MB/sec is chopped off above the 1.5MByte), or about
10% of the total network bandwidth.. This is just one part of the
balancing problem, but I see no reason not to fix it. Not fixing it
just makes it harder to find other balancing issues.


Currently, there is a LOT of unused bandwidth in the top 15% of the
nodes in the network due to load balancing issues. I've prepared some
charts for my Defcon talk to illustrate this imbalancing. 

http://fscked.org/transient/torgraphs/

The bandwidth data was gathered by dividing the network into
5-percentile slices of about 79 nodes each and fetching a 512k file
through 2 hops each chosen from the same percentile range. The circuit
failure and extend time data were gathered by fetching an approx 20k
file over 3 hop paths chosen similarly. 

Average stream capacity for the bottom 85% of the nodes on network is
about 10KB/sec per stream. However, average capacity for the top 5% of
the network is over 70KB/sec per stream.

http://fscked.org/transient/torgraphs/StreamBwBar.pdf

This means the top 5% of the network can support SEVEN TIMES AS MANY
USERS as it currently does. The top 5% of the network carries 45% of
the Tor network traffic.

The next 10% (percentiles 5-15) can support 3 times as many users.
Together, they carry 30% of the network traffic.

Note also the rising rate of circuit failures and extend times, until
you hit the magic 50% threshhold where nodes stop being considered for
unbalanced guard status.

http://fscked.org/transient/torgraphs/ExtendsBar.pdf
http://fscked.org/transient/torgraphs/CircFailure.pdf


The fact of the matter is is that Tor is NOT EVEN CLOSE TO SAFE as a
whistleblower's network until it attracts more users. With so few Tor
users, it is trivial to find the only Tor user in an institution or
location who used Tor to report wrongdoing, post evidence, or contact
the media.

I think this problem is serious enough to treat it a security issue
that warrants both fixing this issue immediately, as well as expiring
all guards that have been chosen uniformly by Tor versions prior to
0.1.2.15. Additionally, we should consider changing bandwidth
reporting in rep_hist_bandwidth_assess() to report average observed
bandwidths instead of peaks, to more smoothly handle nodes whose
capacities are highly volatile (such as my own).


For entertainment's sake, lets do a quick back of the envelope
calculation to see what a balanced network would get us. Lets say that
there are 200,000 Tor users currently. A balanced network should be
able to support 200000*.45*7 + 200000*.30*3 + 200000*.25=860,000 Tor
users at average stream bandwidths of 10KB/sec USING THE SAME NETWORK.

Granted, latency is likely also be a major factor in perceived
performance, requiring intelligent path selection and optionally
shorter path lengths; and as Steven Murdoch pointed out on or-talk,
there may not be 860k users who will put up with 10KB/sec stream
speeds, but that just means the new equilibrium stream bandwidth will
be that much faster for the whole network (instead of randomly fast
or randomly unbearable, as is the case today).



-- 
Mike Perry
Mad Computer Scientist
fscked.org evil labs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20070726/aea8c367/attachment.pgp>