Update specs for weight computation and use.

2 files changed, 211 insertions, 19 deletions

diff --git a/doc/spec/dir-spec.txt b/doc/spec/dir-spec.txt
index 19a32027a..bd20b527d 100644
--- a/doc/spec/dir-spec.txt
+++ b/doc/spec/dir-spec.txt
@@ -1304,8 +1304,42 @@
         or does not support (if 'reject') for exit to "most
         addresses".
 
-   The signature section contains the following item, which appears
-   Exactly Once for a vote, and At Least Once for a consensus.
+   The footer section is delineated in all votes and consensuses supporting
+   consensus method 9 and above with the following:
+
+    "directory-footer" NL
+
+   It contains two subsections, a bandwidths-weights line and a
+   directory-signature.
+
+   The bandwidths-weight line appears At Most Once for a consensus. It does
+   not appear in votes.
+
+    "bandwidth-weights" SP "Wed=" INT SP "Wee=" INT SP "Weg=" INT SP
+       "Wem=" INT SP "Wgd=" INT SP "Wgg=" INT SP "Wgm=" INT SP
+       "Wmd=" INT SP "Wme=" INT SP "Wmg=" INT SP "Wmm=" INT SP NL
+
+       These values represent the weights to apply to router bandwidths during
+       path selection. They are sorted in alphabetical order in the list. The
+       integer values are divided by BW_WEIGHT_SCALE=10000 or the consensus
+       param "bwweightscale". They are:
+
+         Wgg - Weight for Guard-flagged nodes in the guard position
+         Wgm - Weight for non-flagged nodes in the guard Position
+         Wgd - Weight for Guard+Exit-flagged nodes in the guard Position
+         Wmg - Weight for Guard-flagged nodes in the middle Position
+         Wmm - Weight for non-flagged nodes in the middle Position
+         Wme - Weight for Exit-flagged nodes in the middle Position
+         Wmd - Weight for Guard+Exit flagged nodes in the middle Position
+         Weg - Weight for Guard flagged nodes in the exit Position
+         Wem - Weight for non-flagged nodes in the exit Position
+         Wee - Weight for Exit-flagged nodes in the exit Position
+         Wed - Weight for Guard+Exit-flagged nodes in the exit Position
+
+       These values are calculated as specified in Section 3.4.3.
+
+   The signature contains the following item, which appears Exactly Once
+   for a vote, and At Least Once for a consensus.
 
     "directory-signature" SP identity SP signing-key-digest NL Signature
 
@@ -1586,6 +1620,146 @@
   use an accept-style summary and list as much of the port list as is
   possible within these 1000 bytes.  [XXXX be more specific.]
 
