Round relay bandwidths in bandwidth files

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.

changed milestone to %sbws: 1.0.x-final

added component::core tor/sbws milestone::sbws: 1.0.x-final priority::medium resolution::fixed sbws-1.0-must-closed-moved-20181128 severity::normal status::closed type::defect labels

Trac:
Description: 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.

to

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.

Trac:
Parent: N/A to #27108 (moved)

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

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?

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.

Implementation is ready, but #27135 (moved), #27386 (moved), #27336 (moved) need to be fixed first and i'll wait for #27398 (moved) to be fixed too to make PRs

Blocked by #27398 (moved). Implementented in https://github.com/juga0/simple-bw-scanner/commits/dev

Trac:
Status: new to needs_review

Implemented in https://github.com/torproject/sbws/pull/255 Created #27689 (moved) to implement what is commented in #comment:3

Trac:
Resolution: N/A to implemented
Status: needs_review to closed

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%

Trac:
Cc: pastly, juga, teor to pastly, juga, teor, starlight@binnacle.cx
Resolution: implemented to N/A
Parent: #27108 (moved) to N/A
Status: closed to reopened

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.)

Trac:
Status: reopened to closed
Resolution: N/A to fixed

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 (moved),

Move all closed sbws 1.0 must tickets to sbws 1.0.x-final

Trac:
Keywords: N/A deleted, sbws-1.0-must-closed-moved-20181128 added
Milestone: sbws 1.0 (MVP must) to sbws: 1.0.x-final

closed

mentioned in issue #27338 (moved)

mentioned in issue #27690 (moved)

mentioned in issue #28442 (moved)

mentioned in issue #28442 (moved)

mentioned in issue #28447 (moved)

mentioned in issue tpo/core/tor#27690 (closed)

moved to tpo/network-health/sbws#27337 (closed)

mentioned in issue tpo/network-health/sbws#28442 (closed)

mentioned in issue tpo/network-health/sbws#28447 (closed)