[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [tor-dev] Proposal 276: Report bandwidth with lower granularity in consensus documents
On Sun, Feb 26, 2017 at 7:15 AM, teor <teor2345@xxxxxxxxx> wrote:
>
>> On 25 Feb 2017, at 03:25, Nick Mathewson <nickm@xxxxxxxxxxxxxx> wrote:
>>
>> Filename: 276-lower-bw-granularity.txt
>> Title: Report bandwidth with lower granularity in consensus documents
>> Author: Nick Mathewson
>> Created: 20-Feb-2017
>> Status: Open
>> Target: 0.3.1.x-alpha
>>
>> 1. Overview
>>
>> This document proposes that, in order to limit the bandwidth needed for
>> networkstatus diffs, we lower the granularity with which bandwidth is
>> reported in consensus documents.
>> ...
>> 3. Proposal
>>
>> I propose that we round the bandwidth values as they are placed in
>> the votes to two no more than significant digits.
>
> Misordered sentence this is
Fixed; thanks! ;)
>> In addition, for
>> values beginning with decimal "2" through "4", we should round the
>> first two digits the nearest multiple of 2. For values beginning
>> with decimal "5" though "9", we should round to the nearest multiple
>> of 5.
>
> Value Rounding Percentage Distinct Values
> 0-9 0 0% 10
> 10-20 0.5/10-0.5/20 5%-2.5% 10
> 20-50 1/20-1/50 5%-2% 15
> 50-100 2.5/50-2.5/100 5%-2.5% 10
> (repeat the pattern for 100-200 etc.)
> (lower bounds are inclusive, upper bounds are exclusive)
>
> This reduces each set of 1000 3 significant figure bandwidths to
> 35 distinct values.
>
> It's worth noting that the existing bandwidth authority scripts round to
> 3 significant figures, so the overall rounding is up to 5.5%.
>
>> This change does not require a consensus method; it will take effect
>> once enough authorities have upgraded.
>
> The change will take effect progressively as authorities upgrade: since
> the median value is used, when one authority upgrades, 1/5 of the
> bandwidths will be rounded (on average).
>
> Once all authorities upgrade, all bandwidths will be rounded like this.
I've used your wording here.
>> Is there a greedier smoothing algorithm that would produce better
>> results?
>
> Rounding to one significant digit changes 10 by up to 50%, so that's
> clearly unacceptable.
>
> If we wanted 12.5% to be the maximum change, we could round
> approximately double (with some adjustments for scale).
>
> For values beginning with decimal "1", we should round the first two
> digits the nearest multiple of 2. For values beginning with decimal "2"
> through "4", we should round the first two digits the nearest multiple
> of 5. For values beginning with decimal "5" though "9", we should
> round to one significant digit.
>
> Value Rounding Percentage Distinct Values
> 0-9 0 0% 10
> 10-20 1/10-1/20 10%-5% 5
> 20-50 2.5/20-2.5/50 12.5%-4% 6
> 50-100 5/50-5/100 10%-5% 5
> (repeat the pattern for 100-200 etc.)
> (lower bounds are inclusive, upper bounds are exclusive)
>
> This reduces each set of 1000 3 significant figure bandwidths to
> 16 distinct values.
>
> Would a scheme like this reduce the diffs by enough to make it
> worthwhile?
I simulated this scheme, and it didn't pan out: the average reduction
was less than 2% over the scheme currently in 276. (That is, if we
were already doing the 276 scheme, this change would save no more than
2%.)
>> Is there any reason to think this amount of smoothing would not
>> be save?
>
> s/save/safe/
>
> Given the existing variance is around 2%, and the existing rounding of
> 0.5%, rounding by 5% seems quite sensible.
>
> (Typical variance *between* bandwidth authorities is much more than
> this anyway.)
>
> It seems hard to game this scheme, and it would only result in a 5%
> boost anyway.
>
> The same arguments apply to rounding by up to 12.5%. Anything more
> seems risky.
>
>> Would a time-aware smoothing mechanism work better?
>
> Perhaps, but the complexity might outweigh the benefits.
>
> T
>
> --
> Tim Wilson-Brown (teor)
>
> teor2345 at gmail dot com
> PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B
> ricochet:ekmygaiu4rzgsk6n
> xmpp: teor at torproject dot org
> ------------------------------------------------------------------------
>
>
>
>
> _______________________________________________
> tor-dev mailing list
> tor-dev@xxxxxxxxxxxxxxxxxxxx
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
>
_______________________________________________
tor-dev mailing list
tor-dev@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev