[tor-bugs] #27337 [Core Tor/sbws]: Round relay bandwidths in bandwidth files

[Tor Bug Tracker & Wiki]

#27337: Round relay bandwidths in bandwidth files
---------------------------+-------------------------------------
 Reporter:  teor           |          Owner:  (none)
     Type:  defect         |         Status:  reopened
 Priority:  Medium         |      Milestone:  sbws 1.0 (MVP must)
Component:  Core Tor/sbws  |        Version:
 Severity:  Normal         |     Resolution:
 Keywords:                 |  Actual Points:
Parent ID:                 |         Points:
 Reviewer:                 |        Sponsor:
---------------------------+-------------------------------------

Comment (by teor):

 You are correct: sbws' bandwidth rounding scheme adds a maximum error of
 -/+ 5%, and a minimum error of +/- 0.5% (as long as the bandwidth is above
 200).

 We round to 2 significant figures so that compressed consensus diffs are
 small. This is a partial implementation of proposal 276:
 https://gitweb.torproject.org/torspec.git/tree/proposals/276-lower-bw-
 granularity.txt#n27

 I believe that this added error is acceptable, given the current design of
 the bandwidth weighting system.

 Here's how bandwidth measurement system works right now, with the accuracy
 levels at each step:
 * relays report their observed bandwidths every day, or when they are more
 than half or twice the previous bandwidth (greater than -50% or +100%
 change)
 * relays are measured up to a few times per day (usually around 2% change,
 but potentially unlimited change):
 https://gitweb.torproject.org/torspec.git/tree/proposals/276-lower-bw-
 granularity.txt#n27
 * every hour, these observations and measurements are used to create
 bandwidths for votes, rounded to 2 significant figures (+/- 5% change)
 * the consensus uses the low-median of the votes for each relay (choosing
 one figure among several that often differ by more than 100%)
 * clients download compressed diffs of the consensus (no change)
 * clients choose relays at random using bandwidth weights from the
 consensus (no change)

 The rounding step doesn't introduce very much relative inaccuracy (5% or
 less), compared to the rest of the system (2%, 50%, 100%, or greater).

 Even if the rest of the system were perfectly accurate, this change
 doesn't introduce very much absolute inaccuracy:
 * the largest relay is approximately 3% of exit probability:
 https://metrics.torproject.org/rs.html#details/BC630CBBB518BE7E9F4E09712AB0269E9DC7D626
 * So the change in probability for this relay is 5% * 3% = 0.15%, or at
 most 1 in 667 exit choices
 * And the overall affect across the network would be 5%, or at most 1 in
 20 relay choices, but on average, it would be about 1.4%, or 1 in 70 relay
 choices

 Torflow's existing rounding already affects at most 1 in 200 relay
 choices, or on average, 1 in 700 relay choices.

 If you believe that the added rounding in sbws will have a significant
 effect on the network, please open a new ticket with appropriate
 calculations, or send an email to the tor-dev list. Then we will consider
 modifying proposal 276.

 If you think we should implement smoothing in sbws' rounding algorithm,
 please open a new ticket, and we'll implement the rest of proposal 276.

 (The code that was written for this ticket has been release. We don't re-
 use old tickets for new work: it makes changelogs really confusing.)

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/27337#comment:10>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online