[tor-dev] Graphs - Estimated Traffic Capacity

[David Goulet]

On 24 Nov (10:10:44), Moritz Wedel wrote:
> Hi David,
> 
> this sound really interesting!
> Im working on an evaluation of hidden service performance, trying to
> find some improvements. An algorithm to estimate the network capacities
> is a great tool, to evaluate what will happen if we would change some
> circuit parameters. This is why I would like to ask you for your code
> basis. Is there a git?

I do plan to make a git out of all scripts I use for those graphs... time
factor here but I'll reply back to this thread hopefully very soon with more
info.

(It's also a great exercice to use the algorithm below and script it yourself
to see if you get to the same results :)

Thanks!
David

> 
> Thank u in advanced.
> Moritz (Institut für Informatik, HU Berlin)
> 
> Am 20.11.2015 um 19:38 schrieb David Goulet:
> > Hello everyone!
> >
> > I would like to share this graph I've been working on along side with Aaron
> > Johnson (thanks to him for the algorithm I'll be describing).
> >
> > This shows both the maximum additional and total traffic the network can
> > sustain for both HS and Exit. The "additional" traffic here means that we
> > consider the current load on the network thus the additional value is what can
> > be added more on top of the current traffic.
> >
> > http://ygzf7uqcusp4ayjs.onion/tor-health/tor-health/bandwidth_capacity.html
> >
> > (Please ignore the initial downward spike, technical issue)
> >
> > Here is the algorithm we are using for this. It's in no ways an accurate value
> > but rather an estimation as you will see with the following algorithm to
> > compute the traffic capacity you see.
> >
> >   1. Using the latest consensus, build a list of relays that are Running, Valid
> >   and Fast (weight selection only picks relays with Fast flag). Then compute
> >   their positionnal consensus weights.
> >
> >   2. For each of them, set their total capacity to min(avg BW, observed BW).
> >
> >   3. For each of them, compute the unused capacity that is use the extrainfo
> >   descriptor read/write bytes history for the amount of traffic used and
> >   substract that to the total capacity.
> >
> >     max(mean(write_history_values) / write_interval,
> >         mean(read_history_values) / read_interval)
> >
> >   4. For HS traffic, that is a 6-hops circuit, we go over all relays and find
> >   the relay that has the lowest unused capacity divided by it's probability of
> >   being picked in the Guard/Middle position:
> >
> >     picked_prob = (guard_weight * 2) + (middle_weight * 4)
> >     unused = relay.unused_capacity / picked_prob
> >
> >   We use time 2 here since there are two guards in the 6 hops circuit and 4
> >   middle nodes. We get the minimum value between each relays.
> >
> >   5. The minimum "unused" value times the picked_prob is the amount of bytes
> >   that we'll give to all relays thus reducing their unused capacity:
> >
> >     relay.unused_capacity -= (min_unused * picked_prob)
> >
> >   At each iteration of the algorithm, this will make at least one relay go to 0
> >   unused capacity so when this happens, remove that relay from the set of
> >   relays to be picked. Once we can't pick a relay anymore for the 6 hops
> >   circuit (that is no more guards or middle), we stop.
> >
> >   6. Add min_unused value to the total number of bytes. Goto step 4.
> >
> > Ok... this can maybe be not that trivial to understand at first, feel free to
> > ask questions but the basic idea is that at each iteration of the algorithm you
> > spread a specific amount of bytes to each relay depending on the probability of
> > being picked until you have no more relays capacity for such a circuit.
> >
> > For the "Max Total" traffic, the relay.unused_capacity is equal to the relay
> > capacity. For Exit traffic, we do the same logic but with a 3 hops circuit
> > where each position is multiplied by 1 since there is one guard, middle and
> > exit (in normal circumstances).
> >
> > I know that we have sometimes 1, 4, 5, 6 or 7 hops circuit but the general case
> > is considered here and we have no stats on how frequent those unusual circuits
> > are.
> >
> > Anyway, if you think this algorithm could be improved, please respond. If you
> > think this algorithm is wrong, please respond. If you can reproduce the result
> > on your own with this algo, omg please respond! :) The above could be totally
> > wrong but hopefully we did a fairly good job. Please remember, this is an
> > estimate. :)
> >
> > Thanks!
> > David
> >
> >
> > _______________________________________________
> > tor-dev mailing list
> > tor-dev at lists.torproject.org
> > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
> 

> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 603 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20151126/a7659b0a/attachment.sig>