#27337 closed defect (fixed)
Round relay bandwidths in bandwidth files
Reported by: | teor | Owned by: | |
---|---|---|---|
Priority: | Medium | Milestone: | sbws: 1.0.x-final |
Component: | Core Tor/sbws | Version: | |
Severity: | Normal | Keywords: | sbws-1.0-must-closed-moved-20181128 |
Cc: | pastly, juga, teor, starlight@… | Actual Points: | |
Parent ID: | Points: | ||
Reviewer: | Sponsor: |
Description (last modified by )
Torflow rounds raw bandwidths to 3 significant figures, and increases 0 bandwidths to 1:
https://gitweb.torproject.org/torflow.git/tree/NetworkScanners/BwAuthority/aggregate.py#n62
Rounding
sbws must round to 3 (or fewer) significant figures, so that consensus diffs are still efficient.
I suggest 2 significant figures, because the largest error is 5% at 1.5*10^{n} (for example: (105-100)/100 = 5%).
Bandwidth authorities already vary from each other by 25-50%:
https://trac.torproject.org/projects/tor/ticket/25459#comment:5
And network load varies each day (from what I remember, my guards and exits used to vary by at least 10% every day).
Avoiding Zeroes
I think sbws should also increase 0 bandwidths to 1.
We also have to update the spec, I'll open a child ticket.
Child Tickets
Change History (13)
comment:1 Changed 15 months ago by
Description: | modified (diff) |
---|
comment:2 Changed 15 months ago by
Parent ID: | → #27108 |
---|
comment:3 Changed 15 months ago by
comment:4 follow-up: 5 Changed 15 months ago by
Replying to teor:
Torflow rounds raw bandwidths to 3 significant figures, and increases 0 bandwidths to 1:
https://gitweb.torproject.org/torflow.git/tree/NetworkScanners/BwAuthority/aggregate.py#n62
ah, i've being wondering why that
Rounding
sbws must round to 3 (or fewer) significant figures, so that consensus diffs are still efficient.
I suggest 2 significant figures, because the largest error is 5% at 1.5*10^{n} (for example: (105-100)/100 = 5%).
ok, will implement this
Bandwidth authorities already vary from each other by 25-50%:
https://trac.torproject.org/projects/tor/ticket/25459#comment:5
And network load varies each day (from what I remember, my guards and exits used to vary by at least 10% every day).
Avoiding Zeroes
I think sbws should also increase 0 bandwidths to 1.
hmm, which one of the bandwidth values?. So far the we round all decimal values and take max(value, 1). The only bandwidth that can still be 0 is the descriptor observed bandwidth, that's it's also rounded and take min 1 after it's multiplied by the ratio. Should the descriptor observed bandwidth be at least 1 before multiplying by the ratio?
comment:5 Changed 15 months ago by
Replying to juga:
Replying to teor:
Avoiding Zeroes
I think sbws should also increase 0 bandwidths to 1.
hmm, which one of the bandwidth values?. So far the we round all decimal values and take max(value, 1). The only bandwidth that can still be 0 is the descriptor observed bandwidth, that's it's also rounded and take min 1 after it's multiplied by the ratio. Should the descriptor observed bandwidth be at least 1 before multiplying by the ratio?
Each relay's consensus weight in the vote must be >= 1.
You know the sbws code better than I do, so you can implement that however you want.
comment:6 Changed 15 months ago by
comment:7 Changed 15 months ago by
Status: | new → needs_review |
---|
Blocked by #27398.
Implementented in https://github.com/juga0/simple-bw-scanner/commits/dev
comment:8 Changed 14 months ago by
Resolution: | → implemented |
---|---|
Status: | needs_review → closed |
Implemented in https://github.com/torproject/sbws/pull/255
Created #27689 to implement what is commented in #comment:3
comment:9 Changed 12 months ago by
Cc: | starlight@… added |
---|---|
Parent ID: | #27108 |
Resolution: | implemented |
Status: | closed → reopened |
The chosen approach suffers from severe non-linear steps between round values:
100000 -> 110000 +10.0% 40000 -> 41000 +2.5%
The proper way to accomplish this is to round by taking the natural
log of the value, round that to the nearest 1/20th for uniform
5% steps and then raise e by the result:
100000 rounds to 98716 105000 rounds to 103777 98716 -> 103777 +5.1% 40000 rounds to 40135 42000 rounds to 42193 40135 -> 42193 +5.1% 1100 rounds to 1096 1050 rounds to 1043 1043 -> 1096 +5.1%
comment:10 Changed 12 months ago by
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.)
comment:11 Changed 12 months ago by
Resolution: | → fixed |
---|---|
Status: | reopened → closed |
comment:12 Changed 12 months ago by
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 ticket already exists, it's #27689,
comment:13 Changed 12 months ago by
Keywords: | sbws-1.0-must-closed-moved-20181128 added |
---|---|
Milestone: | sbws 1.0 (MVP must) → sbws: 1.0.x-final |
Move all closed sbws 1.0 must tickets to sbws 1.0.x-final
Proposal 276 contains a slightly more complicated rounding algorithm,
which we may want to implement in sbws or in tor:
https://gitweb.torproject.org/torspec.git/tree/proposals/276-lower-bw-granularity.txt