From 7c186cf1e562cd3bee84f7c35525204bd0bedf0c Mon Sep 17 00:00:00 2001 From: Mike Perry Date: Wed, 10 Aug 2022 21:26:11 +0000 Subject: Prop 324: Describe RFC3742 Limited Slow Start --- proposals/324-rtt-congestion-control.txt | 137 +++++++++++++++++++------------ 1 file changed, 85 insertions(+), 52 deletions(-) (limited to 'proposals/324-rtt-congestion-control.txt') 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 -- cgit v1.2.3-54-g00ecf