+3.4.3. Computing Bandwidth Weights
+
+  Let weight_scale = 10000
+
+  Let G be the total bandwidth for Guard-flagged nodes.
+  Let M be the total bandwidth for non-flagged nodes.
+  Let E be the total bandwidth for Exit-flagged nodes.
+  Let D be the total bandwidth for Guard+Exit-flagged nodes.
+  Let T = G+M+E+D
+
+  Let Wgd be the weight for choosing a Guard+Exit for the guard position.
+  Let Wmd be the weight for choosing a Guard+Exit for the middle position.
+  Let Wed be the weight for choosing a Guard+Exit for the exit position.
+
+  Let Wme be the weight for choosing an Exit for the middle position.
+  Let Wmg be the weight for choosing a Guard for the middle position.
+
+  Let Wgg be the weight for choosing a Guard for the guard position.
+  Let Wee be the weight for choosing an Exit for the exit position.
+
+  Balanced network conditions then arise from solutions to the following
+  system of equations:
+
+      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*D + Wmd*D + Wgd*D == D                  (aka: Wed+Wmd+Wdg = 1)
+      Wmg*G + Wgg*G == G                          (aka: Wgg = 1-Wmg)
+      Wme*E + Wee*E == E                          (aka: Wee = 1-Wme)
+
+  We are short 2 constraints with the above set. The remaining constraints
+  come from examining different cases of network load.
+
+  Case 1: E >= T/3 && G >= T/3 (Neither Exit nor Guard Scarce)
+
+    In this case, the additional two constraints are: Wme*E == Wmd*D and
+    Wgd == 0, which maximizes Exit-flagged bandwidth in the middle position.
+
+    This leads to the solution:
+
+       Wgg = (weight_scale*(D+E+G+M))/(3*G)
+       Wmd = (weight_scale*(2*D + 2*E - G - M))/(6*D)
+       Wme = (weight_scale*(2*D + 2*E - G - M))/(6*E)
+       Wee = (weight_scale*(-2*D + 4*E + G + M))/(6*E)
+       Wmg = weight_scale - Wgg
+       Wed = weight_scale - Wmd
+       Wgd = 0
+
+  Case 2: E < T/3 && G < T/3 (Both are scarce)
+
+    Let R denote the more scarce class (Rare) between Guard vs Exit.
+    Let S denote the less scarce class.
+
+    Subcase a: R+D < S
+
+       In this subcase, we simply devote all of D bandwidth to the
+       scarce class.
+
+       Wgg = Wee = weight_scale
+       Wmg = Wme = Wmd = 0;
+       if E < G:
+         Wed = weight_scale
+         Wgd = 0
+       else:
+         Wed = 0
+         Wgd = weight_scale
+
+    Subcase b: R+D >= S
+
+      In this case, if M <= T/3, we have enough bandwidth to try to achieve
+      a balancing condition, and add the constraints Wgg == 1 and
+      Wme*E == Wmd*D:
+
+         Wgg = weight_scale
+         Wgd = (weight_scale*(D + E - 2*G + M))/(3*D)      (T/3 >= G (Ok))
+         Wmd = (weight_scale*(D + E + G - 2*M))/(6*D)      (T/3 >= M)
+         Wme = (weight_scale*(D + E + G - 2*M))/(6*E)
+         Wee = (weight_scale*(-D + 5*E - G + 2*M))/(6*E)   (2E+M >= T/3)
+         Wmg = 0;
+         Wed = weight_scale - Wgd - Wmd
+
+      If M >= T/3, the above solution will not be valid (one of the weights
+      will be < 0 or > 1). In this case, we use:
+
+         Wgg = weight_scale
+         Wee = weight_scale
+         Wmg = Wme = Wmd = 0
+         Wgd = (weight_scale*(D+E-G))/(2*D)
+         Wed = weight_scale - Wgd
+
+  Case 3: One of E < T/3 or G < T/3
+
+    Let S be the scarce class (of E or G).
+
+    Subcase a: (S+D) < T/3:
+      if G=S:
+          Wgg = Wgd = weight_scale;
+          Wmd = Wed = Wmg = 0;
+          Wme = (weight_scale*(E-M))/(2*E);
+          Wee = weight_scale-Wme;
+      if E=S:
+          Wee = Wed = weight_scale;
+          Wmd = Wgd = Wmg = 0;
+          Wmg = (weight_scale*(G-M))/(2*G);
+          Wgg = weight_scale-Wmg;
+
+    Subcase b: (S+D) >= T/3
+      if G=S:
+        Add constraints Wmg = 0, Wme*E == Wmd*D to maximize exit bandwidth
+        in the middle position:
+          Wgd = (weight_scale*(D + E - 2*G + M))/(3*D);
+          Wmd = (weight_scale*(D + E + G - 2*M))/(6*D);
+          Wme = (weight_scale*(D + E + G - 2*M))/(6*E);
+          Wee = (weight_scale*(-D + 5*E - G + 2*M))/(6*E);
+          Wgg = weight_scale;
+          Wmg = 0;
+          Wed = weight_scale - Wgd - Wmd;
+      if E=S:
+        Add constraints Wgd = 0, Wme*E == Wmd*D:
+          Wgg = (weight_scale*(D + E + G + M))/(3*G);
+          Wmd = (weight_scale*(2*D + 2*E - G - M))/(6*D);
+          Wme = (weight_scale*(2*D + 2*E - G - M))/(6*E);
+          Wee = (weight_scale*(-2*D + 4*E + G + M))/(6*E);
+          Wgd = 0;
+          Wmg = weight_scale - Wgg;
+          Wed = weight_scale - Wmd;
+
+  To ensure consensus, all calculations are performed using integer math
+  with a fixed precision determined by the bwweightscale consensus
+  parameter (defaults at 10000).
+
+  For future balancing improvements, Tor clients support 11 additional weights
+  for directory requests and middle weighting. These weights are currently
+  set at 1.0, with the exception of the following groups of assignments:
+
+  Directory requests use middle weights:
+     Wbd=Wmd, Wbg=Wmg, Wbe=Wme, Wbm=Wmm
+
+  Handle bridges and strange exit policies:
+     Wgm=Wgg, Wem=Wee, Weg=Wed
+
 3.5. Detached signatures
 
    Assuming full connectivity, every authority should compute and sign the
