On Mon, Apr 7, 2014 at 11:34 AM, George Kadianakis > So, based on your response, IIUC, the idea is that because young
guards are underutilized, we want to increase the probability of them being chosen in non-guard positions, so that they become more utilized till more people pick them as guards?
Right.
Some questions on the terminology you used:
a) What do you mean by 'last rotation period'? When you say "for fraction k of the last rotation period", you mean that if the authorities read consensuses for the past 12 months, and the relay R was up as a guard for 6 months, then k would be 6/12 == 0.5?
The "rotation period" is the average length of time between choosing guards. For example, with the current parameters (IIRC), clients discard a guard and choose a new one at a time uniformly chosen between 30 and 60 days. So the rotation period is 45 days = 45*24 hours = 1080 consensus votes, and essentially in each of those hours, 1/1080 of the clients choose a new guard. So the last rotation period's worth of status documents should be the only ones that matter for figuring out how heavily a node is used as a guard. For example, if a relay has had the guard flag for 15 days (=360 consensus documents) out of the last 45, then that relay has about k=360/1080 of the number of clients using it as a guard as it would have, if it had been a guard for the full 1080 hours.
Ah, I see. I originally misinterpreted what you meant by 'last rotation period'.
(N.B. I'm making an assumption that guard rotations will be uniformly distributed over the period. This should be safe in equilibrium, but might get kind of shaky when the period first increases to 9 months or whatever the final decision is)
Yep.
We also don't consider new releases of TBB/Tails (many users pick new entry guards), or sudden bulk arrival of users (botnets, real life events, etc.).
b) By (weight with the guard flag) you mean the result of: <consensus BW> * <consensus weight> ?
Is that right, or did I misunderstand you?
Yes.
Assuming the above terminology assumptions, I began trying to understand your formula. First of all, I was wondering how you ended up with it? Is this some standard form? I'm not very familiar with these things.
Well, the way the weights work is that they compute what fraction of guard bandwidth should be used for middle and exit traffic, assuming that the rest will be all used up by client-guard connections. That is, the weights are telling us to use (1-(<consensus middle weight> + <consensus exit weight>)) fraction of the guard's bandwidth for these connections.
But if a relay has only fraction k of its "guard bandwidth" used up this way, then (1-k) of this bandwidth should go back into the pool for other positions. I think that's what the formula does, but I could have it wrong. Does that make sense?
I see. That makes sense, I think.
I will ponder on this a bit more, and then edit the proposal.
(I would like to think a bit more about how accurate the assumption "relay has been a guard for 0.25 of the rotation period => relay has 0.25 of its bandwidth occupied for guard purposes")
Thanks!
On Fri, Apr 11, 2014 at 7:45 AM, George Kadianakis desnacked@riseup.net wrote:
I see. That makes sense, I think.
Good.
I will ponder on this a bit more, and then edit the proposal.
When/if you become convinced, let me know if you want me to draft a patch.
(I would like to think a bit more about how accurate the assumption "relay has been a guard for 0.25 of the rotation period => relay has 0.25 of its bandwidth occupied for guard purposes")
Here's another way to think of it: purely from a load balancing perspective, we would like clients that rotated guards when R had its guard flag to treat R like a guard, and clients that haven't to treat R like it's not a guard.
Using the approximation ("fraction of periods R had the guard flag" = "fraction of nodes that rotated when R had the guard flag") this means that "relay has been a guard for 0.25 of the rotation period => 0.25 of the clients weight the relay as a guard." Since we don't actually want to partition the network this way, the (weighted) average of the two weights will produce the same behavior.
Nicholas Hopper hopper@cs.umn.edu writes:
On Fri, Apr 11, 2014 at 7:45 AM, George Kadianakis desnacked@riseup.net wrote:
I see. That makes sense, I think.
Good.
I will ponder on this a bit more, and then edit the proposal.
When/if you become convinced, let me know if you want me to draft a patch.
I think it makes sense :)
A patch for the proposal would be useful. If you don't have time to do it, just tell me and I will do it myself.
(Also feel free to correct or add anything else to the proposal in your patch :) )
Thanks!
On Tue, Apr 15, 2014 at 6:35 AM, George Kadianakis desnacked@riseup.net wrote:
A patch for the proposal would be useful. If you don't have time to do it, just tell me and I will do it myself.
Here's a patch: https://www-users.cs.umn.edu/~hopper/single-guard-node.patch
On Thu, Apr 17, 2014 at 2:05 PM, Nicholas Hopper hopper@cs.umn.edu wrote:
On Tue, Apr 15, 2014 at 6:35 AM, George Kadianakis desnacked@riseup.net wrote:
A patch for the proposal would be useful. If you don't have time to do it, just tell me and I will do it myself.
Here's a patch: https://www-users.cs.umn.edu/~hopper/single-guard-node.patch
The proposal as patched is now proposal # 236.
yrs,
Nicholas Hopper hopper@cs.umn.edu writes:
On Tue, Apr 15, 2014 at 6:35 AM, George Kadianakis desnacked@riseup.net wrote:
A patch for the proposal would be useful. If you don't have time to do it, just tell me and I will do it myself.
Here's a patch: https://www-users.cs.umn.edu/~hopper/single-guard-node.patch
Thanks for the patch! FWIW, the original proposal + your patch got merged in torspec as proposal 236.
A nitpicking question:
A guard N that has been visible for V out of NNN*30*24 consensuses has had the opportunity to be chosen as a guard by approximately F = V/NNN*30*24 of the clients in the network, and the remaining 1-F fraction of the clients have not noticed this change. So when being chosen for middle or exit positions on a circuit, clients should treat N as if F fraction of its bandwidth is a guard (respectively, dual) node and (1-F) is a middle (resp, exit) node. Let Wpf denote the weight from the 'bandwidth-weights' line a client would apply to N for position p if it had the guard flag, Wpn the weight if it did not have the guard flag, and B the measured bandwidth of N in the consensus. Then instead of choosing N for position p proportionally to Wpf*B or Wpn*B, clients should
Why do you mention Wpn*B here? That is, in the sentence "Wpf*B or Wpn*B".
Since we are talking about picking a *guard* N for middle or exit positions a client would normally only use Wpf*B, right? Or am I confused?
choose N proportionally to F*Wpf*B + (1-F)*Wpn*B.
Nicholas Hopper hopper@cs.umn.edu writes:
On Tue, Apr 15, 2014 at 6:35 AM, George Kadianakis desnacked@riseup.net wrote:
A patch for the proposal would be useful. If you don't have time to do it, just tell me and I will do it myself.
Here's a patch: https://www-users.cs.umn.edu/~hopper/single-guard-node.patch
Just a note on updating the bandwidth-weights based on guardiness information. Proposal 236 states:
Similarly, when calculating the bandwidth-weights line as in section 3.8.3 of dir-spec.txt, directory authorities should treat N as if fraction F of its bandwidth has the guard flag and (1-F) does not. So when computing the totals G,M,E,D, each relay N with guard visibility fraction F and bandwidth B should be added as follows:
G' = G + F*B, if N does not have the exit flag M' = M + (1-F)*B, if N does not have the exit flag D' = D + F*B, if N has the exit flag E' = E + (1-F)*B, if N has the exit flag
I'd just like to mention that updating the global bandwidth-weights based on relay guardiness seems to assume that all clients will upgrade and start understanding guardiness instantly.
Since upgrade is probably going to be gradual, it probably means that more weight will be given to middle/exit position (M'/E') than it should.
Maybe the correct way to deploy this is to first merge the client-side to little-t-tor, then wait till the feature appear in TBB, and then upgrade the authorities to report guardiness information. But maybe this is too slow deployment... Not sure.
-
George Kadianakis -
Nicholas Hopper -
Nick Mathewson