commit 33cd92922a0353111735797832e9ca3e7180eba9 Author: Mike Perry <mikeperry-git@torproject.org> Date: Sun Jun 13 02:20:00 2021 +0000 TOR_WESTWOOD: Implement Prop#324 TOR_WESTWOOD --- src/core/or/congestion_control_westwood.c | 231 ++++++++++++++++++++++++++++++ src/core/or/congestion_control_westwood.h | 33 +++++ 2 files changed, 264 insertions(+) diff --git a/src/core/or/congestion_control_westwood.c b/src/core/or/congestion_control_westwood.c new file mode 100644 index 0000000000..4b24234212 --- /dev/null +++ b/src/core/or/congestion_control_westwood.c @@ -0,0 +1,231 @@ +/* Copyright (c) 2019-2021, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file congestion_control_westwood.c + * \brief Code that implements the TOR_WESTWOOD congestion control algorithm + * from Proposal #324. + */ + +#define TOR_CONGESTION_CONTROL_WESTWOOD_PRIVATE + +#include "core/or/or.h" + +#include "core/or/crypt_path.h" +#include "core/or/or_circuit_st.h" +#include "core/or/sendme.h" +#include "core/or/congestion_control_st.h" +#include "core/or/congestion_control_common.h" +#include "core/or/congestion_control_westwood.h" +#include "core/or/circuitlist.h" +#include "core/or/circuituse.h" +#include "core/or/origin_circuit_st.h" +#include "core/or/channel.h" +#include "feature/nodelist/networkstatus.h" + +#define USEC_ONE_MS (1000) + +#define WESTWOOD_CWND_BACKOFF_M 75 +#define WESTWOOD_RTT_BACKOFF_M 100 +#define WESTWOOD_RTT_THRESH 33 +#define WESTWOOD_MIN_BACKOFF 0 + +/** + * Cache westwood consensus parameters. + */ +void +congestion_control_westwood_set_params(congestion_control_t *cc) +{ + tor_assert(cc->cc_alg == CC_ALG_WESTWOOD); + + cc->westwood_params.cwnd_backoff_m = + networkstatus_get_param(NULL, "cc_westwood_cwnd_m", + WESTWOOD_CWND_BACKOFF_M, + 0, + 100); + + cc->westwood_params.rtt_backoff_m = + networkstatus_get_param(NULL, "cc_westwood_rtt_m", + WESTWOOD_RTT_BACKOFF_M, + 50, + 100); + + cc->westwood_params.rtt_thresh = + networkstatus_get_param(NULL, "cc_westwood_rtt_thresh", + WESTWOOD_RTT_THRESH, + 0, + 100); + + cc->westwood_params.min_backoff = + networkstatus_get_param(NULL, "cc_westwood_min_backoff", + WESTWOOD_MIN_BACKOFF, + 0, + 1); +} + +/** + * Return the RTT threshhold that signals congestion. + * + * Computed from the threshold parameter that specifies a + * percent between the min and max RTT obseved so far. + */ +static inline uint64_t +westwood_rtt_signal(const congestion_control_t *cc) +{ + return ((100 - cc->westwood_params.rtt_thresh)*cc->min_rtt_usec + + cc->westwood_params.rtt_thresh*(cc)->max_rtt_usec)/100; +} + +/** + * Compute a backoff to reduce the max RTT. + * + * This may be necessary to ensure that westwood does not have + * a runaway condition where congestion inflates the max RTT, which + * inflates the congestion threshold. That cannot happen with one + * Westwood instance, but it may happen in aggregate. Hence, this is + * a safety parameter, in case we need it. + */ +static inline uint64_t +westwood_rtt_max_backoff(const congestion_control_t *cc) +{ + return cc->min_rtt_usec + + (cc->westwood_params.rtt_backoff_m * + (cc->max_rtt_usec - cc->min_rtt_usec))/100; +} + +/** + * Returns true if the circuit is experiencing congestion, as per + * TOR_WESTWOOD rules. + */ +static inline bool +westwood_is_congested(const congestion_control_t *cc) +{ + /* If the local channel is blocked, that is always congestion */ + if (cc->blocked_chan) + return true; + + /* If the min RTT is within 1ms of the signal, then there is not enough + * range in RTTs to signify congestion. Treat that as not congested. */ + if (westwood_rtt_signal(cc) < cc->min_rtt_usec || + westwood_rtt_signal(cc) - cc->min_rtt_usec < USEC_ONE_MS) + return false; + + /* If the EWMA-smoothed RTT exceeds the westwood RTT threshhold, + * then it is congestion. */ + if (cc->ewma_rtt_usec > westwood_rtt_signal(cc)) + return true; + + return false; +} + +/** + * Process a SENDME and update the congestion window according to the + * rules specified in TOR_WESTWOOD of Proposal #324. + * + * Essentially, this algorithm uses a threshhold of 'rtt_thresh', which + * is a midpoint between the min and max RTT. If the RTT exceeds this + * threshhold, then queue delay due to congestion is assumed to be present, + * and the algirithm reduces the congestion window. If the RTT is below the + * threshhold, the circuit is not congested (ie: queue delay is low), and we + * increase the congestion window. + * + * The congestion window is updated only once every congestion window worth of + * packets, even if the signal persists. It is also updated whenever the + * upstream orcon blocks, or unblocks. This minimizes local client queues. + */ +int +congestion_control_westwood_process_sendme(congestion_control_t *cc, + const circuit_t *circ, + const crypt_path_t *layer_hint) +{ + tor_assert(cc && cc->cc_alg == CC_ALG_WESTWOOD); + tor_assert(circ); + + /* Update ack counter until next congestion signal event is allowed */ + if (cc->next_cc_event) + cc->next_cc_event--; + + /* If we were unable to update our circuit estimates, Westwood must + * *not* update its cwnd, otherwise it could run to infinity, or to 0. + * Just update inflight from the sendme and return. */ + if (!congestion_control_update_circuit_estimates(cc, circ, layer_hint)) { + cc->inflight = cc->inflight - cc->sendme_inc; + return 0; + } + + /* We only update anything once per window */ + if (cc->next_cc_event == 0) { + if (!westwood_is_congested(cc)) { + if (cc->in_slow_start) { + cc->cwnd = MAX(cc->cwnd + CWND_INC_SS(cc), + cc->bdp[cc->bdp_alg]); + } else { + cc->cwnd = cc->cwnd + CWND_INC(cc); + } + } else { + if (cc->westwood_params.min_backoff) + cc->cwnd = MIN(cc->cwnd*cc->westwood_params.cwnd_backoff_m/100, + cc->bdp[cc->bdp_alg]); + else + cc->cwnd = MAX(cc->cwnd*cc->westwood_params.cwnd_backoff_m/100, + cc->bdp[cc->bdp_alg]); + + cc->in_slow_start = 0; + + // Because Westwood's congestion can runaway and boost max rtt, + // which increases its congestion signal, we backoff the max rtt + // too. + cc->max_rtt_usec = westwood_rtt_max_backoff(cc); + + log_info(LD_CIRC, "CC: TOR_WESTWOOD congestion. New max RTT: %"PRIu64, + cc->max_rtt_usec/1000); + } + + /* cwnd can never fall below 1 increment */ + cc->cwnd = MAX(cc->cwnd, cc->cwnd_min); + + /* Schedule next update */ + cc->next_cc_event = CWND_UPDATE_RATE(cc); + + if (CIRCUIT_IS_ORIGIN(circ)) { + log_info(LD_CIRC, + "CC: TOR_WESTWOOD Circuit %d " + "CWND: %"PRIu64", " + "INFL: %"PRIu64", " + "NCCE: %"PRIu64", " + "WRTT: %"PRIu64", " + "WSIG: %"PRIu64", " + "SS: %d", + CONST_TO_ORIGIN_CIRCUIT(circ)->global_identifier, + cc->cwnd, + cc->inflight, + cc->next_cc_event, + cc->ewma_rtt_usec/1000, + westwood_rtt_signal(cc)/1000, + cc->in_slow_start + ); + } else { + log_info(LD_CIRC, + "CC: TOR_WESTWOOD Circuit %"PRIu64":%d " + "CWND: %"PRIu64", " + "INFL: %"PRIu64", " + "NCCE: %"PRIu64", " + "WRTT: %"PRIu64", " + "WSIG: %"PRIu64", " + "SS: %d", + circ->n_chan->global_identifier, circ->n_circ_id, + cc->cwnd, + cc->inflight, + cc->next_cc_event, + cc->ewma_rtt_usec/1000, + westwood_rtt_signal(cc)/1000, + cc->in_slow_start + ); + } + } + + /* Update inflight with ack */ + cc->inflight = cc->inflight - cc->sendme_inc; + + return 0; +} diff --git a/src/core/or/congestion_control_westwood.h b/src/core/or/congestion_control_westwood.h new file mode 100644 index 0000000000..c6fd596df4 --- /dev/null +++ b/src/core/or/congestion_control_westwood.h @@ -0,0 +1,33 @@ +/* Copyright (c) 2019-2021, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file congestion_control_westwood.h + * \brief Private-ish APIs for the TOR_WESTWOOD congestion control algorithm + **/ + +#ifndef TOR_CONGESTION_CONTROL_WESTWOOD_H +#define TOR_CONGESTION_CONTROL_WESTWOOD_H + +#include "core/or/crypt_path_st.h" +#include "core/or/circuit_st.h" + +/* Processing SENDME cell. */ +int congestion_control_westwood_process_sendme(struct congestion_control_t *cc, + const circuit_t *circ, + const crypt_path_t *layer_hint); +void congestion_control_westwood_set_params(struct congestion_control_t *cc); + +/* Private section starts. */ +#ifdef TOR_CONGESTION_CONTROL_WESTWOOD_PRIVATE + +/* + * Unit tests declaractions. + */ +#ifdef TOR_UNIT_TESTS + +#endif /* defined(TOR_UNIT_TESTS) */ + +#endif /* defined(TOR_CONGESTION_CONTROL_WESTWOOD_PRIVATE) */ + +#endif /* !defined(TOR_CONGESTION_CONTROL_WESTWOOD_H) */