Opened 15 months ago

Closed 12 months ago

Last modified 12 months ago

#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 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

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*10n (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 teor

Description: modified (diff)

comment:2 Changed 15 months ago by teor

Parent ID: #27108

comment:3 Changed 15 months ago by teor

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

comment:4 in reply to:  description ; Changed 15 months ago by juga

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*10n (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 in reply to:  4 Changed 15 months ago by teor

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 juga

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

comment:7 Changed 15 months ago by juga

Status: newneeds_review

comment:8 Changed 14 months ago by juga

Resolution: implemented
Status: needs_reviewclosed

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 starlight

Cc: starlight@… added
Parent ID: #27108
Resolution: implemented
Status: closedreopened

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 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:

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 teor

Resolution: fixed
Status: reopenedclosed

comment:12 Changed 12 months ago by teor

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 teor

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

Note: See TracTickets for help on using tickets.