[tor-dev] Graphs - Estimated Traffic Capacity

[Moritz Wedel]

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?

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20151124/6d6508c5/attachment.html>