diff options
Diffstat (limited to 'spec/guard-spec/algorithm.md')
| -rw-r--r-- | spec/guard-spec/algorithm.md | 26 |
1 files changed, 19 insertions, 7 deletions
diff --git a/spec/guard-spec/algorithm.md b/spec/guard-spec/algorithm.md index 0f04f31..e1d4374 100644 --- a/spec/guard-spec/algorithm.md +++ b/spec/guard-spec/algorithm.md @@ -1,7 +1,9 @@ <a id="guard-spec.txt-4"></a> -# The algorithm. + +# The algorithm <a id="guard-spec.txt-4.0"></a> + ## The guards listed in the current consensus. [Section:GUARDS] By {set:GUARDS} we mean the set of all guards in the current @@ -14,6 +16,7 @@ We require all guards to have the flags that we potentially need from any guard, so that all guards are usable for all circuits. <a id="guard-spec.txt-4.1"></a> + ## The Sampled Guard Set. [Section:SAMPLED] We maintain a set, {set:SAMPLED_GUARDS}, that persists across @@ -126,6 +129,7 @@ adversary would need the clients to exhaust all their initial adversary node. <a id="guard-spec.txt-4.2"></a> + ## The Usable Sample [Section:FILTERED] We maintain another set, {set:FILTERED_GUARDS}, that does not @@ -180,6 +184,7 @@ before the sampling, then our sample would reflect the set of filtering restrictions that we had in the past. <a id="guard-spec.txt-4.3"></a> + ## The confirmed-guard list. [Section:CONFIRMED] [formerly USED_GUARDS] @@ -241,6 +246,7 @@ committing to a guard before we actually use it for sensitive traffic. <a id="guard-spec.txt-4.4"></a> + ## The Primary guards [Section:PRIMARY] We keep a run-time non-persistent ordered list of @@ -264,7 +270,7 @@ non-confirmed primary guards. Note that {PRIMARY_GUARDS} do not have to be in {USABLE_FILTERED_GUARDS}: they might be unreachable. -** Rationale ** +**Rationale** These guards are treated differently from other guards. If one of them is usable, then we use it right away. For other guards @@ -273,6 +279,7 @@ first double-check whether perhaps one of the primary guards is usable after all. <a id="guard-spec.txt-4.5"></a> + ## Retrying guards. [Section:RETRYING] (We run this process as frequently as needed. It can be done once @@ -288,13 +295,14 @@ we decide whether to update its {is_reachable} status to `<maybe>` based on its {last_tried_connect} time, its {failing_since} time, and the {GUARDS_RETRY_SCHED} schedule. -** Rationale ** +**Rationale** 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> + ## Selecting guards for circuits. [Section:SELECTING] Every origin circuit is now in one of these states: @@ -379,7 +387,7 @@ restrict the guards that we use for a single circuit. When this happens, we remember the restrictions that applied when choosing the guard for that circuit, since we will need them later (see [UPDATE_WAITING].). -** Rationale ** +**Rationale** We're getting to the core of the algorithm here. Our main goals are to make sure that @@ -401,6 +409,7 @@ sure that it's the best guard we're getting. (see below). [XXX timeout.] <a id="guard-spec.txt-4.7"></a> + ## When a circuit fails. [Section:ON_FAIL] When a circuit fails in a way that makes us conclude that a guard @@ -422,11 +431,12 @@ is not reachable, we take the following steps: circuits in response to some of these steps; and also see [ON_CONSENSUS].] -** Rationale ** +**Rationale** See [SELECTING] above for rationale. <a id="guard-spec.txt-4.8"></a> + ## When a circuit succeeds [Section:ON_SUCCESS] When a circuit succeeds in a way that makes us conclude that a @@ -460,11 +470,12 @@ guard _was_ reachable, we take these steps: circuits in response to some of these steps; and see [ON_CONSENSUS].] -** Rationale ** +**Rationale** See [SELECTING] above for rationale. <a id="guard-spec.txt-4.9"></a> + ## Updating the list of waiting circuits [Section:UPDATE_WAITING] We run this procedure whenever it's possible that a @@ -504,6 +515,7 @@ them after all if the `<complete>` circuit goes down before {NONPRIMARY_GUARD_IDLE_TIMEOUT} seconds. <a id="guard-spec.txt-4.9.1"></a> + ### Without a list of waiting circuits [Section:NO_CIRCLIST] As an alternative to the section [SECTION:UPDATE_WAITING] above, @@ -546,6 +558,7 @@ circuit is not discarded; instead, it is kept (but not used) until the guard becomes usable or unusable. <a id="guard-spec.txt-4.10"></a> + ## Whenever we get a new consensus. [Section:ON_CONSENSUS] We update {GUARDS}. @@ -591,4 +604,3 @@ directory fetches, but not for longer circuits. (Also, when we are missing descriptors for our first {NUM_USABLE_PRIMARY_GUARDS} primary guards, we don't build circuits at all until we have fetched them.) - |