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

[Lasse Øverlier]

Hi Roger,

I think approach A looks like the best option, but what about adding an
"EntryGuardBandwidth" in /var/lib/tor/state with the bandwidth the node
announced when chosen? This way a significant change in bandwidth can be
detected and the user may be warned/informed that (s)he can consider
"re-selecting" Entry Guards?

Just an idea...


 - Lasse

Roger Dingledine wrote:
> 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
>