r14589@catbus: nickm | 2007-08-16 12:16:06 -0400

 Backport r10939 and r10956: correct handling for weighted exit selection.  I'm not backporting the bitfield code, so this is marginally slower than the version in trunk.


svn:r11133

3 files changed, 40 insertions, 14 deletions

diff --git a/ChangeLog b/ChangeLog
index 051e748191..eb5a0a21ec 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -8,6 +8,15 @@ Changes in version 0.1.2.xx - 2007-xxxxx
       now its only effect is to change our buffer sizes from nice
       powers of two (which platform mallocs tend to like) to values
       slightly over powers of two (which make some platform mallocs sad).
+    - If exit bandwidth ever exceeds one third of total bandwidth, then
+      use the correct formula to weight exit nodes when choosing paths.
+      (Based on patch from Mike Perry.)
+
+  o Minor bugfixes (misc):
+    - Choose perfectly fairly among routers when choosing by bandwidth and
+      weighting by fraction of bandwidth provided by exits.  Previously,
+      we would choose with only approximate fairness, and correct ourselves
+      if we ran off the end of the list.
 
 
 Changes in version 0.1.2.16 - 2007-08-01
diff --git a/doc/TODO.012 b/doc/TODO.012
index 5e309ed04b..5cb759d75b 100644
--- a/doc/TODO.012
+++ b/doc/TODO.012
@@ -1,6 +1,6 @@
 Backport items for 0.1.2:
-  - r10939: Choose with complete fairness when exits are weighted.
-  - r10956: fix the math for exit bandwidth weighting
+  o r10939: Choose with complete fairness when exits are weighted.
+  o r10956: fix the math for exit bandwidth weighting
   o r10994: Disable SENTINELS checking in order to use less RAM in
     buffer allocation.
   - r11117: cookie auth more usable
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 5dc935eab0..1c1d5c1f0e 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -961,6 +961,7 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, int for_exit, int statuses)
   uint64_t rand_bw, tmp;
   double exit_weight;
   int n_unknown = 0;
+  int include_exits = 1;
 
   /* First count the total bandwidth weight, and make a list
    * of each value.  <0 means "unknown; no routerinfo."  We use the
@@ -1043,19 +1044,35 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, int for_exit, int statuses)
     /* If we're choosing an exit node, exit bandwidth counts fully. */
     exit_weight = 1.0;
     total_bw = total_exit_bw + total_nonexit_bw;
-  } else if (total_exit_bw < total_nonexit_bw / 2) {
-    /* If we're choosing a relay and exits are greatly outnumbered, ignore
-     * them. */
-    exit_weight = 0.0;
-    total_bw = total_nonexit_bw;
   } else {
-    /* If we're choosing a relay and exits aren't outnumbered use the formula
-     * from path-spec. */
-    uint64_t leftover = (total_exit_bw - total_nonexit_bw / 2);
-    exit_weight = U64_TO_DBL(leftover) /
-      U64_TO_DBL(leftover + total_nonexit_bw);
-    total_bw =  total_nonexit_bw +
-      DBL_TO_U64(exit_weight * U64_TO_DBL(total_exit_bw));
+    double all_bw = U64_TO_DBL(total_exit_bw+total_nonexit_bw);
+    double exit_bw = U64_TO_DBL(total_exit_bw);
+    /*
+     * For detailed derivation of this formula, see
+     *   http://archives.seul.org/or/dev/Jul-2007/msg00056.html
+     */
+    exit_weight = 1.0 - all_bw/(3.0*exit_bw);
+    if (exit_weight <= 0.0) {
+      include_exits = 0;
+      exit_weight = 0.0;
+      total_bw = total_nonexit_bw;
+    } else {
+      include_exits = 1;
+      total_bw = 0;
+      for (i=0; i < smartlist_len(sl); i++) {
+        if (statuses) {
+          status = smartlist_get(sl, i);
+          is_exit = status->is_exit;
+        } else {
+          router = smartlist_get(sl, i);
+          is_exit = router->is_exit;
+        }
+        if (is_exit)
+          total_bw += ((uint64_t)(bandwidths[i] * exit_weight));
+        else
+          total_bw += bandwidths[i];
+      }
+    }
   }
   /*
   log_debug(LD_CIRC, "Total bw = "U64_FORMAT", total exit bw = "U64_FORMAT