Re: [tor-dev] Optimising Tor node selection probabilities
On 11 Oct 2014, at 01:14, Virgil Griffith 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 ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Optimising Tor node selection probabilities
On Sun, Oct 12, 2014 at 06:43:10AM +1100, teor wrote: > > On 11 Oct 2014, at 23:00 , tor-dev-requ...@lists.torproject.org wrote: > > > Date: Fri, 10 Oct 2014 14:33:52 +0100 > > From: Steven Murdoch > > > > 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. > > [snip] > > > > For more details, see the paper: > > http://www.cl.cam.ac.uk/~sjm217/papers/#pub-el14optimising > > [snip] > > > This is fantastic, Steven - and although we've changed Tor's > consensus weights algorithm, we still waste bandwidth telling > clients about relays that wold slow the network down. > > Your result further supports recent proposals to remove the slowest > relays from the consensus entirely. > I find this theoretically very interesting and an important contribution, but I'm less sure what conclusions it supports for Tor as implemented and deployed. A first major question is that the results assume FIFO processing of cells at each relay, but Tor currently uses EWMA scheduling and is now moving even further from FIFO as KIST is being adopted. There are other questions, e.g., that the paper assumes it is safe to ignore circuits and streams (not just for FIFO vs. prioritized processing but for routing and distribution of cells across relays as well---or said differently, Tor's onion routing, but this isn't). But I'm thinking if I'm correct even about this one point, then it would be extremely premature to directly apply the conclusions of this work to practical proposals for improving Tor performance. Then of course there are those pesky security implications to worry about ;>) My comments are not meant at all to question the value of the paper, which I think contributes to our understanding of such networks. Rather I am cautioning against applying its results outside the scope of its assumptions. Cf. the KIST paper, which itself cites the EWMA introduction paper and subsequent related work. http://www.nrl.navy.mil/itd/chacs/sites/edit-www.nrl.navy.mil.itd.chacs/files/pdfs/14-1231-2094.pdf or http://www.robgjansen.com/publications/kist-sec2014.pdf aloha, Paul ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Optimising Tor node selection probabilities
On 11 Oct 2014, at 23:00 , tor-dev-requ...@lists.torproject.org wrote: > Date: Fri, 10 Oct 2014 14:33:52 +0100 > From: Steven Murdoch > To: tor-dev@lists.torproject.org > Subject: [tor-dev] Optimising Tor node selection probabilities > Message-ID: > Content-Type: text/plain; charset=windows-1252 > > 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 This is fantastic, Steven - and although we've changed Tor's consensus weights algorithm, we still waste bandwidth telling clients about relays that wold slow the network down. Your result further supports recent proposals to remove the slowest relays from the consensus entirely. teor pgp 0xABFED1AC hkp://pgp.mit.edu/ https://gist.github.com/teor2345/d033b8ce0a99adbc89c5 http://0bin.net/paste/Mu92kPyphK0bqmbA#Zvt3gzMrSCAwDN6GKsUk7Q8G-eG+Y+BLpe7wtmU66Mx signature.asc Description: Message signed with OpenPGP using GPGMail ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Optimising Tor node selection probabilities
Will a longer version of this paper be coming out, particularly one for developers? -V ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
[tor-dev] Optimising Tor node selection probabilities
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 ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
