[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Proposal: Path Selection Improvements
- To: or-dev@xxxxxxxxxxxxx
- Subject: Proposal: Path Selection Improvements
- From: Fallon <leftinspace@xxxxxxxxx>
- Date: Sat, 5 Jul 2008 18:46:34 -0700
- Delivered-to: archiver@xxxxxxxx
- Delivered-to: or-dev-outgoing@xxxxxxxx
- Delivered-to: or-dev@xxxxxxxx
- Delivery-date: Sat, 05 Jul 2008 21:46:39 -0400
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to :subject:mime-version:content-type; bh=EylBTBHfq9XwAoxIhE74v3JK+9hyqsjkBMtRBvrTeFE=; b=eWZYpG5ZWRfwp/WEaCA1mmbEXvJr40MTFS9IwKyb6S77OydjyZ1gg1yOSUKTVPnUTb xLuTCcuIj22iaRYeMpN3IWpTf1TabEr6Njyk4GCnqOfQaPkc2dPkKDa5fc606IybDUwE OjVn+YurEp5WLAJOKMEfsTLEg0iprfoS0cHlQ=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:mime-version:content-type; b=j/7M1UjvP/Z6aDWwArA3tAo+exaJyP53e4Gv7hOGwOwFRg3G9NPgPAcu47gR1ieXNI zcOyAIP0PjtNrpLltx52VhRrGkM5B6soST7opCQiy3b3k0ClaNfo0lgmoZwSdMaPgac0 8u5LBfpDDNHHO4arpDqOG6E/ltwC4sz+2wywA=
- Reply-to: or-dev@xxxxxxxxxxxxx
- Sender: owner-or-dev@xxxxxxxxxxxxx
Hi everyone,
Here's a proposal for improving path selection through collecting build time statistics. We're still collecting data, so it's quite short. Comments are appreciated.
Fallon
Filename: path-selection-improvements.txt
Title: Improving Tor Path Selection
Version:
Last-Modified:
Author: Fallon Chen, Mike Perry
Created: 5-Jul-2008
Status: Draft
Overview
The performance of paths selected can be improved by adjusting the
CircuitBuildTimeout and the number of guards. This proposal describes
a method of tracking buildtime statistics, and using those statistics to adjust the
CircuitBuildTimeout and the number of guards.
Motivation
Tor's performance can be improved by excluding those circuits that
have long buildtimes (and by extension, high latency). For those Tor users
who require better performance and have lower requirements for anonymity,
this would be a very useful option to have.
Implementation
Learning the CircuitBuildTimeout
Based on studies of build times, we found that the distribution of
circuit buildtimes appears to be a Pareto distribution. The number of
circuits to observe (ncircuits_to_observe) before changing the
CircuitBuildTimeout will be tunable. From our preliminary measurements,
it is likely that ncircuits_to_observe will be somewhere on the order of
1000. The values can be represented compactly in Tor in milliseconds as a
circular array of 16 bit integers. More compact long-term storage
representations can be implemented by simply storing a histogram with
50 millisecond buckets when writing out the statistics to disk.
Calculating the preferred CircuitBuildTimeout
Circuits that have longer buildtimes than some x% of the estimated CDF of
the Pareto distribution will be excluded. x will be tunable as well.
Circuit timeouts
In the event of a timeout, backoff values should include the 100-x% of
expected CDF of timeouts.
Also, in the event of network failure, the observation mechanism should
stop collecting timeout data.
Other notes
Since this follows a Pareto distribution, large reductions on the timeout
can be achieved without cutting off a great number of the total paths.
However, hard statistics on which cutoff percentage gives optimal
performance have not yet been gathered.
Issues
Impact on anonymity