[tor-dev] Graphs - Estimated Traffic Capacity

[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
-------------- 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/20151120/0f8be73c/attachment.sig>