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.
- 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.
For each of them, set their total capacity to min(avg BW, observed BW).
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)
- 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_probWe 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.
- 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.
- 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@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev