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@lists.torproject.org > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
_______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
