Node-Weight Balancing Corrections

[Mike Perry]

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

> Future Work:
>  [Node weight balancing case updates].

In my git branch of the implementation (in
mikeperry/consensus-bw-weights3), I've included some additional but
currently unused weights for weighting directory server traffic in
future consensus methods.

There are 8 new weights for this:

  Wgb - Weight for BEGIN_DIR-supporting Guard-flagged nodes
  Wmb - Weight for BEGIN_DIR-supporting non-flagged nodes
  Web - Weight for BEGIN_DIR-supporting Exit-flagged nodes
  Wdb - Weight for BEGIN_DIR-supporting Guard+Exit-flagged nodes

  Wbg - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
  Wbm - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
  Wbe - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
  Wbd - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests

The first four weights are currently set to 1.0 by the current consensus
process, and the last four are set to their Wm* equivalents (to treat
directory requests as middle traffic).

However, we can use them in the future by changing the weight
calculation into a two step process:

First, calculate G, M, E, D, and T by reducing the bandwidth of nodes
with dir_port != 0 by the average dirport traffic consumption
percentage that Karsten measures as part of his statistics gathering.
This reduction is represented in the Wgb, Wmb, Web, and Wdb weights,
and these would be set to his measured hardcoded values before the G,
M, E, D and T computation for purposes of doing this computation.

If this places us into a scarcity case that prevents network balancing
(such as Case 2a or 3a), we recompute G, M, E, D, and T without
reducing the bandwidths of dirport enabled nodes for the scarce class
by setting its corresponding weight to 0, and then adjust the above
weights accordingly to compensate for this.


For example, if Exits are scarce, and we know that dirport traffic
takes up approximately (1-Wgb) of Guard, (1-Wmb) of Middle, (1-Web) of
Exit, and (1-Wdb) of Dual dirport bandwidth on average from Karsten's
measurements, we know that the total dirport (BEGIN_DIR) traffic is
then:

   (1-Wgb)*Gb + (1-Wmb)*Mb + (1-Web)*Eb + (1-Wdb)*Db = B

Where Gb, Mb, Eb, and Db are the total bandwidth of Guard, Middle,
Exit, and Dual flagged nodes that ALSO have their dir_port != 0.

If we then set Web=0 and Wdb=0 to shift dirport traffic away from our
scarce Exit-capable nodes, we need to come up with a delta weight w to
add to the other two weights:

   (1-(Wgb+w))*Gb + (1-(Wmb+w))*Mb = B

Solving for w:

   w =  (-B + Gb + Mb - Gb*Wgb - Mb*Wmb)/(Gb + Mb)

We then update Wgb and Wmb with this w to distribute the former Exit
and Dual-flagged dirport traffic among them, and then recompute G, M,
E, D, and T, determine the new scarcity case, and then compute the 7
original weights from the previous post as normal.

We then also publish:

  Wbg = Wbm = 1.0
  Wbe = Wbd = 0 

Along with:

  Web = Wdb = 1.0
  Wgb = Wgb_measured + w
  Wmb = Wmb_measured + w

Clients will then properly avoid the scarce Exit class for their
dirport node selection, and properly redistribute their requests
accordingly, with no additional change in client logic beyond what is
already in my branch.

Because of the complexity of this change, and because we do not yet
have statistics for the bandwidth consumption of dirport traffic in a
balanced network condition, we are not going to compute these weights
this way yet until the network rebalances and stabilizes again.

In the meantime, it is likely that the bandwidth scanners will correct
for any misbalancing caused by treating these requests as middle
traffic, but using this method prevents us from having more control
over our specific scarcity case.


-- 
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/20100213/936ce0d9/attachment.pgp>