[tor-bugs] #27135 [Core Tor/sbws]: Write descriptor bandwidths average in raw results

[Tor Bug Tracker & Wiki]

#27135: Write descriptor bandwidths average in raw results
---------------------------+-------------------------------------
 Reporter:  juga           |          Owner:  juga
     Type:  defect         |         Status:  assigned
 Priority:  Medium         |      Milestone:  sbws 1.0 (MVP must)
Component:  Core Tor/sbws  |        Version:
 Severity:  Normal         |     Resolution:
 Keywords:                 |  Actual Points:
Parent ID:  #27108         |         Points:
 Reviewer:                 |        Sponsor:
---------------------------+-------------------------------------

Comment (by teor):

 Replying to [comment:10 juga]:
 >
 > > take the decaying average of the measurements, and scale by the
 decaying average of the descriptor bandwidths
 >
 > could you point out what do you mean by decaying average?, this [0]?

 Yes, I mean an exponentially decaying average. But that article was
 written by mathematicians, not programmers.

 Here's a simple exponential decay algorithm that can be used for both
 descriptor bandwidths and measured bandwidths:

 1. Set the decay constant (R) to a number in (0, 1).

     We get a descriptor every 12-18 hours, and there is a daily cycle in
 Tor bandwidths. So we want to average over a few days, to smooth out
 spikes. A good value for R is 0.98 every hour, because the decaying
 average for 15 hour bandwidths is 26% B1 + 19% B2 + 14% B3 + 11% B4 + 30%
 B5-10. (B11 is less than 1%.)

 2. For each relay, set the decaying average (D) to 1

 3. At the start of each hour:

   a. multiply the decaying average by the decay constant: D *= R

   b. add the most recent bandwidth (B) to the decaying average: D += B

 4. When voting:

   a. Scale decaying averages before including them in votes (V): `V = D *
 (1 - R)`

      If a relay has a constant bandwidth (B), then the decaying average
 will eventually be (strictly, will converge to) `B * 1/(1 - R)`. We
 probably want decaying average bandwidths to be comparable to bandwidths,
 so we should scale them.

   b. Scale each relay's weight so the total is approximately torflow's
 total weight.

     We want the consensus weights to be comparable with Torflow's
 consensus weights.

   c. If the relay's weight is 0, vote 1.

     We want all relays to have a small weight, to avoid zero-division
 bugs.

 > btw, it seems that the answer to my question in [1] is that 1/45 ~= 1/e

 Can you explain what you mean by `e`?

 The base of the natural logarithm is `e ~= 2.72`, so `1/e ~= 0.37`.

 > > how we handle new relays (treat their old bandwidths as 1 is a nice
 simple way of rewarding stability)
 >
 > you mean for their descriptor bw?, for what we write to the bw file?

 Yes, for the initial decaying average for new relays, and the final vote
 bandwidth for all relays. See steps 2. and 4.c. above, where I use 1
 instead of 0.

 > [0] https://en.wikipedia.org/wiki/Exponential_decay#Mean_lifetime
 > [1] https://github.com/pastly/simple-bw-
 scanner/issues/182#issuecomment-409341398

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