[tor-dev] Proposal Waterfilling

Thu Jan 18 00:03:50 UTC 2018

> On 18 Jan 2018, at 08:10, Florentin Rochet <florentin.rochet at uclouvain.be> wrote:
> ...
>> It might help to provide a procedural algorithm for assigning
>> bandwidth, as well as equations. It would resolve some ambiguity.
> 
> Not sure to understand what 'bandwidth' signifies here. I can provide a
> procedural algorithm to compute the waterfilling bandwidth-weights, if
> this is what you meant?

Yes.

> ...
> 
>>>> ...
>>>> <skip>
>>>>> 2.1 Going further by tweaking original bandwidth-weights computation
>>>>> 
>>>>>  As explained above, our Waterfilling equations are based on: 1) the
>>>>>  Wgg weight computed by Tor 2) the assumption that the bandwidth
>>>>>  available in exit is scarce, i.e., it is lower than the one
>>>>>  available for guard (and middle) positions.
>>>>> 
>>>>>  The second point is satisfied most of the time in Tor, and we do take
>>>>>  it for granted here.
>>>>> 
>>>>>  We, however, observe that Waterfilling could be made even more
>>>>>  effective by applying a minor change in the way Tor computes the
>>>>>  Wgg.  For the moment, Tor computes Wgg in such a way that the same
>>>>>  bandwidth is allocated to the guard and middle positions. As a
>>>>>  result, both positions are in excess compared to the exit position.
>>>>> 
>>>>>  The water level could be decreased and, as a result, the uniformity
>>>>>  of the guard selection process could be improved, by computing Wgg
>>>>>  in a way that allocates the same bandwidth to the guard and exit
>>>>>  positions, putting the middle position as the only position in
>>>>>  excess.
>>>> No, this would slow down Guards, and everything that isn't an exit circuit:
>>>> * directory fetches (3% of total bandwidth to guard position)
>> If we reduce guard weights on large relays, does this slow down Tor bootstrap?
>> (Because smaller relays with higher latency get more micro descriptor requests.)
>> 
>> Does it slow down directory fetches in general?
> 
> Assuming smallest guards have an higher latency in average, this could
> indeed slow down directory fetches and then, maybe it would slow down
> Tor bootstrapping. I guess that measuring this with Shadow is possible,
> as well as collecting statistics on a small set of deployed Tor clients.

This would be helpful.
Although the overall effect might not be measurable.
If it is, we could use the unmodified guard weights for directory fetches.

>>>> * onion services (rend is 4% of total bandwidth to guard and middle)
>>>> * HSDir is unweighted, and we don't know how much bandwidth it uses
>>>> * FallbackDir is unweighted, but mostly Guards, and small
>>>> 
>>> That's difficult to predict, I cannot be sure if it is better or worse for that type of traffic since internal circuits use at least 2 middle relays + the guard and sometimes, even not the guard. Hence we might also think that pushing a bit more to the middle position could be a good thing to do. Moreover, middle relays are unstable and often at the edge of the internet, while guard are stable and most of them within the core of the internet. Hence, a little more of them within the middle position *could* be a good thing, especially if it makes entry's selection probability more uniform. Anyway, I don't have any proof to assert this, as well that I don't have any proof to assert that this optimization could be bad. What I got, is that, for exit circuits, it does not slow down anything.
>>> 
>>> This optimization is not mandatory, and could also be enabled/disabled at will by the directory auths.
>>> 
>>>>>  We show in the performance section of the Waterfilling paper that
>>>>>  scarcity on two positions does not reduce performance compared to
>>>>>  vanilla bandwidth-weights.
>>>> What about guards that have low consensus weight due to latency,
>>>> rather than available bandwidth?
>>>> 
>>>> I think this could also cause you huge latency issues as you push more
>>>> bandwidth away from fast relays. I'm not sure if shadow captures this
>>>> accurately.
>>>> 
>>> If it happens that any bandwidth is pushed away from fast relays within the entry position and make the entry position slower, at average, then it will make the middle position faster (because it got that bandwidth pushed away). Since the latency of your traffic flow just care about the global latency of the circuit, this will not appear to be slower or faster, on average. This is exactly what we observe in Shadow, and yes, it captures latency accurately. At least, better than any other simulator.
>> I am also concerned that this proposal may overload small guards and
>> underload large guards. Because it does not consider advertised
>> bandwidth.
> 
> 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?

> If
> this is not the case, then strange things might happen. In our Shadow
> results, we have seen that the tails of the CDFs for measurements were a
> little bit "longer", meaning that the few worst circuits (3%) that we
> can obtain with the current path selection were a little bit worse with
> Waterfilling on a loaded network (no change on a light network).

This might not be great. UX studies show that users notice the worst
delays, and the variance between the best and worst delays.

> And,
> this fraction of worse circuits was even reduced (less than 1%) when we
> applied Section 2.1 of the proposal (moving more bandwidth to the middle
> position).

Maybe we should do this then.

> How does the current path selection considers advertised bandwidth?
> (Apart bwauths when measuring relays?).

It does not, because advertised bandwidth is easily modified by each relay.

>> For example, some guards are weighted at 10x their advertised bandwidth.
>> Others are weighted at 0.1x their advertised bandwidth.
>> 
>> There is also a geographical bias to guard bandwidth:
>> https://atlas.torproject.org/#map_consensus_weight_to_bandwidth/flag:Guard
> 
> Yep, Thanks for the link. Atlas becomes nicer :) For what it worth, a
> possible explanation for this bias would be to consider how big ISPs
> route internal traffics to their own AS: most of internal links are good
> 10GBits optic fiber while the connections to the outside world is mostly
> through smaller links. Bwauths can be tricked to believe that some
> relays have larger capacity because they have build circuits with relays
> internally connected to strong 10 Gbits. I don't know how the bwauths
> account for such thing? But, it is an another topic of discussion.

They do not.

>> Does shadow capture the consensus weight to advertised bandwidth ratio?
>> (That is, the actual load on the relay.)
>> Or the advertised bandwidth?
>> (The approximate actual capacity of the relay.)
> 
> Well, Shadow uses both. See doc of function
> https://github.com/shadow/shadow-plugin-tor/blob/master/tools/generate.py#L80
> used to generate topology and set up link speed from the relay's
> advertised bandwidth. Then, for the path selection, Shadow uses the
> measured bandwidth from torflow plugins or from a static v3bw file.

Ok, this is pretty close to the public network.

>> I think this proposal will actually be good for the network, because some
>> large consensus weight relays are overloaded. And giving them more middle
>> weight will reduce their overall load. (Middles get less load than guards.)
>> 
>> But I would like others to think through this, too.
> 
> Cool :) And regarding the main point of this proposal? Removing
> top-guard threat anonymity and hardening path compromise? Do you think
> that the method presented here is valuable?

You assume that many smaller relays are harder to run/compromise than fewer
large relays. I do not know if this is true. But it seems that limited IPv4
address space makes it partly true.

Maybe it will make malicious operators split large relays into smaller relays.
This is bad for client anonymity in general. But so are malicious operators.

> And, how this 'weight'
> compared to performance concerns?

It seems ok to me, if we can limit the increase in the slow tail.

> ...
>>>>> Here is how it
>>>>>  works:
>>>>> 
>>>>>  Every hour, directory authorities vote on a new consensus. Once the
>>>>>  votes are collected, the dirauths produce a deterministic network
>>>>>  consensus document containing information about each relay,
>>>>>  including the waterfilling bandwidth-weights produced from the
>>>>>  equations described above. e.g.:
>>>>> 
>>>>>  ...(more relays)
>>>>>  r relayguard34 PPTH75+WkHl1GGw07DRE/S+JNdo 1970-01-01 00:02:37
>>>>>  51.254.112.52 9111 9112
>>>>>  m lp08MLTivsSZPhpZQy88i8NPeBNx10tPKBpHZsM3gYM
>>>>>  s Fast Guard HSDir Running Stable V2Dir Valid
>>>>>  v Tor 0.2.6.7
>>>>>  w Bandwidth=10200
>>>>>  wfbw wgg=8029 wmg=1971.
>>>>>  r 4uthority3 PYnzXGQ+67m0WtO64qtJkwsUzME 1970-01-01 00:02:33 11.0.5.71
>>>>>  9111 9112
>>>>>  m d8G2/8UQzAN3a9DixCtmaivhfUFTvlFKAxCAV1xHVKk
>>>>>  s Authority Fast Guard HSDir Running Stable V2Dir Valid
>>>>>  v Tor 0.2.6.7
>>>>>  w Bandwidth=1890
>>>>>  wfbw wgg=10000 wmg=0.
>>>>>  ...(more relays)
>>>>> 
>>>>>  In this example, we see two relays having the Guard flag and their
>>>>>  new waterfilling bandwidth allocation given on the lines starting
>>>>>  with wfbw.
>>>> These are redundant, and could significantly expand the size of the
>>>> consensus, and consensus diffs. (Consensus weights are one of the
>>>> largest contributors to consensus diff size.)
>>> True, each time the consensus weights are modified, those waterfilling weights need to be recomputed. It adds one line per guard, which is about 2~3% of the size of the full consensus. Is such a thing a problem?
>> Changing bandwidths in each consensus makes consensus diffs *much* bigger.
>> 
>> See this proposal for details and an analysis:
>> https://gitweb.torproject.org/torspec.git/tree/proposals/276-lower-bw-granularity.txt
> 
> Ok. If I understand correctly, any bandwidth change would need a full
> re-calculation and a broadcast of the new weights (1 per guard) in the
> next consensus diff. I didn't imagine that it could be a problem. But if
> consensus diff size matters, then moving the weight calculation to the
> client code would fix it.

Consensus diff size does matter, particularly on mobile and slow connections.

>> The same issue applies to any bandwidth figures.
>> Would it be sufficient to publish a small ratio instead?
>> 
>> For example, you could publish lines like:
>> 
>> w Bandwidth=100000 wfratio=1
>> 
>> or
>> 
>> w Bandwidth=100000 wfratio=3
>> 
>> And have clients calculate wfbw as follows:
>> 
>> wfbw = Bandwidth * 2^-wfratio
>> 
>> This would be much smaller, much more compressible, and would also solve
>> some of your other issues around remainders, and also equal-weight guards
>> and stable sorts.
>> 
>> You would need to use equations something like this:
>> 
>> Compute a "pivot" N and a weight ratio Wggr_i assigned to
>> relay_i in such a way that:
>> 
>> Each high-bandwidth guard has a guard consensus weight within a factor of 2 of water level:
>> 
>>     (a) 2 * 2^-Wggr_(N+1) * BW_(N+1) > 2^-Wggr_i * BW_i >= 2^-Wggr_(N+1) * BW_(N+1) forall i in [1, N]
>> 
>> Each low-bandwidth guard is under the water level: (unchanged)
>> 
>>     (b) Wggr_i == 0 forall i in [N+1, K]
>> 
>> The total guard weight is within a ratio of the desired guard weight:
>> 
>>     (c) 2 * Wgg * G > sum_{i=1}^{K} 2^-Wggr_i * BW_i >= Wgg * G
>> 
>> The upper bound on (c) is actually a worst-case for a single-relay network.
>> We could get closer to Wgg * G by finding the lowest Wggr for the largest
>> relay that satisfies:
>> 
>>      (c.1) sum_{i=1}^{K} 2^-Wggr_i * BW_i >= Wgg * G
>> 
>> This might make the largest relay an exception to (a).
>> I'm not sure if we'll need this optimisation or not.
> 
> 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).
(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.

>>>> Why not calculate wmg on clients?
>>>> Why not calculate both wgg and wmg on clients?
>>>> 
>>> This is again a very good question: for such a critical feature (path selection), it is important that the directory auths have full power over the weight computation. If it happens that some change are needed, then the Tor network is updated in a straightforward way. This is not the case if those weights are computed in client code. In fact, I believe that one of the strength of this proposal is the oriented design towards the dirauths.
>> Consensus changes on dirauths:
>> * need to use consensus methods
>> * require a 6-12 month deployment time
>> * increases the size of all directory documents
>> * change the whole network
>> * if designed carefully, can be turned off using a network-wide parameter
>> 
>> Weight changes on clients:
>> * require a 3-6 month deployment time
>> * can be deployed to small numbers of clients
>> * if designed carefully, can be turned off using a network-wide parameter
>> 
>> I don't know which we'll prefer if we deploy this.
> 
> I have added a subsection in the proposal with those lines. Looks like
> we have to agree on this topic first before going in details in the
> implementation section?

It is ok to preset two alternatives with pros and cons in a proposal.
The implementation section can provide an algorithm for assigning
waterfilling weights. And then we can decide later where to run it.

>> ...

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

--
Tim / teor

PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B
ricochet:ekmygaiu4rzgsk6n
------------------------------------------------------------------------

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: Message signed with OpenPGP
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20180118/cb5af026/attachment-0001.sig>