Hiberation wake up favours mid-month bandwidth

Currently the wake up interval is set uniformly between the start of the accounting cycle and the latest it could start to give enough time for exhaustion.

This is set by accounting_set_wakeup_time() in src/feature/hibernate/hibernate.c this is done to prevent all the relays waking up at midnight, Monday, the first of the month (or all three).

If relays operate for multiple days with accountancy cycles set to a month (starting on day 1) relays are more likely to be awake mid-month due to overlapping leading to uneven bandwidth distribution over the month. Many relays operate for more than 14 days.

You'd expect relay accountancy starts would be (nearly) randomly distributed but it does appear to be born out in the data:

Looking at the Tor bandwidth monitor at various timescales there does seem to be a mid-month peak visibile. https://metrics.torproject.org/bandwidth.html?start=2020-06-22&end=2020-08-20

Currently

wake_up_time = (get_uint32(digest) % time_to_consider); 

Where
digest = a crypt_rand() result
time_to_consider = accountancy_start - estimated_time_bandwidth_exhaustion

Difficulties

• Using only single wake up cycles, only relays which are estimated to use their bandwidth in less than 50% of the accountancy period could be used to fix this.
• The ideal function to level this would depend on the current state of relays. Maybe there is no solution that's better than the current state.

Alternatives

• Possibly as simple as setting the Accountancy Start date to 15th of month with expectation that many will alter it if needed. But this could be a sigificant Gotchya to users and could cost relay operators overage fees.
• Use a more biased wake-up time which is more likely to wake a relay near the beginning or end of the month.
• Randomizing accountancy start dates - risks overusing data.
• Or shorter cycles waking up when month is set go to sleep and wake up again before bandwidth exhausted. This seems clunky.
• Completely random wake ups this would risk not utilizing bandwidth.

Simulation

Can simulate the issue easily, assuming bandwidth is normal, speed is normally distributed, uniform wake up produces a normal distribution of bandwidth.

I assume in real data its weaker since accountancy start dates are random (somewhat)

sim_tor.py

As might be expected exponential distribution of wake up time produces a flat output.