diff --git a/doc/spec/path-spec.txt b/doc/spec/path-spec.txt
index 78f3b63bc..8a85718a0 100644
--- a/doc/spec/path-spec.txt
+++ b/doc/spec/path-spec.txt
@@ -192,23 +192,41 @@ of their choices.
        below)
      - XXXX Choosing the length
 
-   For circuits that do not need to be "fast", when choosing among
-   multiple candidates for a path element, we choose randomly.
-
-   For "fast" circuits, we pick a given router as an exit with probability
-   proportional to its bandwidth.
-
-   For non-exit positions on "fast" circuits, we pick routers as above, but
-   we weight the bandwidth of Exit-flagged nodes depending
-   on the fraction of bandwidth available from non-Exit nodes.  Call the
-   total bandwidth for Exit nodes under consideration E,
-   and the total bandwidth for all nodes under
-   consideration T.  If E<T/3, we do not consider Exit-flagged nodes.
-   Otherwise, we weight their bandwidth with the factor (E-T/3)/E. This 
-   ensures that bandwidth is evenly distributed over nodes in 3-hop paths.
-
-   Similarly, guard nodes are weighted by the factor (G-T/3)/G, and not
-   considered for non-guard positions if this value is less than 0.
+   For "fast" circuits, we only choose nodes with the Fast flag. For
+   non-"fast" circuits, all nodes are eligible.
+
+   For all circuits, we weight node selection according to router bandwidth.
+
+   We also weight the bandwidth of Exit and Guard flagged nodes depending on
+   the fraction of total bandwidth that they make up and depending upon the
+   position they are being selected for.
+
+   These weights are published in the consensus, and are computed as described
+   in Section 3.4.3 of dir-spec.txt. They are:
+
+      Wgg - Weight for Guard-flagged nodes in the guard position
+      Wgm - Weight for non-flagged nodes in the guard Position
+      Wgd - Weight for Guard+Exit-flagged nodes in the guard Position
+
+      Wmg - Weight for Guard-flagged nodes in the middle Position
+      Wmm - Weight for non-flagged nodes in the middle Position
+      Wme - Weight for Exit-flagged nodes in the middle Position
+      Wmd - Weight for Guard+Exit flagged nodes in the middle Position
+
+      Weg - Weight for Guard flagged nodes in the exit Position
+      Wem - Weight for non-flagged nodes in the exit Position
+      Wee - Weight for Exit-flagged nodes in the exit Position
+      Wed - Weight for Guard+Exit-flagged nodes in the exit Position
+
+      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
 
    Additionally, we may be building circuits with one or more requests in
    mind.  Each kind of request puts certain constraints on paths: