Proposal: Load Balancing with Overhead Parameters
This proposal aims to allow us to load balance properly between Guard, Middle, and Exit nodes with the addition of padding traffic to the network. Canonical proposal current lives in my load_balancing-squashed branch: https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/xxx-... Here is the text in-line, for ease of commenting on-list: ============================================================== Filename: xxx-load-balancing-with-overhead.txt Title: Load Balancing with Overhead Parameters Authors: Mike Perry Created: 01 January 2016 Status: Draft 0. Motivation In order to properly load balance in the presence of padding and non-negligible amounts of directory and hidden service traffic, the load balancing equations in Section 3.8.3 of dir-spec.txt are in need of some modifications. In addition to supporting the idea of overhead, the load balancing equations can also be simplified by treating Guard+Exit nodes as Exit nodes in all cases. This causes the 9 sub-cases of the current load balancing equations to consolidate into a single solution, which also will greatly simplify the consensus process, and eliminate edge cases such as #16255[1]. 1. Overview For padding overhead due to Proposals 251 and 254, and changes to hidden service path selection in Proposal 247, it will be useful to be able to specify a pair of parameters that represents the additional traffic present on Guard and Middle nodes due to these changes. The current load balancing equations unfortunately make this excessively complicated. With overhead factors included, each of the 9 subcases goes from being a short solution to over a page of calculations for each subcase. Moreover, out of 8751 hourly consensus documents produced in 2015[2], only 78 of them had a non-zero weight for using Guard+Exit nodes in the Guard position (weight Wgd), and most of those were well under 1%. The highest weight for using Guard+Exits in the Guard position recorded in 2015 was 2.62% (on December 10th, 2015). This means clients that chose a Guard node during that particular hour used only 2.62% of Guard+Exit flagged nodes' bandwidth when performing a bandwidth-weighted Guard selection. All clients that chose a Guard node during any other hour did not consider Guard+Exit nodes at all as potential candidates for their Guards. This indicates that we can greatly simplify these load balancing equations with little to no change in diversity to the network. 2. Simplified Load Balancing Equations Recall that the point of the load balancing equations in section 3.8.3 of dir-spec.txt is to ensure that an equal amount of client traffic is distributed between Guards, Middles, Exits, and Guard+Exits, where each flag type can occupy one or more positions in a path. This allocation is accomplished by solving a system of equations for weights for flag position selection to ensure equal allocation of client traffic for each position in a circuit. If we ignore overhead for the moment and treat Guard+Exit nodes as Exit nodes, then this allows the simplified system of equations to become: Wgg*G == M + Wme*E + Wmg*G # Guard position == middle position Wgg*G == Wee*E # Guard position == equals exit position Wmg*G + Wgg*G == G # Guard allocation weights sum to 1 Wme*E + Wee*E == E # Exit allocation weights sum to 1 This system has four equations and four unknowns, and by transitivity we ensure that allocated capacity for guard, middle, and exit positions are all equal. Unlike the equations in 3.8.3 of dir-spec.txt, there are no special cases to the solutions of these equations because there is no shortage of constraints and no decision points for allocation based on scarcity. Thus, there is only one solution. Using SymPy's symbolic equation solver (see attached script) we obtain: E + G + M E + G + M 2*E - G - M 2*G - E - M Wee: ---------, Wgg: ---------, Wme: -----------, Wmg: ------------ 3*E 3*G 3*E 3*G For the rest of the flags weights, we will do the following: Dual-flagged (Guard+Exit) nodes should be treated as Exits: Wgd = 0, Wmd = Wme, Wed = Wee Directory requests use middle weights: Wbd=Wmd, Wbg=Wmg, Wbe=Wme, Wbm=Wmm Handle bridges and strange exit policies: Wgm=Wgg, Wem=Wee, Weg=Wed 2.1. Checking for underflow and overflow In the old load balancing equations, we required a case-by-case proof to guard against overflow and underflow, and to decide what to do in the event of various overflow and underflow conditions[3]. Even still, the system proved fragile to changes, such as the implementation of Guard uptime fractions[1]. Here, with the simplified equations, we can plainly see that the only time that a negative weight can arise is in Wme and Wmg, when 2*E < G+M or when 2*G < E+M. In other words, only when Exits or Guards are scarce. Similarly, the only time that a weight exceeding 1.0 can arise is in Wee and Wgg, which also happens when 2*E < G+M or 2*G < E+M. This means that parameters will always overflow in pairs (Wee and Wme, and/or Wgg and Wmg). In both these cases, simply clipping the parameters at 1 and 0 provides as close of a balancing condition as is possible, given the scarcity. 3. Load balancing with Overhead Parameters Intuitively, overhead due to padding and path selection changes can be represented as missing capacity in the relevant position. This means that in the presence of a Guard overhead fraction of G_o and a Middle overhead fraction of M_o, the total fraction of actual client traffic carried in those positions is (1-G_o) and (1-M_o), respectively. Then, to achieve a balanced allocation of traffic, we consider only the actual client capacity carried in each position: # Guard position minus overhead matches middle position minus overhead: (1-G_o)*(Wgg*G) == (1-M_o)*(M + Wme*E + Wmg*G) # Guard position minus overhead matches exit position: (1-G_o)*(Wgg*G) == 1*(Wee*E) # Guard weights still sum to 1: Wmg*G + Wgg*G == G # Exit weights still sum to 1: Wme*E + Wee*E == E Solving this system with SymPy unfortunately yields some unintuitively simplified results. For each weight, we first show the SymPy solution, and then factor that solution into a form analogous to Section 2: -(G_o - 1)*(M_o - 1)*(E + G + M) Wee: --------------------------------------- E*(G_o + M_o - (G_o - 1)*(M_o - 1) - 2) (1 - G_o)*(1 - M_o)*(E + G + M) Wee: --------------------------------------- E*(2 - G_o - M_o + (1 - G_o)*(1 - M_o)) (M_o - 1)*(E + G + M) Wgg: --------------------------------------- G*(G_o + M_o - (G_o - 1)*(M_o - 1) - 2) (1 - M_o)*(E + G + M) Wgg: --------------------------------------- G*(2 - G_o - M_o + (1 - G_o)*(1- M_o)) -E*(M_o - 1) + G*(G_o - 1)*(-M_o + 2) - M*(M_o - 1) Wmg: --------------------------------------------------- G*(G_o + M_o - (G_o - 1)*(M_o - 1) - 2) (2 - M_o)*G*(1 - G_o) - M*(1 - M_o) - E*(1 - M_o) Wmg: --------------------------------------------------- G*(2 - G_o - M_o + (1 - G_o )*(1 - M_o)) E*(G_o + M_o - 2) + G*(G_o - 1)*(M_o - 1) + M*(G_o - 1)*(M_o - 1) Wme: ----------------------------------------------------------------- E*(G_o + M_o - (G_o - 1)*(M_o - 1) - 2) (2 - G_o - M_o)*E - G*(1 - G_o)*(1 - M_o) - M*(1 - G_o)*(1 - M_o) Wme: ----------------------------------------------------------------- E*(2 - G_o - M_o + (1 - G_o)*(1 - M_o)) A simple spot check with G_o = M_o = 0 shows us that with zero overhead, these solutions become identical to the solutions in Section 2 of this proposal. The final condition that we need to ensure is that these weight values never become negative or greater than 1.0[3]. 3.1. Ensuring against underflow and overflow Note that if M_o = G_o = 0, then the solutions and the overflow conditions are the same as in Section 2. Unfortunately, SimPy is unable to solve multivariate inequalities, which prevents us from directly deriving overflow conditions for each variable independently (at least easily and without mistakes). Wolfram Alpha is able to derive closed form solutions to some degree for this, but they are more complicated than checking the weights for underflow and overflow directly. However, for all overflow and underflow cases, simply warning in the event of overflow or underflow in the weight variable solutions above is equivalent anyway. Optimal load balancing given this scarcity should still result if we clip the resulting solutions to [0, 1.0]. It will be wise in the implementation to test the overflow conditions with M_o = G_o = 0, and with their actual values. This will allow us to know if the overflow is a result of inherent unbalancing, or due to input overhead values that are too large (and need to be reduced by, for example, reducing padding). 4. Consensus integration 4.1. Making use of the Overhead Factors In order to keep the consensus process simple on the Directory Authorities, the overhead parameters represent the combined overhead from many factors. The G_o variable is meant to account for sum of directory overhead, netflow padding overhead, future two-hop padding overhead, and future hidden service overhead (for cases where Guard->Middle->Exit circuits are not used). The M_o variable is meant to account for multi-hop padding overhead, hidden service overhead, as well as an overhead for any future two-hop directory connections (so that we can consolidate Guards and Directory guard functionality into a single Guard node). There is no need for an E_o variable, because even if there were Exit-specific overhead, it could be represented by an equivalent reductions in both G_o and M_o instead. Since all relevant padding and directory overhead information is included in the extra-info documents for each relay, the M_o and G_o variables could be computed automatically from these extra-info documents during the consensus process. However, it is probably wiser to keep humans in the loop and set them manually as consensus parameters instead, especially since we have not previously had to deal with serious adversarial consequences from malicious extra-info reporting. For clarity, though, it may be a good idea to separate all of the components of M_o and G_o into separate consensus parameters, and combine them (via addition) in the final equations. That way it will be easier to pinpoint the source of any potential overflow issues. This separation will also enable us to potentially govern padding's contribution to the overhead via a single tunable value. 4.2 Integration with Guardfraction The GuardFraction changes in Proposal 236 and #16255 should continue to work with these new equations, so long as the total T, G, and M values are counted after the GuardFraction multiplier has been applied. 4.3. Guard flag assignment Ideally, the Guard flag assignment process would also not count Exit-flagged nodes when determining the Guard flag uptime and bandwidth cutoffs, since we will not be using Guard+Exit flagged nodes as Guard nodes at all when this change is applied. This will result in more accurate thresholds for Guard node status, as well as better control over the true total amount of Guard bandwidth in the consensus. 1. https://trac.torproject.org/projects/tor/ticket/16255 2. https://collector.torproject.org/archive/relay-descriptors/consensuses/ 3. http://tor-dev.torproject.narkive.com/17H9FewJ/correctness-proof-for-new-ban... Appendix A: SymPy Script for Balancing Equation Solutions #!/usr/bin/python from sympy.solvers import solve from sympy import simplify, Symbol, init_printing, pprint # Sympy variable declarations (G,M,E,D) = (Symbol('G'),Symbol('M'),Symbol('E'),Symbol('D')) (Wgd,Wmd,Wed,Wme,Wmg,Wgg,Wee) = (Symbol('Wgd'),Symbol('Wmd'),Symbol('Wed'), Symbol('Wme'),Symbol('Wmg'),Symbol('Wgg'), Symbol('Wee')) (G_o, M_o) = (Symbol('G_o'),Symbol('M_o')) print "Current Load Balancing Equation Solutions, Case 1:" pprint(solve( [Wgg*G + Wgd*D - (M + Wmd*D + Wme*E + Wmg*G), Wgg*G + Wgd*D - (Wee*E + Wed*D), Wed*D + Wmd*D + Wgd*D - D, Wmg*G + Wgg*G - G, Wme*E + Wee*E - E, Wmg - Wmd, 3*Wed - 1], Wgd, Wmd, Wed, Wme, Wmg, Wgg, Wee)) print print "Case 1 with guard and middle overhead: " pprint(solve( [(1-G_o)*(Wgg*G + Wgd*D) - (1-M_o)*(M + Wmd*D + Wme*E + Wmg*G), (1-G_o)*(Wgg*G + Wgd*D) - (Wee*E + Wed*D), Wed*D + Wmd*D + Wgd*D - D, Wmg*G + Wgg*G - G, Wme*E + Wee*E - E, Wmg - Wmd, 3*Wed - 1], Wgd, Wmd, Wed, Wme, Wmg, Wgg, Wee)) print "\n\n" print "Elimination of combined Guard+Exit flags (no overhead): " pprint(solve( [(Wgg*G) - (M + Wme*E + Wmg*G), (Wgg*G) - 1*(Wee*E), Wmg*G + Wgg*G - G, Wme*E + Wee*E - E], Wme, Wmg, Wgg, Wee)) print print "Elimination of combined Guard+Exit flags (Guard+middle overhead): " combined = solve( [(1-G_o)*(Wgg*G) - (1-M_o)*(M + Wme*E + Wmg*G), (1-G_o)*(Wgg*G) - 1*(Wee*E), Wmg*G + Wgg*G - G, Wme*E + Wee*E - E], Wme, Wmg, Wgg, Wee) pprint(combined)
On 13 Jan 2016, at 00:53, Mike Perry <mikeperry@torproject.org> wrote:
This proposal aims to allow us to load balance properly between Guard, Middle, and Exit nodes with the addition of padding traffic to the network. ... 1. Overview
For padding overhead due to Proposals 251 and 254, and changes to hidden service path selection in Proposal 247, it will be useful to be able to specify a pair of parameters that represents the additional traffic present on Guard and Middle nodes due to these changes.
I don't know if it's worth noting that proposals 252 and 260 (the Single Onion Services variants) will reduce traffic to guard and middle nodes, as they remove the nodes between the hidden service and client-controlled endpoint (rendezvous point in Rendezvous Single Onion Services, extend point in Single Onion Services). I think these will just be part of the overhead parameters?
... 2. Simplified Load Balancing Equations
Recall that the point of the load balancing equations in section 3.8.3 of dir-spec.txt is to ensure that an equal amount of client traffic is distributed between Guards, Middles, Exits, and Guard+Exits, where each flag type can occupy one or more positions in a path. This allocation is accomplished by solving a system of equations for weights for flag position selection to ensure equal allocation of client traffic for each position in a circuit.
If we ignore overhead for the moment and treat Guard+Exit nodes as Exit nodes, then this allows the simplified system of equations to become:
Wgg*G == M + Wme*E + Wmg*G # Guard position == middle position Wgg*G == Wee*E # Guard position == equals exit position Wmg*G + Wgg*G == G # Guard allocation weights sum to 1 Wme*E + Wee*E == E # Exit allocation weights sum to 1
This system has four equations and four unknowns, and by transitivity we ensure that allocated capacity for guard, middle, and exit positions are all equal. Unlike the equations in 3.8.3 of dir-spec.txt, there are no special cases to the solutions of these equations because there is no shortage of constraints and no decision points for allocation based on scarcity. Thus, there is only one solution. Using SymPy's symbolic equation solver (see attached script) we obtain:
E + G + M E + G + M 2*E - G - M 2*G - E - M Wee: ---------, Wgg: ---------, Wme: -----------, Wmg: ------------ 3*E 3*G 3*E 3*G
For the rest of the flags weights, we will do the following:
Dual-flagged (Guard+Exit) nodes should be treated as Exits: Wgd = 0, Wmd = Wme, Wed = Wee
Directory requests use middle weights: Wbd=Wmd, Wbg=Wmg, Wbe=Wme, Wbm=Wmm
Handle bridges and strange exit policies: Wgm=Wgg, Wem=Wee, Weg=Wed
I think this analysis assumes that all paths in the Tor network are 3-hop paths. What about the 4-hop paths created by circuit cannibalisation? (We don't actually know what proportion of the Tor network has 3-hop vs 4-hop paths.) Depending on whether an exit or internal circuit is cannibalised, they can look like: G M E E G M M E And what about hidden service paths (paths that include two middle nodes?) G M M Or, if cannibalised from an exit or internal circuit: G M E M G M M M Again, I think these will just be part of the overhead parameters?
…
Tim Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F
Tim Wilson-Brown - teor:
On 13 Jan 2016, at 00:53, Mike Perry <mikeperry@torproject.org> wrote: 1. Overview
For padding overhead due to Proposals 251 and 254, and changes to hidden service path selection in Proposal 247, it will be useful to be able to specify a pair of parameters that represents the additional traffic present on Guard and Middle nodes due to these changes.
I don't know if it's worth noting that proposals 252 and 260 (the Single Onion Services variants) will reduce traffic to guard and middle nodes, as they remove the nodes between the hidden service and client-controlled endpoint (rendezvous point in Rendezvous Single Onion Services, extend point in Single Onion Services).
I think these will just be part of the overhead parameters?
Probably, though this will require us to have some estimation on the amount of network traffic using these services. Will they be broken out separately in the extra-info hidden service stats?
2. Simplified Load Balancing Equations
Recall that the point of the load balancing equations in section 3.8.3 of dir-spec.txt is to ensure that an equal amount of client traffic is distributed between Guards, Middles, Exits, and Guard+Exits, where each flag type can occupy one or more positions in a path. This allocation is accomplished by solving a system of equations for weights for flag position selection to ensure equal allocation of client traffic for each position in a circuit.
If we ignore overhead for the moment and treat Guard+Exit nodes as Exit nodes, then this allows the simplified system of equations to become:
Wgg*G == M + Wme*E + Wmg*G # Guard position == middle position Wgg*G == Wee*E # Guard position == equals exit position Wmg*G + Wgg*G == G # Guard allocation weights sum to 1 Wme*E + Wee*E == E # Exit allocation weights sum to 1
I think this analysis assumes that all paths in the Tor network are 3-hop paths.
That is correct.
What about the 4-hop paths created by circuit cannibalisation? (We don't actually know what proportion of the Tor network has 3-hop vs 4-hop paths.)
Depending on whether an exit or internal circuit is cannibalised, they can look like: G M E E G M M E
Or, if cannibalised from an exit or internal circuit: G M E M G M M M
Again, I think these will just be part of the overhead parameters?
Ugh. This will be complicated to work out. Cannibalization rate is a function of how often you need to build a path, and have circuits available, but none with the right exit/endpoint at the time. This will be hard to predict accurately in the wild. Cannibalization has been the bane of my existence every time I've made any performance or path selection change to Tor. It was an optimization introduced because TAP was believed to be too CPU-expensive to allow us to opt to build fresh circuits when we needed a different endpoint than was currently available in the open set, and so we needed to add the new required endpoint to an existing open circuit instead. Now that we have ntor, I am wondering if we can just remove cannibalization. My guess is that without it, we will pay some up-front latency cost in terms of needing to build fresh full circuits in some (rare?) cases, but probably will have faster and higher capacity circuits for those cases once they are built (especially since the Circuit Build Timeout cutoff works better without factoring in cannibalization time, as well). Circuit build prediction should also reduce this cost over time, since it will ensure that we always have a circuit open to recently used endpoint types (either exit ports or hidserv-capable circs). David Goulet supposedly has a simulator+test script to examine the impact of cannibalization. He said that he'd look into updating it for 0.2.7/master, but here's a graph of his results from 0.2.5: https://people.torproject.org/~dgoulet/hs/rp-025.png Basically, that says that unless you make a whole lot of rendezvous connections, cannibalized circuits are slower. I'm not sure why their speed would be a function of quantity at all.. As I said, circuit prediction should reduce the need for cannibalization over time, but it shouldn't actually make the circuits that do get cannibalized any faster.. All told, I think in the interest of simplification and also better load balancing, we should still kill cannibalization for most cases. The one case where I think it may still be desired is in the connection to the hsdir, since it seems natural to just extend an existing circuit rather than build a whole new one there.
And what about hidden service paths (paths that include two middle nodes?) G M M
This one definitely needs to be included in the M_o overhead. I believe the right additive amount is the current estimated percentage of network hidden service traffic (by bytes), but we need to make sure we use the estimate that reflects the fact that two hidden service paths are used for each hidden service connection. So: network total hidden service traffic percentage, not actual total hidden service throughput. Does that make sense? -- Mike Perry
On 14 Jan (08:07:47), Mike Perry wrote:
Tim Wilson-Brown - teor:
On 13 Jan 2016, at 00:53, Mike Perry <mikeperry@torproject.org> wrote: 1. Overview
For padding overhead due to Proposals 251 and 254, and changes to hidden service path selection in Proposal 247, it will be useful to be able to specify a pair of parameters that represents the additional traffic present on Guard and Middle nodes due to these changes.
I don't know if it's worth noting that proposals 252 and 260 (the Single Onion Services variants) will reduce traffic to guard and middle nodes, as they remove the nodes between the hidden service and client-controlled endpoint (rendezvous point in Rendezvous Single Onion Services, extend point in Single Onion Services).
I think these will just be part of the overhead parameters?
Probably, though this will require us to have some estimation on the amount of network traffic using these services. Will they be broken out separately in the extra-info hidden service stats?
2. Simplified Load Balancing Equations
Recall that the point of the load balancing equations in section 3.8.3 of dir-spec.txt is to ensure that an equal amount of client traffic is distributed between Guards, Middles, Exits, and Guard+Exits, where each flag type can occupy one or more positions in a path. This allocation is accomplished by solving a system of equations for weights for flag position selection to ensure equal allocation of client traffic for each position in a circuit.
If we ignore overhead for the moment and treat Guard+Exit nodes as Exit nodes, then this allows the simplified system of equations to become:
Wgg*G == M + Wme*E + Wmg*G # Guard position == middle position Wgg*G == Wee*E # Guard position == equals exit position Wmg*G + Wgg*G == G # Guard allocation weights sum to 1 Wme*E + Wee*E == E # Exit allocation weights sum to 1
I think this analysis assumes that all paths in the Tor network are 3-hop paths.
That is correct.
What about the 4-hop paths created by circuit cannibalisation? (We don't actually know what proportion of the Tor network has 3-hop vs 4-hop paths.)
Depending on whether an exit or internal circuit is cannibalised, they can look like: G M E E G M M E
Or, if cannibalised from an exit or internal circuit: G M E M G M M M
Again, I think these will just be part of the overhead parameters?
Ugh. This will be complicated to work out. Cannibalization rate is a function of how often you need to build a path, and have circuits available, but none with the right exit/endpoint at the time. This will be hard to predict accurately in the wild.
Cannibalization has been the bane of my existence every time I've made any performance or path selection change to Tor. It was an optimization introduced because TAP was believed to be too CPU-expensive to allow us to opt to build fresh circuits when we needed a different endpoint than was currently available in the open set, and so we needed to add the new required endpoint to an existing open circuit instead.
Now that we have ntor, I am wondering if we can just remove cannibalization. My guess is that without it, we will pay some up-front latency cost in terms of needing to build fresh full circuits in some (rare?) cases, but probably will have faster and higher capacity circuits for those cases once they are built (especially since the Circuit Build Timeout cutoff works better without factoring in cannibalization time, as well). Circuit build prediction should also reduce this cost over time, since it will ensure that we always have a circuit open to recently used endpoint types (either exit ports or hidserv-capable circs).
David Goulet supposedly has a simulator+test script to examine the impact of cannibalization. He said that he'd look into updating it for 0.2.7/master, but here's a graph of his results from 0.2.5: https://people.torproject.org/~dgoulet/hs/rp-025.png
Datapoint here: I'm almost done with #13802 (adding instrumentation framework to Tor) from which we'll be able to add events to the code so we can trace anything we want to measure. Once I'm done with KIST tracing, I'll jump on this one for which I already have most of the code ready for it. I want to get datapoints from a real relay and chutney. I'll update this thread once I get results.
Basically, that says that unless you make a whole lot of rendezvous connections, cannibalized circuits are slower. I'm not sure why their speed would be a function of quantity at all.. As I said, circuit prediction should reduce the need for cannibalization over time, but it shouldn't actually make the circuits that do get cannibalized any faster..
All told, I think in the interest of simplification and also better load balancing, we should still kill cannibalization for most cases. The one case where I think it may still be desired is in the connection to the hsdir, since it seems natural to just extend an existing circuit rather than build a whole new one there.
Both the HSDir (client/service) and Introduciton circuits (client) are short lived so it makes sense to use an existing circuit for those. However, keep in mind that on the client side if the connection to the intro point fails, the initial circuit used for that connection will be re-extended to the next one to try and this is done as long as we can that is 7 hops. This actually happens probably more than we think because if a client has a descriptor with the wrong introduction points, ultimately we end up with: G -> M -> M -> I_1 -> I_2 -> I_3 Cheers! David
And what about hidden service paths (paths that include two middle nodes?) G M M
This one definitely needs to be included in the M_o overhead. I believe the right additive amount is the current estimated percentage of network hidden service traffic (by bytes), but we need to make sure we use the estimate that reflects the fact that two hidden service paths are used for each hidden service connection. So: network total hidden service traffic percentage, not actual total hidden service throughput.
Does that make sense?
-- Mike Perry
_______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Mike Perry:
Tim Wilson-Brown - teor:
On 13 Jan 2016, at 00:53, Mike Perry <mikeperry@torproject.org> wrote: 1. Overview
For padding overhead due to Proposals 251 and 254, and changes to hidden service path selection in Proposal 247, it will be useful to be able to specify a pair of parameters that represents the additional traffic present on Guard and Middle nodes due to these changes.
I don't know if it's worth noting that proposals 252 and 260 (the Single Onion Services variants) will reduce traffic to guard and middle nodes, as they remove the nodes between the hidden service and client-controlled endpoint (rendezvous point in Rendezvous Single Onion Services, extend point in Single Onion Services).
I think these will just be part of the overhead parameters?
Probably, though this will require us to have some estimation on the amount of network traffic using these services. Will they be broken out separately in the extra-info hidden service stats?
2. Simplified Load Balancing Equations
Recall that the point of the load balancing equations in section 3.8.3 of dir-spec.txt is to ensure that an equal amount of client traffic is distributed between Guards, Middles, Exits, and Guard+Exits, where each flag type can occupy one or more positions in a path. This allocation is accomplished by solving a system of equations for weights for flag position selection to ensure equal allocation of client traffic for each position in a circuit.
If we ignore overhead for the moment and treat Guard+Exit nodes as Exit nodes, then this allows the simplified system of equations to become:
Wgg*G == M + Wme*E + Wmg*G # Guard position == middle position Wgg*G == Wee*E # Guard position == equals exit position Wmg*G + Wgg*G == G # Guard allocation weights sum to 1 Wme*E + Wee*E == E # Exit allocation weights sum to 1
I think this analysis assumes that all paths in the Tor network are 3-hop paths.
That is correct.
What about the 4-hop paths created by circuit cannibalisation? (We don't actually know what proportion of the Tor network has 3-hop vs 4-hop paths.)
Depending on whether an exit or internal circuit is cannibalised, they can look like: G M E E G M M E
Or, if cannibalised from an exit or internal circuit: G M E M G M M M
Again, I think these will just be part of the overhead parameters?
Ugh. This will be complicated to work out. Cannibalization rate is a function of how often you need to build a path, and have circuits available, but none with the right exit/endpoint at the time. This will be hard to predict accurately in the wild.
Cannibalization has been the bane of my existence every time I've made any performance or path selection change to Tor. It was an optimization introduced because TAP was believed to be too CPU-expensive to allow us to opt to build fresh circuits when we needed a different endpoint than was currently available in the open set, and so we needed to add the new required endpoint to an existing open circuit instead.
Now that we have ntor, I am wondering if we can just remove cannibalization. My guess is that without it, we will pay some up-front latency cost in terms of needing to build fresh full circuits in some (rare?) cases, but probably will have faster and higher capacity circuits for those cases once they are built (especially since the Circuit Build Timeout cutoff works better without factoring in cannibalization time, as well). Circuit build prediction should also reduce this cost over time, since it will ensure that we always have a circuit open to recently used endpoint types (either exit ports or hidserv-capable circs).
David Goulet supposedly has a simulator+test script to examine the impact of cannibalization. He said that he'd look into updating it for 0.2.7/master, but here's a graph of his results from 0.2.5: https://people.torproject.org/~dgoulet/hs/rp-025.png
Basically, that says that unless you make a whole lot of rendezvous connections, cannibalized circuits are slower. I'm not sure why their speed would be a function of quantity at all.. As I said, circuit prediction should reduce the need for cannibalization over time, but it shouldn't actually make the circuits that do get cannibalized any faster..
All told, I think in the interest of simplification and also better load balancing, we should still kill cannibalization for most cases. The one case where I think it may still be desired is in the connection to the hsdir, since it seems natural to just extend an existing circuit rather than build a whole new one there.
And what about hidden service paths (paths that include two middle nodes?) G M M
This one definitely needs to be included in the M_o overhead. I believe the right additive amount is the current estimated percentage of network hidden service traffic (by bytes), but we need to make sure we use the estimate that reflects the fact that two hidden service paths are used for each hidden service connection. So: network total hidden service traffic percentage, not actual total hidden service throughput.
With Proposal 247, we decided that to avoid the need to create a secondary guard connection for issues like https://trac.torproject.org/projects/tor/ticket/14917, we have to omit Guard-flagged nodes from the two M's in the G M M path selection for hidden services and their rendezvous points. This means that we need to subtract the hidden service overhead from G_o, in addition to adding to to M_o. Right now, I'm thinking this means M_o needs to add the total hidden service *network bytecount* overhead (2X the hidden service end-to-end traffic bytecount). We also need to subtract 4*Wmg*hs_e2e_bytecount from the G_o overhead, to account for not using Guard-flagged nodes for the four M's in full prop-247 G M M M M G circuits. Again, I still think we should kill cannibalization, so that we don't have to worry about 7 hop hidden service circuits for a new rendezvous point being added to an existing cannibalized circuit. I have added these and the other comments from Teor to a new branch: https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/265-... They are still in the form of XXX's, pending additional comments. I will turn them into better descriptions if this makes sense to folks. -- Mike Perry
On 15 Jan 2016, at 03:07, Mike Perry <mikeperry@torproject.org> wrote:
Tim Wilson-Brown - teor:
On 13 Jan 2016, at 00:53, Mike Perry <mikeperry@torproject.org <mailto:mikeperry@torproject.org>> wrote: 1. Overview
For padding overhead due to Proposals 251 and 254, and changes to hidden service path selection in Proposal 247, it will be useful to be able to specify a pair of parameters that represents the additional traffic present on Guard and Middle nodes due to these changes.
I don't know if it's worth noting that proposals 252 and 260 (the Single Onion Services variants) will reduce traffic to guard and middle nodes, as they remove the nodes between the hidden service and client-controlled endpoint (rendezvous point in Rendezvous Single Onion Services, extend point in Single Onion Services).
I think these will just be part of the overhead parameters?
Probably, though this will require us to have some estimation on the amount of network traffic using these services. Will they be broken out separately in the extra-info hidden service stats?
Logged as #18082. https://trac.torproject.org/projects/tor/ticket/18082 <https://trac.torproject.org/projects/tor/ticket/18082> Since Rendezvous Single Onion Services (RSOS) and Single Onion Services (SOS) have the same path length, I think they can be combined into a single extra-info statistic, rather than being split into separate groups. I don't know what impact separating HS and (R)SOS has on anonymity, but my gut feeling is that it should be OK as large site operators are keen to adopt (R)SOS. Tim Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F
On 15 Jan 2016, at 03:07, Mike Perry <mikeperry@torproject.org> wrote:
Tim Wilson-Brown - teor:
On 13 Jan 2016, at 00:53, Mike Perry <mikeperry@torproject.org <mailto:mikeperry@torproject.org>> wrote: 1. Overview
For padding overhead due to Proposals 251 and 254, and changes to hidden service path selection in Proposal 247, it will be useful to be able to specify a pair of parameters that represents the additional traffic present on Guard and Middle nodes due to these changes.
I don't know if it's worth noting that proposals 252 and 260 (the Single Onion Services variants) will reduce traffic to guard and middle nodes, as they remove the nodes between the hidden service and client-controlled endpoint (rendezvous point in Rendezvous Single Onion Services, extend point in Single Onion Services).
I think these will just be part of the overhead parameters?
Probably, though this will require us to have some estimation on the amount of network traffic using these services. Will they be broken out separately in the extra-info hidden service stats?
Unfortunately, it is not possible to separate the statistics for Rendezvous Single Onion Services (RSOS), as the hidden service statistics are measured at the HSDir and Rendezvous Point relays, and not at the hidden service itself. These relays have no way of knowing whether they are connected to a RSOS or not. The impact of this is: * Rendezvous Single Onion Services will appear as Hidden Services in the HSDir and Rendezvous Point statistics * Single Onion Services will appear as Hidden Services in the HSDir statistics only (they don't do Rendezvous) However, it is possible to keep separate statistics on cells seen by a relay via Single Onion Service extend requests. HSDirs can log requests for Single Onion Service descriptors separately, as they are the only descriptors that contain an extend-info line. However, it's may not be worth implementing, as the encryption in proposal 224 will stop HSDirs reading HS descriptors. We could have Rendezvous Single Onion Services add an identifying line to their descriptors, but we'd have to do it in a way that allowed clients to still parse the descriptors. That would only get us the HSDir statistics anyway. That said, if we identify RSOS in their descriptor so Tor2web clients don't connect to them, we could use the identifier for statistics as well. I'll post a similar comment to #18082 and #17945, where this work is being tracked. https://trac.torproject.org/projects/tor/ticket/18082 <https://trac.torproject.org/projects/tor/ticket/18082> https://trac.torproject.org/projects/tor/ticket/17945 <https://trac.torproject.org/projects/tor/ticket/17945> Tim Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F
On Tue, Jan 12, 2016 at 8:53 AM, Mike Perry <mikeperry@torproject.org> wrote:
This proposal aims to allow us to load balance properly between Guard, Middle, and Exit nodes with the addition of padding traffic to the network.
Canonical proposal current lives in my load_balancing-squashed branch: https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/xxx-...
Here is the text in-line, for ease of commenting on-list:
Added from the list as proposal 265 before I saw there was a canonical location :/ . Please point me at something to pull if the proposal needs to be updated.
participants (4)
-
David Goulet -
Mike Perry -
Nick Mathewson -
Tim Wilson-Brown - teor