Proposal: Two Hop Paths

[Mike Perry]

Thus spake Paul Syverson (syverson at itd.nrl.navy.mil):

> My guess is that two-hop-Tor-at-its-best is not perceptibly faster or
> otherwise better than Tor-classic-at-its-best. Likewise for
> two-hop-Tor-at-its-worst vs. Tor-classic-at-its-worst. Thus, the
> entire question turns on the expected perceived performance, i.e., the
> distribution of perceived-slow circuits across all circuits. Now I
> will totally make up some numbers for purpose of illustration.  If,
> e.g., 95 percent of circuits through two-hop Tor (2ht) are perceived
> as acceptably fast, vs., e.g., 5 percent of circuits for Tor Classic
> (3ht), then it seems at least reasonable that usage from perceived
> better usability will increase significantly.  Even then there
> probably needs to be some argument? But why should we expect such a
> dramatic difference. My guess is that the limitations are mostly
> caused by the slowest pipe or OR in the chain for any given circuit
> (yes I know it's actually much more complicated than that). If even
> very roughly correct, then the improvement in user perception is
> not going to impress someone who find Tor unacceptably slow now.  Even
> if that idea that circuits generally have a single bottleneck
> is wrong but the effect of this change is rather to go from,
> e.g., 60 percent of circuits for a given user being considered too
> slow by that user to 35 percent of circuits, why do we think the user
> will have any change of opinion about bad Tor performance at all?
> It's possible that the usability improvements from this proposal will
> be dramatic (though I personally doubt it). But for the moment there
> is not even a handwavy argument to support that view. And a
> much-more-than-handwavy argument should be given before consider so
> dramatic a change.

This is an excellent point. I will address this in a little more
detail in the proposal, and will eventually do a few speedracer runs
to back up the analysis empirically, but the general idea is that the
performance will come from 5 factors:

1. Decreased latency from less queuing from the extra hop
2. Decreased latency from less total distance from the extra hop
3. Decreased load on the network -> increased capacity at slowest hops
4. Decreased probability of choosing a slow hop in a 2 hop circuit
5. Decreased probability of crossing slow peering links (oceans, etc) 

I think the bulk of the performance gain will come from points 1 and
2. Latency is a killer factor in user pereception of performance.
Johannes is also working on mechanisms to address points 1, 2 and 5
also, but there is nothing about either approach that prevents them
from both being used.

Unfortunately, the proposal is blocked on a backport of Bug #440*, and
its subsequent adoption, which I believe is also a significant
performance bottleneck and prevents me from taking accurate
measurments to determine the proper failure ratios to flag active
adversaries.

So it's possible that we will have time to determine if Johannes's
work improves latency+queuing enough to be sufficient before
implementing the proposal in full. But it's likely his work will also
have anonymity implicants that may require it to be only enabled for
the low-risk user class addressed by this proposal anyways.


* Bug 440 is an issue with load balancing guard nodes. Guard nodes in
Tor prior to svn r10493 were chosen uniformly:
http://bugs.noreply.org/flyspray/index.php?do=details&id=440

I believe this bug is the reason why nodes in the 35-60 perentiles
exhibit higher failure rates and timeouts than both faster and slower
nodes, but obviously there is no proof for this until I run another
scan after the bug is backported to 0.1.2.x and adopted widely:
http://archives.seul.org/or/talk/Dec-2006/msg00123.html



-- 
Mike Perry
Mad Computer Scientist
fscked.org evil labs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20070609/c357b99c/attachment.pgp>