Node-Weight Balancing Corrections

[Mike Perry]

Thus spake Mike Perry (mikeperry at fscked.org):

> > Case 2: Both Guards and Exits are scarce
> > 
> > If both exits and guards are scarce, we need to determine weightings
> > to distribute the Exit+Guard bandwidth evenly between the guard and
> > exit positions, and ignore the middle position. First, we should
> > consider some subcases.
> > 
> > Let R denote the more scarce class (Rare) between Guard vs Exit.
> > Let S denote the less scarce class.
> > 
> > Subcase b: R+D > S
> > 
> > For this case, we should divide D to make the two scarce classes
> > equal.
> > 
> > Using Case 1's General Form:
> > 
> >   Wgg*G + Wgd*D = M + Wmd*D + Wme*E + Wmg*G    (guard bw = middle bw)
> >   Wgg*G + Wgd*D = Wee*E + Wed*D                (guard bw = exit bw)
> >   Wed + Wmd + Wgd = 1                          (Wed*D+Wmd*D+Wgd*D = D)
> >   Wgg = 1-Wmg                                  (Wmg*G + Wgg*G = G)
> >   Wee = 1-Wme                                  (Wme*E + Wee*E = E)
> > 
> > We want guard bandwidth to equal exit bandwidth, and also:
> >    Wgg = Wee = 1 and Wme = Wmg = Wmd = 0.
> > 
> > Therefore, we know we want the following two equations to hold:
> >    1.   G +     Wgd*D = E + Wed*D     (guard bw = exit bw)
> >    2.   Wed*D + Wgd*D = D             (properly divide D)
> > 
> > Solving for Wed by adding 1+2:
> >     2*Wed*D + E + Wgd*D = G + Wgd*D + D
> >     2*Wed*D = G + D - E
> >     Wed = (G+D-E)/2D
> >     Wed = (G-E)/2D + 1/2
> > 
> > Solving for Wgd by rewriting 2 as Wgd=1-Wed:
> >     Wgd = 1-(G+D-E)/2D
> >     Wgd = (E+D-G)/2D
> >     Wgd = (E-G)/2D + 1/2
> > 
> > Here is a Mathematica line to verify this:
> > Reduce[{G + Wgd*D == E + Wed*D,
> >         Wed*D + Wgd*D == D},
> >        {Wed, Wgd}]
> 
> Here's a mathematica line to verify it from the General Form:
> Reduce[{Wgg*G + Wgd*D == Wee*E + Wed*D,
>         Wed*D + Wmd*D + Wgd*D == D,
>         Wgg == Wee, Wee == 1,
>         Wme == Wmd, Wmd == Wmg, Wme == 0,
>         Wmg*G + Wgg*G == G, Wme*E + Wee*E == E},
>         {Wgg, Wgd, Wmd, Wme, Wmg, Wee, Wed}]

While running the new consensus weight code on the current Tor
network, I've discovered that there is a subcase that Case 2b above
does not handle optimally. It turns out that if both G and E are
scarce, there still can be enough D bandwidth such that the above
result actually creates a scarcity in the middle position.

I am handling this subcase in the code by computing the above weightings
for Wgd and Wed, and then seeing if G+Wgd*D > M && E+Wed*D > M.

When this happens, we know that G+Wgd*D and E+Wed*D both exceed T/3
(because G+Wgd*D+E+Wed*D+M = T and G+Wgd*D = E+Wed*D).
 
Therefore, we can fix the Guard and Exit flagged nodes in their
position, because they are scarce (Wgg = Wee = 1 and Wmg = Wme = 0),
and add a new constraint similar to Case 3b:

 G+Wgd*D = T/3
 Wgd = (T/3-G)/D

In fact, since we know that there is sufficient bandwidth to balance
the network, we can cut right to the chase and say:

 M+Wmd*D = T/3
 Wmd = (T/3-M)/D

 E+Wed*D = T/3
 Wed = (T/3-E)/D

This can be verified in mathematica from the general form in case 1:
Reduce[{Wgg*G + Wgd*D == M + Wmd*D + Wme*E + Wmg*G,
        Wgg*G + Wgd*D == Wee*E + Wed*D,
        Wed*D + Wmd*D + Wgd*D == D,
        Wgg == 1, Wmg == 0, Wee == 1, Wme == 0,
        Wmg*G + Wgg*G == G, Wme*E + Wee*E == E},
        {Wgg, Wgd, Wmd, Wme, Wmg, Wee, Wed}]


Future work:

It has also occurred to me that while the above cases for balancing
the network attempt to conserve entropy in an ad-hoc fashion, there
are likely also entropy-maximizing constraints that would strike a
balance somehow between fixing Guard and Exit flagged nodes in their
place and allowing them to also be middle nodes in exchange for the
Guard+Exit nodes that could be either Guard or Exit.

For example, right now, in case 2b, Guard nodes will only be in the
Guard position, and Exit nodes will only be in the Exit position. The
other cases (except for case 1) have similar constraints on fixing one
of either the Guard or the Exit hop. This is less than ideal from an
entropy standpoint, but I'm not sure exactly how to frame
entropy-maximizing constraints into the general formula.


-- 
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/20100129/2d9797d2/attachment.pgp>