Node-Weight Balancing Corrections

Mike Perry mikeperry at fscked.org
Thu Jan 28 02:30:24 UTC 2010


Since no one is likely to review this math except for me, I decided to
write mathematica commands to verify all the cases directly from the
General Form in Case 1. While doing this and writing the
implementation, I noticed one error, and a few edge cases. They are
documented below.

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 a: R+D <= S
> 
> For this case, we should simply devote all of D to the more scarce
> condition. This is because we don't have enough Exit+Guard bandwidth
> to make the more-scarce position have as much capacity as the
> less-scarce one.

For reference, this is: Wgg = Wee = 1; Wmg = Wme = Wmd = 0;

And then, if R=E: Wed = 1; Wgd = 0;
or if R=G: Wed = 0; Wgd = 1;

> 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}]

The result is the same, but since nobody will likely review this math
except me, its nice to have a full verification handy.

> Case 3: One of Exit or Guard is scarce
> 
> If only one of exits or guards are scarce, we want to proceed
> similarly as Case 2.
> 
> Let S be the scarce class.
> 
> This has two subcases:
> 
> Subcase a: S+D < T/3
> 
> In this case, we can simply treat D as the scarce class, and attempt
> to balance the load between the non-scarce class and the middle nodes.
> For simplification's sake, lets say S=G.
> 
> 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 then want Wgg = Wgd = 1 and Wmd = Wed = Wmg = 0.
> 
> We're now left with:
> 
>   G + D < M + Wme*E                            (guard bw < middle bw)
>   G + D < Wee*E                                (guard bw < exit bw)
>   M + Wme = Wee*E                              (middle bw = exit bw)
>   Wee = 1-Wme                                  (Wme*E + Wee*E = E)
> 
> Which is only two equations with two unknowns.
> 
> Solving for Wme:
> 
>   M + Wme = (1-Wme)*E
>   M + Wme = E - Wme*E   (Typo! Missed an E!)
>   Wme + Wme*E = E - M
>   (1+E)*Wme = E-M
>   Wme = (E-M)/(1+E)
> 
>   Wee = (1+E)/(1+E) - (E-M)/(1+E)
>   Wee = (1+M)/(1+E)
>   
> Here is a Mathematica line to verify this:
> Reduce[{M + Wme == Wee*E, Wee == 1-Wme}, {Wme, Wee}]

This was actually incorrect due to a typo in the second line. When I
wrote the mathematica reduce command to verify the entire derivation, I
got a different result. Here is that command:
Reduce[{M + Wmd*D + Wme*E + Wmg*G == Wee*E + Wed*D,
        Wed*D + Wmd*D + Wgd*D == D,
        Wgg == Wgd, Wgd == 1,
        Wmd == Wed, Wmd == Wmg, Wmg == 0,
        Wmg*G + Wgg*G == G, Wme*E + Wee*E == E},
        {Wgg, Wgd, Wmd, Wme, Wmg, Wee, Wed}]

Solving for Wme and Wee:

  M + Wme = (1-Wme)*E
  M + Wme*E = E - Wme*E   (Typo in original formula. Missed an E)
  2*Wme*E = E - M
  (2*E)*Wme = E-M
  Wme = (E-M)/(2E)
  Wee = 1-Wme
  
> Subcase b: S+D >= T/3
> 
> In this case, the formerly scarce class is no longer scarce, and now
> we have a condition that is similar to Case 1 with the exception that
> we want to change the D weighting from 1/3 for position S to whatever
> quantity brings it up to T/3. For simplification's sake, lets say S=G:
> 
>   G+Wgd*D = T/3                                (guard bw = T/3)
>   Wgd = (T/3-G)/D
> 
> 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 then want Wgg = 1 and Wmg = 0.
> 
> We can then evenly divide D between middle and exit positions:
> 
>   Wed = Wmd
> 
> We're now left with:
> 
>   G + Wgd*D = M + Wed*D + Wme*E
>   G + Wgd*D = (1-Wme)*E + Wed*D
>   2*Wed*D + Wgd*D = D
>   Wgd = (T/3-G)/D
> 
> This gives:
>  
>   Wed = 1/2 - (T/3-G)/2D
>   Wme = (E-M)/2E
> 
> Here is a Mathematica line to verify this:
> Reduce[{G + Wgd*D == M + Wed*D + Wme*E,
>         G + Wgd*D == (1-Wme)*E + Wed*D,
>         2*Wed*D + Wgd*D == D,
>         Wgd == (T/3-G)/D,
>         T == G + M + E + D},
>         {Wed, Wme, Wgd}]

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, Wed == Wmd,
        Wmg*G + Wgg*G == G, Wme*E + Wee*E == E},
        {Wgg, Wgd, Wmd, Wme, Wmg, Wee, Wed}]

Result is the same.
 
> Implementation Notes:

When D is 0, the denominator of some of those equations is zero. In
those cases, simply setting the Wxd weights to zero is acceptable,
since there is no D bandwidth to distribute. 

There are also edge cases when E < M or G < M in Case 3a and 3b, which
leads to a negative result. In those cases, setting Wme or Wmg to 0 is
fine, because we do not want to devote any bandwidth to an already
large middle position capacity.



-- 
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/20100127/e4144456/attachment.pgp>


More information about the tor-dev mailing list