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