This is an automated email from the git hooks/post-receive script.
dgoulet pushed a change to branch main in repository torspec.
from c2e057a Prop 324: RTT should only be reset after slow start. new dabadcc Update Prop#324 clock heuristic spec for bug 40626. new 773fc92 Merge branch 'tor-gitlab/mr/75' new aab9efe prop#324: mention rearranged form for N_EWMA smoothing new 0bacc73 Merge branch 'tor-gitlab/mr/83'
The 4 revisions listed above as "new" are entirely new to this repository and will be described in separate emails. The revisions listed as "add" were already present in the repository and have only been added to this reference.
Summary of changes: proposals/324-rtt-congestion-control.txt | 32 +++++++++++++++++++------------- 1 file changed, 19 insertions(+), 13 deletions(-)
This is an automated email from the git hooks/post-receive script.
dgoulet pushed a commit to branch main in repository torspec.
commit dabadcc9d6a264c81ff84c3672c76e3261d4fe34 Author: Mike Perry mikeperry-git@torproject.org AuthorDate: Tue Jun 21 20:26:37 2022 +0000
Update Prop#324 clock heuristic spec for bug 40626. --- proposals/324-rtt-congestion-control.txt | 30 ++++++++++++++++-------------- 1 file changed, 16 insertions(+), 14 deletions(-)
diff --git a/proposals/324-rtt-congestion-control.txt b/proposals/324-rtt-congestion-control.txt index 78b6789..67514dc 100644 --- a/proposals/324-rtt-congestion-control.txt +++ b/proposals/324-rtt-congestion-control.txt @@ -144,20 +144,22 @@ measured by the RTT estimator, and if these heurtics detect a stall or a jump, we do not use that value to update RTT or BDP, nor do we update any congestion control algorithm information that round.
-If the time delta is 0, that is always treated as a clock stall. - -If we have measured at least 'cc_bwe_min' RTT values or we have successfully -exited slow start, then every sendme ACK, the new candidate RTT is compared to -the stored EWMA RTT. If the new RTT is either 5000 times larger than the EWMA -RTT, or 5000 times smaller than the stored EWMA RTT, then we do not record that -estimate, and do not update BDP or the congestion control algorithms for that -SENDME ack. - -Moreover, if a clock stall is detected by *any* circuit, this fact is -cached, and this cached value is used on circuits for which we do not -have enough data to compute the above heueristics. This cached value is -also exported for use by the edge connection rate calculations done by -[XON_ADVISORY]. +If the time delta is 0, that is always treated as a clock stall, the RTT is +not used, congestion control is not updated, and this fact is cached globally. + +If the circuit does not yet have an EWMA RTT or it is still in Slow Start, then +no further checks are performed, and the RTT is used. + +If the circuit has stored an EWMA RTT and has exited Slow Start, then every +sendme ACK, the new candidate RTT is compared to the stored EWMA RTT. If the +new RTT is 5000 times larger than the EWMA RTT, then the circuit does not +record that estimate, and does not update BDP or the congestion control +algorithms for that SENDME ack. If the new RTT is 5000 times smaller than the +EWMA RTT, then the circuit uses the globally cached value from above (ie: it +assumes the clock is stalled *only* if there was previously *also* a 0-delta RTT). + +If both ratio checks pass, the globally cached clock stall state is set to +false (no stall), and the RTT value is used.
2.1.2. N_EWMA Smoothing [N_EWMA_SMOOTHING]
This is an automated email from the git hooks/post-receive script.
dgoulet pushed a commit to branch main in repository torspec.
commit aab9efe13b3162db29e72d9364e30bc2955614ab Author: eta tor@eta.st AuthorDate: Mon Aug 8 13:14:45 2022 +0100
prop#324: mention rearranged form for N_EWMA smoothing
The formula used for N_EWMA is actually rearranged in the C tor implementation, in a way that caused the arti reimplementation to be off by a small rounding error until it was corrected.
In order to ensure other implementations don't have this issue, mention the rearranged form and add a requirement that it be used.
(background: https://gitlab.torproject.org/tpo/core/arti/-/merge_requests/525#note_280724...) --- proposals/324-rtt-congestion-control.txt | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
diff --git a/proposals/324-rtt-congestion-control.txt b/proposals/324-rtt-congestion-control.txt index 78b6789..c617983 100644 --- a/proposals/324-rtt-congestion-control.txt +++ b/proposals/324-rtt-congestion-control.txt @@ -167,7 +167,11 @@ reduce the effects of packet jitter. This smoothing is performed using N_EWMA[27], which is an Exponential Moving Average with alpha = 2/(N+1):
- N_EWMA = BDP*2/(N+1) + N_EWMA_prev*(N-1)/(N+1). + N_EWMA = BDP*2/(N+1) + N_EWMA_prev*(N-1)/(N+1) + = (BDP*2 + N_EWMA_prev*(N-1))/(N+1). + +Note that the second rearranged form MUST be used in order to ensure that +rounding errors are handled in the same manner as other implementations.
Flow control rate limiting uses this function
This is an automated email from the git hooks/post-receive script.
dgoulet pushed a commit to branch main in repository torspec.
commit 773fc9200046124e40f40f9367e0c94736353cac Merge: c2e057a dabadcc Author: David Goulet dgoulet@torproject.org AuthorDate: Tue Jan 10 16:17:06 2023 -0500
Merge branch 'tor-gitlab/mr/75'
proposals/324-rtt-congestion-control.txt | 30 ++++++++++++++++-------------- 1 file changed, 16 insertions(+), 14 deletions(-)
This is an automated email from the git hooks/post-receive script.
dgoulet pushed a commit to branch main in repository torspec.
commit 0bacc73d6baee7c2dfd9a7a864163e26f6c121ef Merge: 773fc92 aab9efe Author: David Goulet dgoulet@torproject.org AuthorDate: Tue Jan 10 16:17:25 2023 -0500
Merge branch 'tor-gitlab/mr/83'
proposals/324-rtt-congestion-control.txt | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
diff --cc proposals/324-rtt-congestion-control.txt index 7701230,c617983..952d140 --- a/proposals/324-rtt-congestion-control.txt +++ b/proposals/324-rtt-congestion-control.txt @@@ -169,14 -167,16 +169,18 @@@ reduce the effects of packet jitter This smoothing is performed using N_EWMA[27], which is an Exponential Moving Average with alpha = 2/(N+1):
- N_EWMA = BDP*2/(N+1) + N_EWMA_prev*(N-1)/(N+1). + N_EWMA = BDP*2/(N+1) + N_EWMA_prev*(N-1)/(N+1) + = (BDP*2 + N_EWMA_prev*(N-1))/(N+1). + + Note that the second rearranged form MUST be used in order to ensure that + rounding errors are handled in the same manner as other implementations.
-Flow control rate limiting uses this function +Flow control rate limiting uses this function. + +During Slow Start, N is set to `cc_ewma_ss`, for RTT estimation.
-For both RTT and SENDME BDP estimation, N is the number of SENDME acks -between congestion window updates, divided by the value of consensus +After Slow Start, for both RTT and SENDME BDP estimation, N is the number +of SENDME acks between congestion window updates, divided by the value of consensus parameter 'cc_ewma_cwnd_pct', and then capped at a max of 'cc_ewma_max', but always at least 2:
tor-commits@lists.torproject.org