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

[Roger Dingledine]

On Mon, Jun 04, 2007 at 08:15:00PM -0400, nickm at seul.org wrote:
>    tor/trunk/src/or/routerlist.c
>  When choosing a guard, weight by bandwidth.  Resolves bug 440.

Hi Nick, Mike, folks,

I'm still not convinced that this is the best fix.

A recap for those following along at home:
http://bugs.noreply.org/flyspray/index.php?do=details&id=440
The issue is that Tor clients were weighting every node that qualified
as a guard equally when choosing a new entry guard. So the guards that
had 60KB/s of bandwidth were getting as much action as the ones that had
600KB/s of bandwidth. This meant that the "low end" guards were getting
hammered harder than they should be.

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

Nick chose approach "A" in his patch.

Approach A has the downside that if the bandwidths change dramatically
over time, we can't adapt. In this case, a whole lot of clients would
list the once-600KB/s-but-now-slow server in their guard lists, and it
would get more attention than it should.

Approach B adapts better to changes in guard bandwidth, but it has the
downside that if we're only picking a few guards uniformly at random, we
probably won't get the fast ones, so even if we load balance well over the
ones we've got we're still not going to produce globally good behavior.

Note that none of these options are *really* bad, because if a node
loses its guard flag then we stop using it as a guard. So nodes can't
get *really* crummy here; just sort of crummy.

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.

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?

--Roger