This is an automated email from the git hooks/post-receive script.

dgoulet pushed a commit to branch main in repository torspec.

commit 7c186cf1e562cd3bee84f7c35525204bd0bedf0c Author: Mike Perry mikeperry-git@torproject.org AuthorDate: Wed Aug 10 21:26:11 2022 +0000

Prop 324: Describe RFC3742 Limited Slow Start --- proposals/324-rtt-congestion-control.txt | 137 +++++++++++++++++++------------ 1 file changed, 85 insertions(+), 52 deletions(-)

diff --git a/proposals/324-rtt-congestion-control.txt b/proposals/324-rtt-congestion-control.txt index 78b6789..78d526d 100644 --- a/proposals/324-rtt-congestion-control.txt +++ b/proposals/324-rtt-congestion-control.txt @@ -535,13 +535,29 @@ SENDME ack arrival, as an immediate congestion signal. ideas/xxx-backward-ecn.txt, but this is not implemented. It is likely only of any benefit during Slow Start, and even that benefit is likely small.)

-Congestion signals from RTT, blocked OR connections, or ECN are processed only -once per congestion window. This is achieved through the next_cc_event flag, -which is initialized to a cwnd worth of SENDME acks, and is decremented -each ack. Congestion signals are only evaluated when it reaches 0. - -Here is the complete pseudocode for TOR_VEGAS, which is run every time -an endpoint receives a SENDME ack: +During Slow Start, we use RFC3742 Limited Slow Start[32], which checks the +congestion signals from RTT, blocked OR connections, or ECN every single +SENDME ack. It also provides a `cc_sscap_*` parameter for each path length, +which reduces the congestion window increment rate after it is crossed, as +per the rules in RFC3742: + rfc3742_ss_inc(cwnd): + if cwnd <= cc_ss_cap_pathtype: + # Below the cap, we increment as per cc_cwnd_inc_pct_ss percent: + return round(cc_cwnd_inc_pct_ss*cc_sendme_inc/100) + else: + # This returns an increment equivalent to RFC3742, rounded: + # K = int(cwnd/(0.5 max_ssthresh)); + # inc = int(MSS/K); + return round((cc_sendme_inc*cc_ss_cap_pathtype)/(2*cwnd)); + +After Slow Start, congestion signals from RTT, blocked OR connections, or ECN +are processed only once per congestion window. This is achieved through the +next_cc_event flag, which is initialized to a cwnd worth of SENDME acks, and +is decremented each ack. Congestion signals are only evaluated when it reaches +0. + +Here is the complete pseudocode for TOR_VEGAS with RFC3742, which is run every +time an endpoint receives a SENDME ack:

# Update acked cells inflight -= cc_sendme_inc @@ -554,38 +570,45 @@ an endpoint receives a SENDME ack: if clock_stalled_or_jumped: return

- if next_cc_event == 0: - if BDP > cwnd: - queue_use = 0 - else: - queue_use = cwnd - BDP - - if in_slow_start: - if queue_use < cc_vegas_gamma and not orconn_blocked: - # Increment by slow start %, or at least 2 sendme_inc's worth - cwnd = cwnd + MAX(cwnd * cc_cwnd_inc_pct_ss, 2*cc_sendme_inc) - # If our BDP estimator thinks the BDP is still larger, use that - cwnd = MAX(cwnd, BDP) - else: - cwnd = BDP + cc_vegas_gamma - in_slow_start = 0 - else: - if queue_use > cc_vegas_delta: - cwnd = BDP + cc_vegas_delta - cc_cwnd_inc - elif queue_use > cc_vegas_beta or orconn_blocked: - cwnd -= cc_cwnd_inc - elif queue_use < cc_vegas_alpha: - cwnd += cc_cwnd_inc - - cwnd = MAX(cwnd, cc_circwindow_min) - - # Count the number of sendme acks until next update of cwnd, - # rounded to nearest integer - if in_slow_start: - next_cc_event = round(cwnd / cc_sendme_inc) - else - # Never increment faster in slow start, only steady state. - next_cc_event = round(cwnd / (cc_cwnd_inc_rate * cc_sendme_inc)) + if BDP > cwnd: + queue_use = 0 + else: + queue_use = cwnd - BDP + + if in_slow_start: + if queue_use < cc_vegas_gamma and not orconn_blocked: + inc = rfc3742_ss_inc(cwnd); + cwnd += inc + next_cc_event = 1 + + # If the RFC3742 increment drops below steady-state increment + # over a full cwnd worth of acks, exit slow start + if inc*SENDME_PER_CWND(cwnd) <= cc_cwnd_inc: + in_slow_start = 0 + next_cc_event = round(cwnd / (cc_cwnd_inc_rate * cc_sendme_inc)) + else: + in_slow_start = 0 + cwnd = BDP + cc_vegas_gamma + next_cc_event = round(cwnd / (cc_cwnd_inc_rate * cc_sendme_inc)) + + # Provide an emergency hard-max on slow start: + if cwnd >= cc_ss_max: + cwnd = cc_ss_max + in_slow_start = 0 + next_cc_event = round(cwnd / (cc_cwnd_inc_rate * cc_sendme_inc)) + else if next_cc_event == 0: + if queue_use > cc_vegas_delta: + cwnd = BDP + cc_vegas_delta - cc_cwnd_inc + elif queue_use > cc_vegas_beta or orconn_blocked: + cwnd -= cc_cwnd_inc + elif queue_use < cc_vegas_alpha: + cwnd += cc_cwnd_inc + + cwnd = MAX(cwnd, cc_circwindow_min) + + # Count the number of sendme acks until next update of cwnd, + # rounded to nearest integer + next_cc_event = round(cwnd / (cc_cwnd_inc_rate * cc_sendme_inc))

