This is an automated email from the git hooks/post-receive script.
dgoulet pushed a commit to branch main in repository tor.
commit 832a1d9fae9a006d9f5fcf26718901395d197703 Author: Mike Perry mikeperry-git@torproject.org AuthorDate: Fri Jul 22 17:00:22 2022 +0000
Implement RFC3742 Limited Slow Start
RFC3742 updates the cwnd every sendme during slow start, and backs off of the exponential growth based on a cap parameter. --- src/core/or/congestion_control_common.c | 2 +- src/core/or/congestion_control_st.h | 14 ++ src/core/or/congestion_control_vegas.c | 266 +++++++++++++++++++++----------- 3 files changed, 191 insertions(+), 91 deletions(-)
diff --git a/src/core/or/congestion_control_common.c b/src/core/or/congestion_control_common.c index 42f816690f..8f09a80bae 100644 --- a/src/core/or/congestion_control_common.c +++ b/src/core/or/congestion_control_common.c @@ -42,7 +42,7 @@ #define CC_ALG_DFLT_ALWAYS (CC_ALG_VEGAS)
#define CWND_INC_DFLT (TLS_RECORD_MAX_CELLS) -#define CWND_INC_PCT_SS_DFLT (50) +#define CWND_INC_PCT_SS_DFLT (100) #define CWND_INC_RATE_DFLT (1)
#define CWND_MIN_DFLT (SENDME_INC_DFLT) diff --git a/src/core/or/congestion_control_st.h b/src/core/or/congestion_control_st.h index bc547b59d9..f88e1f4a9a 100644 --- a/src/core/or/congestion_control_st.h +++ b/src/core/or/congestion_control_st.h @@ -97,6 +97,10 @@ struct westwood_params_t {
/** Vegas algorithm parameters. */ struct vegas_params_t { + /** The slow-start cwnd cap for RFC3742 */ + uint32_t ss_cwnd_cap; + /** The maximum slow-start cwnd */ + uint32_t ss_cwnd_max; /** The queue use allowed before we exit slow start */ uint16_t gamma; /** The queue use below which we increment cwnd */ @@ -227,6 +231,16 @@ static inline uint64_t CWND_UPDATE_RATE(const struct congestion_control_t *cc) } }
+/** + * Gives us the number of SENDMEs in a CWND, rounded. + */ +static inline uint64_t SENDME_PER_CWND(const struct congestion_control_t *cc) +{ + /* We add cwnd_inc_rate*sendme_inc/2 to round to nearest integer number + * of acks */ + return ((cc->cwnd + cc->sendme_inc/2)/cc->sendme_inc); +} + /** * Returns the amount to increment the congestion window each update, * during slow start. diff --git a/src/core/or/congestion_control_vegas.c b/src/core/or/congestion_control_vegas.c index 5451d7849c..9e10e1311e 100644 --- a/src/core/or/congestion_control_vegas.c +++ b/src/core/or/congestion_control_vegas.c @@ -26,29 +26,35 @@
#define OUTBUF_CELLS (2*TLS_RECORD_MAX_CELLS)
+#define SS_CWND_MAX_DFLT (5000) + /* sbws circs are two hops, so params are based on 2 outbufs of cells */ #define VEGAS_ALPHA_SBWS_DFLT (2*OUTBUF_CELLS-TLS_RECORD_MAX_CELLS) #define VEGAS_BETA_SBWS_DFLT (2*OUTBUF_CELLS) #define VEGAS_GAMMA_SBWS_DFLT (2*OUTBUF_CELLS) #define VEGAS_DELTA_SBWS_DFLT (4*OUTBUF_CELLS) +#define VEGAS_SSCAP_SBWS_DFLT (400)
/* Exits are three hops, so params are based on 3 outbufs of cells */ #define VEGAS_ALPHA_EXIT_DFLT (3*OUTBUF_CELLS-TLS_RECORD_MAX_CELLS) #define VEGAS_BETA_EXIT_DFLT (3*OUTBUF_CELLS) #define VEGAS_GAMMA_EXIT_DFLT (3*OUTBUF_CELLS) #define VEGAS_DELTA_EXIT_DFLT (5*OUTBUF_CELLS) +#define VEGAS_SSCAP_EXIT_DFLT (500)
/* Onion rends are six hops, so params are based on 6 outbufs of cells */ #define VEGAS_ALPHA_ONION_DFLT (6*OUTBUF_CELLS-TLS_RECORD_MAX_CELLS) #define VEGAS_BETA_ONION_DFLT (6*OUTBUF_CELLS) #define VEGAS_GAMMA_ONION_DFLT (6*OUTBUF_CELLS) #define VEGAS_DELTA_ONION_DFLT (8*OUTBUF_CELLS) +#define VEGAS_SSCAP_ONION_DFLT (600)
/* Single Onions are three hops, so params are based on 3 outbufs of cells */ #define VEGAS_ALPHA_SOS_DFLT (3*OUTBUF_CELLS-TLS_RECORD_MAX_CELLS) #define VEGAS_BETA_SOS_DFLT (3*OUTBUF_CELLS) #define VEGAS_GAMMA_SOS_DFLT (3*OUTBUF_CELLS) #define VEGAS_DELTA_SOS_DFLT (5*OUTBUF_CELLS) +#define VEGAS_SSCAP_SOS_DFLT (500)
/* Vanguard Onions are 7 hops (or 8 if both sides use vanguards, but that * should be rare), so params are based on 7 outbufs of cells */ @@ -56,26 +62,15 @@ #define VEGAS_BETA_VG_DFLT (7*OUTBUF_CELLS) #define VEGAS_GAMMA_VG_DFLT (7*OUTBUF_CELLS) #define VEGAS_DELTA_VG_DFLT (9*OUTBUF_CELLS) - -#define VEGAS_BDP_MIX_PCT 100 +#define VEGAS_SSCAP_VG_DFLT (600)
/** - * The original TCP Vegas used only a congestion window BDP estimator. We - * believe that the piecewise estimator is likely to perform better, but - * for purposes of experimentation, we might as well have a way to blend - * them. It also lets us set Vegas to its original estimator while other - * algorithms on the same network use piecewise (by setting the - * 'vegas_bdp_mix_pct' consensus parameter to 100, while leaving the - * 'cc_bdp_alg' parameter set to piecewise). - * - * Returns a percentage weighted average between the CWND estimator and - * the specified consensus BDP estimator. + * The original TCP Vegas congestion window BDP estimator. */ static inline uint64_t -vegas_bdp_mix(const congestion_control_t *cc) +vegas_bdp(const congestion_control_t *cc) { - return cc->vegas_params.bdp_mix_pct*cc->bdp[BDP_ALG_CWND_RTT]/100 + - (100-cc->vegas_params.bdp_mix_pct)*cc->bdp[cc->bdp_alg]/100; + return cc->bdp[BDP_ALG_CWND_RTT]; }
/** @@ -87,8 +82,8 @@ congestion_control_vegas_set_params(congestion_control_t *cc, { tor_assert(cc->cc_alg == CC_ALG_VEGAS); const char *alpha_str = NULL, *beta_str = NULL, *gamma_str = NULL; - const char *delta_str = NULL; - int alpha, beta, gamma, delta; + const char *delta_str = NULL, *sscap_str = NULL; + int alpha, beta, gamma, delta, ss_cwnd_cap;
switch (path) { case CC_PATH_SBWS: @@ -96,56 +91,78 @@ congestion_control_vegas_set_params(congestion_control_t *cc, beta_str = "cc_vegas_beta_sbws"; gamma_str = "cc_vegas_gamma_sbws"; delta_str = "cc_vegas_delta_sbws"; + sscap_str = "cc_sscap_sbws"; alpha = VEGAS_ALPHA_SBWS_DFLT; beta = VEGAS_BETA_SBWS_DFLT; gamma = VEGAS_GAMMA_SBWS_DFLT; delta = VEGAS_DELTA_SBWS_DFLT; + ss_cwnd_cap = VEGAS_SSCAP_SBWS_DFLT; break; case CC_PATH_EXIT: alpha_str = "cc_vegas_alpha_exit"; beta_str = "cc_vegas_beta_exit"; gamma_str = "cc_vegas_gamma_exit"; delta_str = "cc_vegas_delta_exit"; + sscap_str = "cc_sscap_exit"; alpha = VEGAS_ALPHA_EXIT_DFLT; beta = VEGAS_BETA_EXIT_DFLT; gamma = VEGAS_GAMMA_EXIT_DFLT; delta = VEGAS_DELTA_EXIT_DFLT; + ss_cwnd_cap = VEGAS_SSCAP_EXIT_DFLT; break; case CC_PATH_ONION: alpha_str = "cc_vegas_alpha_onion"; beta_str = "cc_vegas_beta_onion"; gamma_str = "cc_vegas_gamma_onion"; delta_str = "cc_vegas_delta_onion"; + sscap_str = "cc_sscap_onion"; alpha = VEGAS_ALPHA_ONION_DFLT; beta = VEGAS_BETA_ONION_DFLT; gamma = VEGAS_GAMMA_ONION_DFLT; delta = VEGAS_DELTA_ONION_DFLT; + ss_cwnd_cap = VEGAS_SSCAP_ONION_DFLT; break; case CC_PATH_ONION_SOS: alpha_str = "cc_vegas_alpha_sos"; beta_str = "cc_vegas_beta_sos"; gamma_str = "cc_vegas_gamma_sos"; delta_str = "cc_vegas_delta_sos"; + sscap_str = "cc_sscap_sos"; alpha = VEGAS_ALPHA_SOS_DFLT; beta = VEGAS_BETA_SOS_DFLT; gamma = VEGAS_GAMMA_SOS_DFLT; delta = VEGAS_DELTA_SOS_DFLT; + ss_cwnd_cap = VEGAS_SSCAP_SOS_DFLT; break; case CC_PATH_ONION_VG: alpha_str = "cc_vegas_alpha_vg"; beta_str = "cc_vegas_beta_vg"; gamma_str = "cc_vegas_gamma_vg"; delta_str = "cc_vegas_delta_vg"; + sscap_str = "cc_sscap_vg"; alpha = VEGAS_ALPHA_VG_DFLT; beta = VEGAS_BETA_VG_DFLT; gamma = VEGAS_GAMMA_VG_DFLT; delta = VEGAS_DELTA_VG_DFLT; + ss_cwnd_cap = VEGAS_SSCAP_VG_DFLT; break; default: tor_assert(0); break; }
+ cc->vegas_params.ss_cwnd_cap = + networkstatus_get_param(NULL, sscap_str, + ss_cwnd_cap, + 100, + INT32_MAX); + + cc->vegas_params.ss_cwnd_max = + networkstatus_get_param(NULL, "cc_ss_max", + SS_CWND_MAX_DFLT, + 500, + INT32_MAX); + cc->vegas_params.alpha = networkstatus_get_param(NULL, alpha_str, alpha, @@ -169,12 +186,107 @@ congestion_control_vegas_set_params(congestion_control_t *cc, delta, 0, INT32_MAX); +}
- cc->vegas_params.bdp_mix_pct = - networkstatus_get_param(NULL, "cc_vegas_bdp_mix", - VEGAS_BDP_MIX_PCT, - 0, - 100); +/** + * Common log function for tracking all vegas state. + */ +static void +congestion_control_vegas_log(const circuit_t *circ, + const congestion_control_t *cc) +{ + uint64_t queue_use = cc->cwnd - vegas_bdp(cc); + + if (CIRCUIT_IS_ORIGIN(circ) && + circ->purpose == CIRCUIT_PURPOSE_S_REND_JOINED) { + log_info(LD_CIRC, + "CC: TOR_VEGAS Onion Circuit %d " + "RTT: %"PRIu64", %"PRIu64", %"PRIu64", " + "CWND: %"PRIu64", " + "INFL: %"PRIu64", " + "VBDP: %"PRIu64", " + "QUSE: %"PRIu64", " + "BWE: %"PRIu64", " + "SS: %d", + CONST_TO_ORIGIN_CIRCUIT(circ)->global_identifier, + cc->min_rtt_usec/1000, + cc->ewma_rtt_usec/1000, + cc->max_rtt_usec/1000, + cc->cwnd, + cc->inflight, + vegas_bdp(cc), + queue_use, + cc->cwnd*CELL_MAX_NETWORK_SIZE*1000/ + MAX(cc->min_rtt_usec,cc->ewma_rtt_usec), + cc->in_slow_start + ); + } else { + log_info(LD_CIRC, + "CC: TOR_VEGAS " + "RTT: %"PRIu64", %"PRIu64", %"PRIu64", " + "CWND: %"PRIu64", " + "INFL: %"PRIu64", " + "VBDP: %"PRIu64", " + "QUSE: %"PRIu64", " + "BWE: %"PRIu64", " + "SS: %d", + cc->min_rtt_usec/1000, + cc->ewma_rtt_usec/1000, + cc->max_rtt_usec/1000, + cc->cwnd, + cc->inflight, + vegas_bdp(cc), + queue_use, + cc->cwnd*CELL_MAX_NETWORK_SIZE*1000/ + MAX(cc->min_rtt_usec,cc->ewma_rtt_usec), + cc->in_slow_start + ); + } +} + +/** + * Implements RFC3742: Limited Slow Start. + * https://datatracker.ietf.org/doc/html/rfc3742#section-2 + */ +static inline uint64_t +rfc3742_ss_inc(const congestion_control_t *cc) +{ + if (cc->cwnd <= cc->vegas_params.ss_cwnd_cap) { + /* If less than the cap, round and always grow by at least 1 sendme_inc. */ + return ((uint64_t)cc->cwnd_inc_pct_ss*cc->sendme_inc + 50)/100; + } else { + // K = int(cwnd/(0.5 max_ssthresh)); + // => K = 2*cwnd/max_ssthresh + // cwnd += int(MSS/K); + // => cwnd += MSS*max_ssthresh/(2*cwnd) + return ((uint64_t)cc->sendme_inc*cc->vegas_params.ss_cwnd_cap + cc->cwnd)/ + (2*cc->cwnd); + } +} + +/** + * Exit Vegas slow start. + * + * This function sets our slow-start state to 0, and emits logs + * and control port information signifying end of slow start. + * It also schedules the next CWND update for steady-state. + */ +static void +congestion_control_vegas_exit_slow_start(const circuit_t *circ, + congestion_control_t *cc) +{ + congestion_control_vegas_log(circ, cc); + cc->in_slow_start = 0; + cc->next_cc_event = CWND_UPDATE_RATE(cc); + congestion_control_vegas_log(circ, cc); + + /* We need to report that slow start has exited ASAP, + * for sbws bandwidth measurement. */ + if (CIRCUIT_IS_ORIGIN(circ)) { + /* We must discard const here because the event modifies fields :/ */ + control_event_circ_bandwidth_used_for_circ( + TO_ORIGIN_CIRCUIT((circuit_t*)circ)); + } }
/** @@ -217,43 +329,45 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, return 0; }
- /* We only update anything once per window */ - if (cc->next_cc_event == 0) { - /* The queue use is the amount in which our cwnd is above BDP; - * if it is below, then 0 queue use. */ - if (vegas_bdp_mix(cc) > cc->cwnd) - queue_use = 0; - else - queue_use = cc->cwnd - vegas_bdp_mix(cc); - - if (cc->in_slow_start) { - if (queue_use < cc->vegas_params.gamma && !cc->blocked_chan) { - /* Grow to BDP immediately, then exponential growth until - * congestion signal. Increment by at least 2 sendme's worth. */ - cc->cwnd = MAX(cc->cwnd + MAX(CWND_INC_SS(cc), 2*cc->sendme_inc), - vegas_bdp_mix(cc)); + /* The queue use is the amount in which our cwnd is above BDP; + * if it is below, then 0 queue use. */ + if (vegas_bdp(cc) > cc->cwnd) + queue_use = 0; // This should not happen anymore.. + else + queue_use = cc->cwnd - vegas_bdp(cc); + + if (cc->in_slow_start) { + if (queue_use < cc->vegas_params.gamma && !cc->blocked_chan) { + /* Get the "Limited Slow Start" increment */ + uint64_t inc = rfc3742_ss_inc(cc); + + // Check if inc is less than what we would do in steady-state + // avoidance + if (inc*SENDME_PER_CWND(cc) <= CWND_INC(cc)) { + cc->cwnd += inc; + congestion_control_vegas_exit_slow_start(circ, cc); } else { - /* Congestion signal: Set cwnd to gamma threshhold */ - cc->cwnd = vegas_bdp_mix(cc) + cc->vegas_params.gamma; - cc->in_slow_start = 0; - log_info(LD_CIRC, "CC: TOR_VEGAS exiting slow start"); - - /* We need to report that slow start has exited ASAP, - * for sbws bandwidth measurement. */ - if (CIRCUIT_IS_ORIGIN(circ)) { - /* We must discard const here because the event modifies fields :/ */ - control_event_circ_bandwidth_used_for_circ( - TO_ORIGIN_CIRCUIT((circuit_t*)circ)); - } + cc->cwnd += inc; + cc->next_cc_event = 1; // Technically irellevant, but for consistency } } else { - if (queue_use > cc->vegas_params.delta) { - cc->cwnd = vegas_bdp_mix(cc) + cc->vegas_params.delta - CWND_INC(cc); - } else if (queue_use > cc->vegas_params.beta || cc->blocked_chan) { - cc->cwnd -= CWND_INC(cc); - } else if (queue_use < cc->vegas_params.alpha) { - cc->cwnd += CWND_INC(cc); - } + /* Congestion signal: Set cwnd to gamma threshhold */ + cc->cwnd = vegas_bdp(cc) + cc->vegas_params.gamma; + congestion_control_vegas_exit_slow_start(circ, cc); + } + + if (cc->cwnd >= cc->vegas_params.ss_cwnd_max) { + cc->cwnd = cc->vegas_params.ss_cwnd_max; + congestion_control_vegas_exit_slow_start(circ, cc); + } + /* After slow start, We only update once per window */ + } else if (cc->next_cc_event == 0) { + if (queue_use > cc->vegas_params.delta) { + cc->cwnd = vegas_bdp(cc) + cc->vegas_params.delta - CWND_INC(cc); + } else if (queue_use > cc->vegas_params.beta || cc->blocked_chan) { + cc->cwnd -= CWND_INC(cc); + } else if (queue_use < cc->vegas_params.alpha) { + cc->cwnd += CWND_INC(cc); }
/* cwnd can never fall below 1 increment */ @@ -262,41 +376,13 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, /* Schedule next update */ cc->next_cc_event = CWND_UPDATE_RATE(cc);
- if (CIRCUIT_IS_ORIGIN(circ)) { - log_info(LD_CIRC, - "CC: TOR_VEGAS Circuit %d " - "CWND: %"PRIu64", " - "INFL: %"PRIu64", " - "VBDP: %"PRIu64", " - "QUSE: %"PRIu64", " - "NCCE: %"PRIu64", " - "SS: %d", - CONST_TO_ORIGIN_CIRCUIT(circ)->global_identifier, - cc->cwnd, - cc->inflight, - vegas_bdp_mix(cc), - queue_use, - cc->next_cc_event, - cc->in_slow_start - ); - } else { + congestion_control_vegas_log(circ, cc); + + /* Log if we're above the ss_cap */ + if (cc->cwnd >= cc->vegas_params.ss_cwnd_max) { log_info(LD_CIRC, - "CC: TOR_VEGAS Circuit %"PRIu64":%d " - "CWND: %"PRIu64", " - "INFL: %"PRIu64", " - "VBDP: %"PRIu64", " - "QUSE: %"PRIu64", " - "NCCE: %"PRIu64", " - "SS: %d", - CONST_TO_OR_CIRCUIT(circ)->p_chan->global_identifier, - CONST_TO_OR_CIRCUIT(circ)->p_circ_id, - cc->cwnd, - cc->inflight, - vegas_bdp_mix(cc), - queue_use, - cc->next_cc_event, - cc->in_slow_start - ); + "CC: TOR_VEGAS above ss_max in steady state for circ %d: %"PRIu64, + circ->purpose, cc->cwnd); } }