Node-Weight Balancing Corrections

[Nick Mathewson]

On Wed, Jan 20, 2010 at 7:17 PM, Mike Perry <mikeperry at fscked.org> wrote:
> For purposes of load balancing, exit and guard node node bandwidths
> are weighted by fractional values when they are probabilistically
> selected for circuit positions other than their primary purpose. This
> done is to govern scarcity and properly distribute load amongst the
> node classes.
 [...]
> The current smartlist_choose_by_bandwidth() calculates Guard, Exit,
> and Total bandwidth based on the smartlist passed in, which has
> already been restricted to viable nodes. We'll need to refactor this
> function to receive G, E, M, D and T as parameters independent of the
> current node selection list, which is a local position property
> independent from the global capacity and balance of the network.
>
> Furthermore, even these weights are approximate, because in actual
> operation not all Exit nodes are equal. In fact, some nodes lack an
> Exit flag, but still contribute Exit bandwidth for certain ports. We
> could envision dividing the classes such that E and D are counted only
> for the current exit port instead of purely based on flag, but this is
> not always known at time of circuit construction.
>
> The implementation should verify that the total weighted bandwidth
> available to each position is properly balanced according to the
> current scarcity case of the network. This will be difficult to do in
> a unit test, but there should be debug ifdefs on non-release Tors to
> check these conditions on the current consensus during selection.

Nice. Your reasoning seems correct, though I haven't doublechecked your math.

For implementation, I'm wondering if we can't push the complexity to
the authority side and have clients look at a parameter or set of
per-router values derived by the authorities, so that if we want to
change the weighting algorithm even more in the  future we can.

For unit testing, it probably makes sense to split the function into
two parts, one of which calculates node weights, and one of which
picks nodes by weight?  This should be good enough to confirm that our
code really does as specified.  To confirm that the spec is correct,
I'd think it would be smarter to write a simulation script to see how
the specified load balancing works in practice.

Also, once we've finalized the formulas here, they should all go into
path-spec.txt .

peace,
-- 
Nick