proposals/160-bandwidth-offset.txt

   1 Filename: 160-bandwidth-offset.txt
   2 Title: Authorities vote for bandwidth offsets in consensus
   3 Author: Roger Dingledine
   4 Created: 4-May-2009
   5 Status: Finished
   6 Target: 0.2.1.x
   7
   8 1. Motivation
   9
  10   As part of proposal 141, we moved the bandwidth value for each relay
  11   into the consensus. Now clients can know how they should load balance
  12   even before they've fetched the corresponding relay descriptors.
  13
  14   Putting the bandwidth in the consensus also lets the directory
  15   authorities choose more accurate numbers to advertise, if we come up
  16   with a better algorithm for deciding weightings.
  17
  18   Our original plan was to teach directory authorities how to measure
  19   bandwidth themselves; then every authority would vote for the bandwidth
  20   it prefers, and we'd take the median of votes as usual.
  21
  22   The problem comes when we have 7 authorities, and only a few of them
  23   have smarter bandwidth allocation algorithms. So long as the majority
  24   of them are voting for the number in the relay descriptor, the minority
  25   that have better numbers will be ignored.
  26
  27 2. Options
  28
  29   One fix would be to demand that every authority also run the
  30   new bandwidth measurement algorithms: in that case, part of the
  31   responsibility of being an authority operator is that you need to run
  32   this code too. But in practice we can't really require all current
  33   authority operators to do that; and if we want to expand the set of
  34   authority operators even further, it will become even more impractical.
  35   Also, bandwidth testing adds load to the network, so we don't really
  36   want to require that the number of concurrent bandwidth tests match
  37   the number of authorities we have.
  38
  39   The better fix is to allow certain authorities to specify that they are
  40   voting on bandwidth measurements: more accurate bandwidth values that
  41   have actually been evaluated. In this way, authorities can vote on
  42   the median measured value if sufficient measured votes exist for a router,
  43   and otherwise fall back to the median value taken from the published router
  44   descriptors.
  45
  46 3. Security implications
  47
  48   If only some authorities choose to vote on an offset, then a majority of
  49   those voting authorities can arbitrarily change the bandwidth weighting
  50   for the relay. At the extreme, if there's only one offset-voting
  51   authority, then that authority can dictate which relays clients will
  52   find attractive.
  53
  54   This problem isn't entirely new: we already have the worry wrt
  55   the subset of authorities that vote for BadExit.
  56
  57   To make it not so bad, we should deploy at least three offset-voting
  58   authorities.
  59
  60   Also, authorities that know how to vote for offsets should vote for
  61   an offset of zero for new nodes, rather than choosing not to vote on
  62   any offset in those cases.
  63
  64 4. Design
  65
  66   First, we need a new consensus method to support this new calculation.
  67
  68   Now v3 votes can have an additional value on the "w" line:
  69     "w Bandwidth=X Measured=" INT.
  70
  71   Once we're using the new consensus method, the new way to compute the
  72   Bandwidth weight is by checking if there are at least 3 "Measured"
  73   votes. If so, the median of these is taken. Otherwise, the median
  74   of the "Bandwidth=" values are taken, as described in Proposal 141.
  75
  76   Then the actual consensus looks just the same as it did before,
  77   so clients never have to know that this additional calculation is
  78   happening.
  79
  80 5. Implementation
  81
  82   The Measured values will be read from a file provided by the scanners
  83   described in proposal 161. Files with a timestamp older than 3 days
  84   will be ignored.
  85
  86   The file will be read in from dirserv_generate_networkstatus_vote_obj()
  87   in a location specified by a new config option "V3MeasuredBandwidths".
  88   A helper function will be called to populate new 'measured' and
  89   'has_measured' fields of the routerstatus_t 'routerstatuses' list with
  90   values read from this file.
  91
  92   An additional for_vote flag will be passed to
  93   routerstatus_format_entry() from format_networkstatus_vote(), which will
  94   indicate that the "Measured=" string should be appended to the "w Bandwith="
  95   line with the measured value in the struct.
  96
  97   routerstatus_parse_entry_from_string() will be modified to parse the
  98   "Measured=" lines into routerstatus_t struct fields.
  99
 100   Finally, networkstatus_compute_consensus() will set rs_out.bandwidth
 101   to the median of the measured values if there are more than 3, otherwise
 102   it will use the bandwidth value median as normal.
 103
 104
 105