[tor-dev] Proposal Waterfilling

[teor]

On 1 Feb 2018, at 07:15, Florentin Rochet <florentin.rochet at uclouvain.be> wrote:

>> On 18/01/18 01:03, teor wrote:
>> 
>>> I've added this concern within the 'unanswered questions' section. This
>>> proposal assumes relay measurement are reliable (consensus weight).
>> How reliable?
>> 
>> Current variance is 30% - 40% between identical bandwidth authorities, and
>> 30% - 60% between all bandwidth authorities.
>> 
>> Sources:
>> https://tomrittervg.github.io/bwauth-tools/#apples-to-apples-comparison
>> https://tomrittervg.github.io/bwauth-tools/#updated-01
>> 
>> Is this sufficient?
> 
> My apologies, I was not enough specific: we assume bandwidth
> measurements reliable as an hypothesis to make the claim that
> Waterfilling is not going to reduce or improve the performance. If these
> measurements are not reliable enough, then Waterfilling might make
> things better, worse or both compared to the current bandwidth-weights
> is some unpredictable way.

This variance is measurement error. In this case, discretization error is
less than 1%.

We need to know whether measurement inaccuracy makes the network
weights converge or diverge under your scheme.

It looks like they converge on the current network with the current
bandwidth authorities. This is an essential property we need to keep.

> All of this depends on the bandwidth
> authority. Anyway, I willingly agree that we need some kind of tools
> able to report on such modification. Besides, those tools could be
> reused for any new proposal impacting the path selection, such as
> research protecting against network adversaries or even some of the
> changes you already plan to do (such as Prop 276).

Yes, we are hoping to introduce better tools over time.

>> <skip>
>>> …
>>> 
>>> - The upper bound in (a) is huge, and would be appreciated for an
>>> adversary running relays. The adversary could manage to set relays with
>>> almost 2 times the consensus weight of the water level, and still being
>>> used at 100% in the entry position. This would reduce a lot the benefits
>>> of this proposal, right?
>> I do not know how much the benefits of the proposal depend on the exact
>> water level, and how close relays are to the water level.
>> 
>> …
>> 
>> How much variance will your proposal tolerate?
>> Because current variance is 30% - 60% anyway (see above).
> 
> The variance is not a problem if the water level is adapted
> (re-computed) at each consensus.

I'm not sure we're talking about the same thing here.
The variance I am talking about here is measurement error and
discretization error. Re-computation doesn't change the error.
(And going from relay measurement to consensus bandwidth can take hours.)

See my comment above about convergence: we need to converge in
the presence of discretization error, too.

>> …
>> 
>>> With your explanations below (weight change on clients), and given that
>>> the consensus diff size is a thing, I am leaning to believe that the
>>> weight calculation should be done on clients. Anyway, I have added a
>>> remark about this possibility within the proposal.
>> Another alternative is to apply proposal 276 weight rounding to these
>> weights as well.
>> 
>> https://gitweb.torproject.org/torspec.git/tree/proposals/276-lower-bw-granularity.txt
>> 
>> I think this may be our best option. Because running all these divisions on
>> some mobile clients will be very slow and cost a lot of power.
> 
> Added this to the proposal. We might also "divide" the algorithm: what
> about computing the weights on dirauths but broadcasting only the pivot
> (the index of the relay at the water level). Clients can then resume the
> computation and produce the weights themselves with a reduced cost.
> Strength:
>   - The weight calculation would be O(n) on clients (n being the size of
> the guard set) instead of O(n*log(n))
>   - No impact on the consensus diff (well, except 1 line, the pivot value).
> Weakness:
>   - We still have O(n) divisions on the client, each time we download a
> new consensus.

Why not list the waterfilling level on a single line in the consensus?

That way:
* authorities do the expensive calculation
* clients can re-weight relays using a simple calculation:

if it is less than or equal to the waterfilling level:
  use the relay's weight as its guard weight
  use 0 as its middle weight
otherwise:
  use the waterfilling level as the relay's guard weight
  use the relay's weight minus the waterfilling level as its middle weight

This is O(n) and requires one comparison and one subtraction in the worst case.

T