Correct formulas for exit weights [was Re: Exit Balancing Patch]

[Roger Dingledine]

On Sat, Jul 28, 2007 at 01:34:54AM -0400, Nick Mathewson wrote:
> [I'm writing this parenthetical after having gone through the
>  derivation.  Summary: I got the same result as Mike.]

Great. Can you extract the part of Mike's suggested patch that makes the
math right, verify that it actually does the right thing, and apply it?

> So long as we're doing this, let's do it properly and expand our model
> a little, to consider cannibalized circuits and non-3-hop paths.
> These questions are mostly for Roger, but anybody else who has
> empirical data should step up too:
> 
> 1) Roger, can you comment on the average path length in practice?  Is it
>    close enough to that we should just set L=3?

Yes, I think it's pretty much three.

Tor uses four hop paths when you use the .exit notation, or when you
request a site that runs on the same IP address as a Tor node that allows
exit to that site. There are a few other minor cases but I don't think
they matter.

I'll let you know if I realize I'm wrong, but don't wait up.

> 2) What fraction of circuits are cannibalized?  If all L-hop circuits
>    that already end at an Exit are (with probability Pc) cannibalized
>    and extended to another Exit, we now have
>      BE = (1+Pc)*B + B*(L-1) * Pe,
>    which changes our analysis a little.

Again, the only ones that are extended to a fourth hop are the cases
above.

Also notice that these equations neglect the concept of "internal"
circuits (see path-spec.txt for definitions) that are used for interacting
with hidden services. But I think it's also safe to assume that roughly
none of the Tor bandwidth relates to hidden services.

--Roger