[tor-dev] Proposal Waterfilling

[Florentin Rochet]

Hi,

I updated the proposal with some more of your advises, questions and
concerns.

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

> <skip>
>> Wow, so first of all, thanks for suggesting new ways of resolving
>> issues. I really appreciate your consideration for this work.
>>
>> This suggestion indeed reduces the diff problem, and I find it elegant.
>> But, I have the following concerns:
>>
>>  - 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.
>
> I chose the exponent "2" as an example that is easy to calculate.
> Smaller exponents are possible.
>
> 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 think using the median reduces this, but I can't see it going below 40%,
> because that's what identical authorities get.)
>
>>  - The analysis in our paper works for equations we showed. Even if
>> these ones are very similar, I am not sure we can say that it would be
>> good without re-doing the research.
> I do not know enough to answer this.
>
>> 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.

> <skip>
>>>>> Unanswered questions:
>>>>>
>>>>> What about the feedback loop between this new allocation system
>>>>> and the bandwidth authorities?
>>>>>
>>>> I am sorry, I don't really understand why a feedback loop is needed. Measuring bandwidth and producing bandwidth-weights seems orthogonal to me.
>>> You do not need to add a feedback loop, one already exists:
>>> 1. Consensus weights on guards and middles change
>>> 2. Client use of guards and middles change
>>> 3. Bandwidth authority measurements of guards and middles change
>>> 4. Repeat from 1
>>>
>>> My question is:
>>>
>>> How does this existing feedback loop affect your proposal?
>>> Does it increase or reduce the size of the guard and middle weight changes?
>> I have added those questions to the proposal. This looks difficult to know.
> Can shadow simulate this?

I am not fully sure about this. Shadow's topology is static, meaning
that a change in advertised bandwidth does not change the uplink and
downlink bandwidth configured by the initial advertised bandwidth. But,
Shadow can use a Torflow plugin and continuously measure the virtual
network, which would produce the feedback loop you describe. However, we
have to run the simulation long enough to observe this effect, which was
not done in our research. We ran 1 virtual hour for each simulation
during our experiments (1 week of real time for each...).

Best,
Florentin

> --
> Tim / teor
>
> PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B
> ricochet:ekmygaiu4rzgsk6n
> ------------------------------------------------------------------------
>
>
>
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev