[or-cvs] r10493: When choosing a guard, weight by bandwidth. Resolves bug 440 (in tor/trunk: . src/or)

[Mike Perry]

Thus spake Roger Dingledine (arma at mit.edu):

> I'm still not convinced that this is the best fix.
> 
> There are two places that we might want to fix:
> 
> A) When choosing a new entry guard, weight the options by bandwidth.
> So we are ten times more likely to add the 600KB/s guard than the 60KB/s
> guard to our guard list. But when building a circuit, choose a guard
> uniformly from our list.
> 
> B) When adding a new guard, choose uniformly. But when choosing which
> guard to use for a given circuit, weight each choice in our guard list
> by its current bandwidth. So if one guard is 600KB/s right now and the
> other is 60KB/s, we're ten times more likely to pick the first for a
> given circuit.
> 
> (My first thought was that we should apply both approaches. But this
> would be bad, because assuming the bandwidths are still the same as
> they were when we first picked the guards, the slow ones will end up
> being under-used in each given circuit (1/100 as often rather than 1/10
> as often -- assuming we picked both the slow and the fast).
> 
> Note also that Mike's hopes for current users to upgrade and suddenly
> help the global load balancing won't work in approach A, since people
> will still use their old (uniformly chosen) lists. It will only gradually
> solve itself as new users join and as old guards lose their guard status
> entirely

Ah shucks.. Forgot about this. Can we put some code to make users
re-choose guards for this upgrade? Or perhaps a general mechanism so
that we can decide in the future to expire guard selections chosen by 
a tor older than some given version?

It's not so much of a problem for mobile, transient and dialup users..
They get disconnected enough that the current guard selection stuff is
always picking new ones.. But perhaps we want to change this too.
Probably should, at some point... somehow..

Also, this brings up the point that older guard nodes are going to
tend to have more load than newer ones.. This is by design, but it may
get serious enough that really old nodes actually begin to suffer
reliability/congestion issues as a result, and may not be as stable as
their uptime would otherwise indicate? I suppose I can measure this
with speedracer at some point, but I think that the current balancing 
issue is going to mess with any runs I try to do..

> If I had to choose right now, I'd pick approach A, because at least it
> starts out being globally good, even if it degrades over time.
> 
> Anybody have a more creative option?

What about using the square root of the bandwidths for weighting for
guards? Then we could implement approach B by weighting based on this
value twice? 


-- 
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/20070612/dbd7d502/attachment.pgp>