[tor-dev] Optimising Tor node selection probabilities

[Paul Syverson]

On Sun, Oct 12, 2014 at 06:43:10AM +1100, teor wrote:
> 
> On 11 Oct 2014, at 23:00 , tor-dev-request at lists.torproject.org wrote:
> 
> > Date: Fri, 10 Oct 2014 14:33:52 +0100
> > From: Steven Murdoch <Steven.Murdoch at cl.cam.ac.uk>
> > 
> > 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