diff options
author | Nick Mathewson <nickm@torproject.org> | 2023-11-01 09:11:40 -0400 |
---|---|---|
committer | Nick Mathewson <nickm@torproject.org> | 2023-11-01 09:11:40 -0400 |
commit | 4365dab1021338328cb5bcc6c30ed6539ebe4fee (patch) | |
tree | 1ff4b1cc1b97eab3c99cd5679bd43db6d223fd6d /spec/guard-spec | |
parent | 00ae47caf7cf645b077f6d1b3e3c6e831c51b271 (diff) | |
download | torspec-4365dab1021338328cb5bcc6c30ed6539ebe4fee.tar.gz torspec-4365dab1021338328cb5bcc6c30ed6539ebe4fee.zip |
guard selection: Try to clarify and clean up a bit
This is a follow-on for !182.
Diffstat (limited to 'spec/guard-spec')
-rw-r--r-- | spec/guard-spec/algorithm.md | 83 |
1 files changed, 61 insertions, 22 deletions
diff --git a/spec/guard-spec/algorithm.md b/spec/guard-spec/algorithm.md index 8a3e1ca..1dc0b18 100644 --- a/spec/guard-spec/algorithm.md +++ b/spec/guard-spec/algorithm.md @@ -301,11 +301,15 @@ An observation that a guard has been 'unreachable' only lasts for a given amount of time, since we can't infer that it's unreachable now from the fact that it was unreachable a few minutes ago. -<a id="guard-spec.txt-4.6"></a> +## Circuit status {#CIRC-STATUS} -## Selecting guards for circuits. \[Section:SELECTING\] +Sometimes the guard selection algorithm will return a guard that we +would always be happy to use; but in other cases, the guard +selection algorithm can return a guard that we shouldn't use +without gathering additional information. -Every origin circuit is now in one of these states: +From the point of view of guard selection, +every circuit we build is considered to be in one of these states: * `<state:usable_on_completion>` * `<state:usable_if_no_better_guard>` @@ -313,8 +317,8 @@ Every origin circuit is now in one of these states: * `<state:complete>` You may only attach streams to `<complete>` circuits. -(Additionally, you may only send RENDEZVOUS cells, ESTABLISH_INTRO -cells, and INTRODUCE cells on `<complete>` circuits.) +(Additionally, you may only send RENDEZVOUS messages, ESTABLISH_INTRO +messages, and INTRODUCE messages on `<complete>` circuits.) The per-circuit state machine is: @@ -334,7 +338,36 @@ The per-circuit state machine is: * A `<complete>` circuit remains `<complete>` until it fails or is closed. - * Each of these transitions is described below. +```mermaid +--- +title: Circuit state transitions +--- + +[*] -> usable_on_completion +[*] -> usable_if_no_better_guard +usable_on_completion -> complete +usable_on_completion -> failed +usable_if_no_better_guard -> usable_on_completion +usable_if_no_better_guard -> waiting_for_better_guard +usable_if_no_better_guard -> failed +waiting_for_better_guard -> complete +waiting_for_better_guard -> failed +waiting_for_better_guard -> closed +complete -> failed +complete -> closed +failed -> [*] +closed -> [*] +``` +<!-- TODO: The above diagram does not yet render. Fix that. --> + +Each of these transitions is described in sections below. + +<a id="guard-spec.txt-4.6"></a> + +## Selecting guards for circuits. \[Section:SELECTING\] + +Now that we have described the various lists of guards, we can explain how +guards are chosen for each circuit. We keep, as global transient state: @@ -342,23 +375,29 @@ We keep, as global transient state: successfully used a circuit or connected to a guard. At startup we set this to "infinitely far in the past." +As an input to the algorithm, we take a list of _restrictions_. +These may include specific relays or families that we need to avoid. + +Here is the algorithm. It is given as a series of sub-algorithms, +in decreasing order of preference from best case to worst case. When we want to build a circuit, and we need to pick a guard: - * If any entry in PRIMARY_GUARDS has {is_reachable} status of - `<maybe>` or `<yes>`, check the first {NUM_USABLE_PRIMARY_GUARDS} or - {NUM_USABLE_PRIMARY_DIRECTORY_GUARDS} such guards against - any path selection restrictions, to build a temporary list of - usable guards. If the path restriction is circuit-specific and - excludes a primary guard, do not use that guard, but still - increment the number of usable guards that were considered. - If the restriction causes the number of guards considered to - exceed either usable limit count, then proceed to select another - primary guard. - - This usable list is temporary, but because the primary guard ordering - is persistent, it will be a stable set. At the end of this selection - process, chose uniformly at random from this usable list. The - circuit is `<usable_on_completion>`. + * In the base case, if any entry in PRIMARY_GUARDS has {is_reachable} status of + `<maybe>` or `<yes>`, consider only such guards. Call them the + "reachable primary guards". + + Start by considering the the first {NUM_USABLE_PRIMARY_GUARDS} (or + {NUM_USABLE_PRIMARY_DIRECTORY_GUARDS}) reachable primary guards. + Remove any guards that do not follow our path selection + restrictions, to build a temporary list. If that temporary list contains at + least one guard, choose a guard from that list uniformly at + random. + + If the temporary list contains no guards, return the first guard + from our reachable primary guard that does obey the path restriction. + + When selecting a guard according to this approach, its circuit + is `<usable_on_completion>`. [Note: We do not use {is_pending} on primary guards, since we are willing to try to build multiple circuits through them @@ -380,7 +419,7 @@ When we want to build a circuit, and we need to pick a guard: true, and set its {pending_since} to the current time. The circuit is `<usable_if_no_better_guard>`. - * Otherwise, if USABLE_FILTERED_GUARDS is empty, we have exhausted + * Otherwise, in the worst case, if USABLE_FILTERED_GUARDS is empty, we have exhausted all the sampled guards. In this case we proceed by marking all guards as `<maybe>` reachable so that we can keep on trying circuits. |