3.4. Tor NOLA: Direct BDP tracker [TOR_NOLA] @@ -1395,20 +1418,27 @@ These are sorted in order of importance to tune, most important first. need to verify that the path length multiplier still holds for other types of circuits, specifically onion services.

- cc_vegas_bdp_mix: - - Description: This parameter allows us to specify a weighted percent - average between the cwnd BDP estimator and the piecewise - estimator. - - Range: [0, 100] - - Default: 100 (use 100% CWND estimator) - - Tuning Notes: - The original Vegas literature specified the CWND estimator, but - the Piecewise estimator is very likely more suited for our use - case. This parameter allows us to average them. We're unlikely to - need it. + cc_sscap_sbws_{exit,onion,sbws}: + - Description: These parameters describe the RFC3742 'cap', after which + congestion window increments are reduced. INT32_MAX disables + RFC3742. + - Range: [100, INT32_MAX] + - Defaults: + sbws: 400 + exit: 500 + onion: 600 - Shadow Tuning Results: - Because the BDP estimator had ack compression and over-estimation, - we the CWND estimator. + We picked these defaults based on the average congestion window + seen in Shadow sims for exits and onion service circuits. + + cc_ss_max: + - Description: This parameter provides a hard-max on the congestion + window in slow start. + - Range: [500, INT32_MAX] + - Default: 5000 + - Shadow Tuning Results: + The largest congestion window seen in Shadow is ~3000, so this was + set as a safety valve above that.

6.5.4. NOLA Parameters

@@ -2133,3 +2163,6 @@ receive more data. It is sent to tell the sender to resume sending.

31. KIST: Kernel-Informed Socket Transport for Tor https://matt.traudt.xyz/static/papers/kist-tops2018.pdf + +32. RFC3742 Limited Slow Start + https://datatracker.ietf.org/doc/html/rfc3742#section-2

This is an automated email from the git hooks/post-receive script.

dgoulet pushed a commit to branch main in repository torspec.

commit d339bb9fab10c32c10fce0e06421bbadaffe2777 Author: Mike Perry mikeperry-git@torproject.org AuthorDate: Wed Aug 10 22:28:33 2022 +0000

Prop 324: Describe how to reset RTT if cc_cwnd_min is hit. --- proposals/324-rtt-congestion-control.txt | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)

diff --git a/proposals/324-rtt-congestion-control.txt b/proposals/324-rtt-congestion-control.txt index 0e8c349..c9997ef 100644 --- a/proposals/324-rtt-congestion-control.txt +++ b/proposals/324-rtt-congestion-control.txt @@ -389,6 +389,13 @@ Simplifying:

BDP = cwnd * RTT_min / RTT_current_ewma

+The RTT_min for this calculation comes from the minimum RTT_current_ewma +seen in the lifetime of this circuit. If the congestion window falls to +`cc_cwnd_min`, implementations MAY choose to reset RTT_min for use in this +calculation to either the RTT_current_ewma, or a percentile-weighted average +between RTT_min and RTT_current_ewma, specified by `cc_rtt_reset_pct`. This +helps with escaping starvation conditions. + The net effect of this estimation is to correct for any overshoot of the cwnd over the actual BDP. It will obviously underestimate BDP if cwnd is below BDP. @@ -1304,6 +1311,16 @@ These are sorted in order of importance to tune, most important first. - Shadow Tuning Results: Setting this to 2 helped reduce overshoot during Slow Start.

+ cc_rtt_reset_pct: + - Description: Describes a percentile average between RTT_min and + RTT_current_ewma, for use to reset RTT_min, when the + congestion window hits cwnd_min. + - Range: [0, 100] + - Default: 100 + - Shadow Tuning Results: + cwnd_min is not hit in Shadow simulations, but it can be hit + on the live network while under DoS conditions, and with cheaters. + cc_cwnd_inc: - Description: How much to increment the congestion window by during steady state, every cwnd.