Prop 324: Describe RFC3742 Limited Slow Start

1 files 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