I’ve just published a new paper on selecting the node selection probabilities (consensus weights) in Tor. It takes a queuing-theory approach and shows that what Tor used to do (distributing traffic to nodes in proportion to their contribution to network capacity) is not the best approach.
Counter-intuitively the paper shows that some of the slowest nodes should not be used at all, because if they are used they will slow down the average performance for all users. The proportion of nodes which shouldn’t be used depends on the relationship between network usage and network capacity, so will vary over time.
It’s not clear that there is a closed-form solution to the problem of calculating node selection probabilities (I couldn’t find one), but this paper shows that the optimisation surface is convex and so gradient-based optimisation methods will find the global optimum (rather than some local optimum which depends on the starting position of the optimisation process).
Although the process outlined in the paper requires knowing the relationship between network capacity and usage, it isn’t highly sensitive to minor inaccuracies in measuring this value. For example if it is assumed the network is loaded at 50% then the solution will outperform Tor’s old approach provided the true network load is between 0% and 60%.
After this work was done, Tor moved to actively measuring the network performance and manipulating the consensus weights in response to changes. This seems to have ended up with roughly the same outcome. The advantage of Tor’s new approach is that it doesn’t require knowing network usage and node capacity; however the disadvantage is that it can only react slowly to changes in network characteristics.
For more details, see the paper: http://www.cl.cam.ac.uk/~sjm217/papers/#pub-el14optimising
Note that this is published in IET Electronics Letters, which is a bit different to the usual Computer Science publication venues. It jumps straight into the maths and leaves it to the reader to understand the background and implications. The advantage is that it’s 2 pages long; the disadvantage is that to understand it you need to know a reasonable amount about Tor and queuing theory to make much sense of it.
Best wishes, Steven
Will a longer version of this paper be coming out, particularly one for developers?
-V
On 11 Oct 2014, at 01:14, Virgil Griffith i@virgil.gr wrote:
Will a longer version of this paper be coming out, particularly one for developers?
I don’t have any immediate plans to do so, as my current thinking is it would end up being a queuing theory tutorial with the current paper appended, and plenty of people have done good queuing theory tutorials. It could be that I could come up with a slightly compressed tutorial, but really anyone who is interested in network performance needs to have a reasonably good understanding of queuing theory.
The work started off as some experiments using a simple optimisation method – gradient descent [1]. This method finds local minima, but is only guaranteed to find the global minimum if the function is convex (because the local minimum of a convex function for any starting point is the global minimum).
The function being minimised is the average latency for a cell entering the Tor network, and what we are varying in order to minimise latency is the distribution of traffic over nodes.
So the paper is mainly about finding out whether the function which gives the average latency, given a particular traffic distribution policy, is convex. It turns out that it is and so gradient descent is a valid method. If you don’t want to deal with the maths proving this result then you can just skip the middle of the paper which discusses Hessian matrices.
When you run gradient descent you end up with Figure 1 which shows that for the slow nodes the optimal approach is to not use them. The intuitive reason is that a cell spends some time in a queue and some time being processed once it reaches the head of the queue (processing consists of it being decrypted then put on the wire). For slow nodes, the processing time is so long, that even if the node’s queue is empty would be better to find a fast node and give it the cell instead. The cell will have to wait in a queue but processing time of a fast node is so much faster that it’s worth it.
The big open question in the paper is about the assumptions. Queuing theory is very powerful, but it quickly gets very ugly when you move away from simple models of reality. This paper uses M/D/1 [3] which is a reasonable approximation but not a perfect one. Moving even to a more slightly more realistic approximation makes the maths get much more difficult, so we didn’t do it.
Best wishes, Steven
[1] http://mathworld.wolfram.com/MethodofSteepestDescent.html [2] http://en.wikipedia.org/wiki/Maxima_and_minima [3] http://en.wikipedia.org/wiki/M/D/1_queue
-
Steven Murdoch -
Virgil Griffith