diff options
author | David Goulet <dgoulet@torproject.org> | 2023-06-28 17:05:47 +0000 |
---|---|---|
committer | David Goulet <dgoulet@torproject.org> | 2023-06-28 17:05:47 +0000 |
commit | 05624b578152f3bdcc2e7ee8f49a87839839c22c (patch) | |
tree | fe740664ece478cb176807dad5cfae099e5315bb | |
parent | bcbc5b5ba0b8d1a72128dd6d2fa8d350110944b4 (diff) | |
parent | 5867ddefaedb63933c579101315e8978f4cdcab2 (diff) | |
download | tor-05624b578152f3bdcc2e7ee8f49a87839839c22c.tar.gz tor-05624b578152f3bdcc2e7ee8f49a87839839c22c.zip |
Merge branch 'bug40566' into 'main'
Remove unused congestion control and BDP algs
See merge request tpo/core/tor!725
-rw-r--r-- | changes/ticket40566 | 4 | ||||
-rw-r--r-- | src/core/or/congestion_control_common.c | 292 | ||||
-rw-r--r-- | src/core/or/congestion_control_common.h | 6 | ||||
-rw-r--r-- | src/core/or/congestion_control_nola.c | 139 | ||||
-rw-r--r-- | src/core/or/congestion_control_nola.h | 33 | ||||
-rw-r--r-- | src/core/or/congestion_control_st.h | 44 | ||||
-rw-r--r-- | src/core/or/congestion_control_vegas.c | 7 | ||||
-rw-r--r-- | src/core/or/congestion_control_vegas.h | 3 | ||||
-rw-r--r-- | src/core/or/congestion_control_westwood.c | 241 | ||||
-rw-r--r-- | src/core/or/congestion_control_westwood.h | 33 | ||||
-rw-r--r-- | src/core/or/include.am | 4 | ||||
-rw-r--r-- | src/core/or/lttng_cc.inc | 8 | ||||
-rw-r--r-- | src/core/or/sendme.c | 2 | ||||
-rw-r--r-- | src/test/test_conflux_pool.c | 2 | ||||
-rw-r--r-- | src/test/test_congestion_control.c | 2 |
15 files changed, 44 insertions, 776 deletions
diff --git a/changes/ticket40566 b/changes/ticket40566 new file mode 100644 index 0000000000..ce988de166 --- /dev/null +++ b/changes/ticket40566 @@ -0,0 +1,4 @@ + o Minor bugfix (congestion control): + - Remove unused congestion control algorithms and BDP calculation + code, now that we have settled on and fully tuned Vegas. Fixes + bug 40566; bugfix on 0.4.7.4-alpha. diff --git a/src/core/or/congestion_control_common.c b/src/core/or/congestion_control_common.c index f747987957..7dc9dbafdd 100644 --- a/src/core/or/congestion_control_common.c +++ b/src/core/or/congestion_control_common.c @@ -22,8 +22,6 @@ #include "core/or/congestion_control_st.h" #include "core/or/congestion_control_common.h" #include "core/or/congestion_control_vegas.h" -#include "core/or/congestion_control_nola.h" -#include "core/or/congestion_control_westwood.h" #include "core/or/congestion_control_st.h" #include "core/or/conflux.h" #include "core/or/conflux_util.h" @@ -88,8 +86,7 @@ static bool congestion_control_update_circuit_bdp(congestion_control_t *, const circuit_t *, - const crypt_path_t *, - uint64_t, uint64_t); + uint64_t); /* Number of times the RTT value was reset. For MetricsPort. */ static uint64_t num_rtt_reset; @@ -216,6 +213,13 @@ congestion_control_new_consensus_params(const networkstatus_t *ns) CC_ALG_DFLT, CC_ALG_MIN, CC_ALG_MAX); + if (cc_alg != CC_ALG_SENDME && cc_alg != CC_ALG_VEGAS) { + // Does not need rate limiting because consensus updates + // are at most 1x/hour + log_warn(LD_BUG, "Unsupported congestion control algorithm %d", + cc_alg); + cc_alg = CC_ALG_DFLT; + } #define BWE_SENDME_MIN_MIN 2 #define BWE_SENDME_MIN_MAX (20) @@ -316,37 +320,13 @@ congestion_control_init_params(congestion_control_t *cc, cc->cc_alg = cc_alg; } - bdp_alg_t default_bdp_alg = 0; - - switch (cc->cc_alg) { - case CC_ALG_WESTWOOD: - default_bdp_alg = WESTWOOD_BDP_ALG; - break; - case CC_ALG_VEGAS: - default_bdp_alg = VEGAS_BDP_MIX_ALG; - break; - case CC_ALG_NOLA: - default_bdp_alg = NOLA_BDP_ALG; - break; - case CC_ALG_SENDME: - default: - tor_fragile_assert(); - return; // No alg-specific params - } - - cc->bdp_alg = - networkstatus_get_param(NULL, "cc_bdp_alg", - default_bdp_alg, - 0, - NUM_BDP_ALGS-1); - /* Algorithm-specific parameters */ - if (cc->cc_alg == CC_ALG_WESTWOOD) { - congestion_control_westwood_set_params(cc); - } else if (cc->cc_alg == CC_ALG_VEGAS) { + if (cc->cc_alg == CC_ALG_VEGAS) { congestion_control_vegas_set_params(cc, path); - } else if (cc->cc_alg == CC_ALG_NOLA) { - congestion_control_nola_set_params(cc); + } else { + // This should not happen anymore + log_warn(LD_BUG, "Unknown congestion control algorithm %d", + cc->cc_alg); } } @@ -420,7 +400,6 @@ congestion_control_init(congestion_control_t *cc, cc_path_t path) { cc->sendme_pending_timestamps = smartlist_new(); - cc->sendme_arrival_timestamps = smartlist_new(); cc->in_slow_start = 1; congestion_control_init_params(cc, params, path); @@ -451,9 +430,7 @@ congestion_control_free_(congestion_control_t *cc) return; SMARTLIST_FOREACH(cc->sendme_pending_timestamps, uint64_t *, t, tor_free(t)); - SMARTLIST_FOREACH(cc->sendme_arrival_timestamps, uint64_t *, t, tor_free(t)); smartlist_free(cc->sendme_pending_timestamps); - smartlist_free(cc->sendme_arrival_timestamps); tor_free(cc); } @@ -471,22 +448,6 @@ enqueue_timestamp(smartlist_t *timestamps_u64, uint64_t timestamp_usec) } /** - * Peek at the head of a smartlist queue of u64 timestamps. - */ -static inline uint64_t -peek_timestamp(const smartlist_t *timestamps_u64_usecs) -{ - uint64_t *timestamp_ptr = smartlist_get(timestamps_u64_usecs, 0); - - if (BUG(!timestamp_ptr)) { - log_err(LD_CIRC, "Congestion control timestamp list became empty!"); - return 0; - } - - return *timestamp_ptr; -} - -/** * Dequeue a u64 monotime usec timestamp from the front of a * smartlist of pointers to 64. */ @@ -690,61 +651,6 @@ congestion_control_note_cell_sent(congestion_control_t *cc, } /** - * Returns true if any edge connections are active. - * - * We need to know this so that we can stop computing BDP if the - * edges are not sending on the circuit. - */ -static int -circuit_has_active_streams(const circuit_t *circ, - const crypt_path_t *layer_hint) -{ - const edge_connection_t *streams; - - if (CIRCUIT_IS_ORIGIN(circ)) { - streams = CONST_TO_ORIGIN_CIRCUIT(circ)->p_streams; - } else { - streams = CONST_TO_OR_CIRCUIT(circ)->n_streams; - } - - /* Check linked list of streams */ - for (const edge_connection_t *conn = streams; conn != NULL; - conn = conn->next_stream) { - if (conn->base_.marked_for_close) - continue; - - if (edge_uses_cpath(conn, layer_hint)) { - if (connection_get_inbuf_len(TO_CONN(conn)) > 0) { - log_info(LD_CIRC, "CC: More in edge inbuf..."); - return 1; - } - - /* If we did not reach EOF on this read, there's more */ - if (!TO_CONN(conn)->inbuf_reached_eof) { - log_info(LD_CIRC, "CC: More on edge conn..."); - return 1; - } - - if (TO_CONN(conn)->linked_conn) { - if (connection_get_inbuf_len(TO_CONN(conn)->linked_conn) > 0) { - log_info(LD_CIRC, "CC: More in linked inbuf..."); - return 1; - } - - /* If there is a linked conn, and *it* did not each EOF, - * there's more */ - if (!TO_CONN(conn)->linked_conn->inbuf_reached_eof) { - log_info(LD_CIRC, "CC: More on linked conn..."); - return 1; - } - } - } - } - - return 0; -} - -/** * Upon receipt of a SENDME, pop the oldest timestamp off the timestamp * list, and use this to update RTT. * @@ -753,15 +659,13 @@ circuit_has_active_streams(const circuit_t *circ, */ bool congestion_control_update_circuit_estimates(congestion_control_t *cc, - const circuit_t *circ, - const crypt_path_t *layer_hint) + const circuit_t *circ) { uint64_t now_usec = monotime_absolute_usec(); /* Update RTT first, then BDP. BDP needs fresh RTT */ uint64_t curr_rtt_usec = congestion_control_update_circuit_rtt(cc, now_usec); - return congestion_control_update_circuit_bdp(cc, circ, layer_hint, now_usec, - curr_rtt_usec); + return congestion_control_update_circuit_bdp(cc, circ, curr_rtt_usec); } /** @@ -777,13 +681,6 @@ time_delta_should_use_heuristics(const congestion_control_t *cc) return true; } - /* If we managed to get enough acks to estimate a SENDME BDP, then - * we have enough to estimate clock jumps relative to a baseline, - * too. (This is at least 'cc_bwe_min' acks). */ - if (cc->bdp[BDP_ALG_SENDME_RATE]) { - return true; - } - /* Not enough data to estimate clock jumps */ return false; } @@ -950,14 +847,10 @@ congestion_control_update_circuit_rtt(congestion_control_t *cc, static bool congestion_control_update_circuit_bdp(congestion_control_t *cc, const circuit_t *circ, - const crypt_path_t *layer_hint, - uint64_t now_usec, uint64_t curr_rtt_usec) { int chan_q = 0; unsigned int blocked_on_chan = 0; - uint64_t timestamp_usec; - uint64_t sendme_rate_bdp = 0; tor_assert(cc); @@ -995,10 +888,7 @@ congestion_control_update_circuit_bdp(congestion_control_t *cc, cc->blocked_chan = 0; } - cc->bdp[BDP_ALG_CWND_RTT] = cwnd; - cc->bdp[BDP_ALG_INFLIGHT_RTT] = cwnd; - cc->bdp[BDP_ALG_SENDME_RATE] = cwnd; - cc->bdp[BDP_ALG_PIECEWISE] = cwnd; + cc->bdp = cwnd; static ratelim_t dec_notice_limit = RATELIM_INIT(300); log_fn_ratelim(&dec_notice_limit, LOG_NOTICE, LD_CIRC, @@ -1017,84 +907,7 @@ congestion_control_update_circuit_bdp(congestion_control_t *cc, * close to ewma RTT. Since all fields are u64, there is plenty of * room here to multiply first. */ - cc->bdp[BDP_ALG_CWND_RTT] = cc->cwnd*cc->min_rtt_usec/cc->ewma_rtt_usec; - - /* - * If we have no pending streams, we do not have enough data to fill - * the BDP, so preserve our old estimates but do not make any more. - */ - if (!blocked_on_chan && !circuit_has_active_streams(circ, layer_hint)) { - log_info(LD_CIRC, - "CC: Streams drained. Spare package window: %"PRIu64 - ", no BDP update", cc->cwnd - cc->inflight); - - /* Clear SENDME timestamps; they will be wrong with intermittent data */ - SMARTLIST_FOREACH(cc->sendme_arrival_timestamps, uint64_t *, t, - tor_free(t)); - smartlist_clear(cc->sendme_arrival_timestamps); - } else if (curr_rtt_usec && is_monotime_clock_reliable()) { - /* Sendme-based BDP will quickly measure BDP in much less than - * a cwnd worth of data when in use (in 2-10 SENDMEs). - * - * But if the link goes idle, it will be vastly lower than true BDP. Hence - * we only compute it if we have either pending stream data, or streams - * are still blocked on the channel queued data. - * - * We also do not compute it if we do not have a current RTT passed in, - * because that means that monotime is currently stalled or just jumped. - */ - enqueue_timestamp(cc->sendme_arrival_timestamps, now_usec); - - if (smartlist_len(cc->sendme_arrival_timestamps) >= bwe_sendme_min) { - /* If we have more sendmes than fit in a cwnd, trim the list. - * Those are not acurrately measuring throughput, if cwnd is - * currently smaller than BDP */ - while (smartlist_len(cc->sendme_arrival_timestamps) > - bwe_sendme_min && - (uint64_t)smartlist_len(cc->sendme_arrival_timestamps) > - n_ewma_count(cc)) { - (void)dequeue_timestamp(cc->sendme_arrival_timestamps); - } - int sendme_cnt = smartlist_len(cc->sendme_arrival_timestamps); - - /* Calculate SENDME_BWE_COUNT pure average */ - timestamp_usec = peek_timestamp(cc->sendme_arrival_timestamps); - uint64_t delta = now_usec - timestamp_usec; - - /* In Shadow, the time delta between acks can be 0 if there is no - * network activity between them. Only update BDP if the delta is - * non-zero. */ - if (delta > 0) { - /* The acked data is in sendme_cnt-1 chunks, because we are counting - * the data that is processed by the other endpoint *between* all of - * these sendmes. There's one less gap between the sendmes than the - * number of sendmes. */ - uint64_t cells = (sendme_cnt-1)*cc->sendme_inc; - - /* The bandwidth estimate is cells/delta, which when multiplied - * by min RTT obtains the BDP. However, we multiply first to - * avoid precision issues with the RTT being close to delta in size. */ - sendme_rate_bdp = cells*cc->min_rtt_usec/delta; - - /* Calculate BDP_EWMA_COUNT N-EWMA */ - cc->bdp[BDP_ALG_SENDME_RATE] = - n_count_ewma(sendme_rate_bdp, cc->bdp[BDP_ALG_SENDME_RATE], - n_ewma_count(cc)); - } - } - - /* In-flight BDP will cause the cwnd to drift down when underutilized. - * It is most useful when the local OR conn is blocked, so we only - * compute it if we're utilized. */ - cc->bdp[BDP_ALG_INFLIGHT_RTT] = - (cc->inflight - chan_q)*cc->min_rtt_usec/ - MAX(cc->ewma_rtt_usec, curr_rtt_usec); - } else { - /* We can still update inflight with just an EWMA RTT, but only - * if there is data flowing */ - cc->bdp[BDP_ALG_INFLIGHT_RTT] = - (cc->inflight - chan_q)*cc->min_rtt_usec/cc->ewma_rtt_usec; - } + cc->bdp = cc->cwnd*cc->min_rtt_usec/cc->ewma_rtt_usec; /* The orconn is blocked; use smaller of inflight vs SENDME */ if (blocked_on_chan) { @@ -1107,13 +920,6 @@ congestion_control_update_circuit_bdp(congestion_control_t *cc, cc->next_cc_event = 0; cc->blocked_chan = 1; } - - if (cc->bdp[BDP_ALG_SENDME_RATE]) { - cc->bdp[BDP_ALG_PIECEWISE] = MIN(cc->bdp[BDP_ALG_INFLIGHT_RTT], - cc->bdp[BDP_ALG_SENDME_RATE]); - } else { - cc->bdp[BDP_ALG_PIECEWISE] = cc->bdp[BDP_ALG_INFLIGHT_RTT]; - } } else { /* If we were previously blocked, emit a new congestion event * now that we are unblocked, to re-evaluate cwnd */ @@ -1123,19 +929,6 @@ congestion_control_update_circuit_bdp(congestion_control_t *cc, log_info(LD_CIRC, "CC: Streams un-blocked on circ channel. Chanq: %d", chan_q); } - - cc->bdp[BDP_ALG_PIECEWISE] = MAX(cc->bdp[BDP_ALG_SENDME_RATE], - cc->bdp[BDP_ALG_CWND_RTT]); - } - - /* We can end up with no piecewise value if we didn't have either - * a SENDME estimate or enough data for an inflight estimate. - * It also happens on the very first sendme, since we need two - * to get a BDP. In these cases, use the cwnd method. */ - if (!cc->bdp[BDP_ALG_PIECEWISE]) { - cc->bdp[BDP_ALG_PIECEWISE] = cc->bdp[BDP_ALG_CWND_RTT]; - log_info(LD_CIRC, "CC: No piecewise BDP. Using %"PRIu64, - cc->bdp[BDP_ALG_PIECEWISE]); } if (cc->next_cc_event == 0) { @@ -1143,44 +936,25 @@ congestion_control_update_circuit_bdp(congestion_control_t *cc, log_info(LD_CIRC, "CC: Circuit %d " "SENDME RTT: %"PRIu64", %"PRIu64", %"PRIu64", %"PRIu64", " - "BDP estimates: " - "%"PRIu64", " - "%"PRIu64", " - "%"PRIu64", " - "%"PRIu64", " - "%"PRIu64". ", + "BDP estimate: %"PRIu64, CONST_TO_ORIGIN_CIRCUIT(circ)->global_identifier, cc->min_rtt_usec/1000, curr_rtt_usec/1000, cc->ewma_rtt_usec/1000, cc->max_rtt_usec/1000, - cc->bdp[BDP_ALG_INFLIGHT_RTT], - cc->bdp[BDP_ALG_CWND_RTT], - sendme_rate_bdp, - cc->bdp[BDP_ALG_SENDME_RATE], - cc->bdp[BDP_ALG_PIECEWISE] - ); + cc->bdp); } else { log_info(LD_CIRC, "CC: Circuit %"PRIu64":%d " "SENDME RTT: %"PRIu64", %"PRIu64", %"PRIu64", %"PRIu64", " - "%"PRIu64", " - "%"PRIu64", " - "%"PRIu64", " - "%"PRIu64", " - "%"PRIu64". ", + "%"PRIu64, CONST_TO_OR_CIRCUIT(circ)->p_chan->global_identifier, CONST_TO_OR_CIRCUIT(circ)->p_circ_id, cc->min_rtt_usec/1000, curr_rtt_usec/1000, cc->ewma_rtt_usec/1000, cc->max_rtt_usec/1000, - cc->bdp[BDP_ALG_INFLIGHT_RTT], - cc->bdp[BDP_ALG_CWND_RTT], - sendme_rate_bdp, - cc->bdp[BDP_ALG_SENDME_RATE], - cc->bdp[BDP_ALG_PIECEWISE] - ); + cc->bdp); } } @@ -1188,8 +962,7 @@ congestion_control_update_circuit_bdp(congestion_control_t *cc, * the curr_rtt_usec was not 0. */ bool ret = (blocked_on_chan || curr_rtt_usec != 0); if (ret) { - tor_trace(TR_SUBSYS(cc), TR_EV(bdp_update), circ, cc, curr_rtt_usec, - sendme_rate_bdp); + tor_trace(TR_SUBSYS(cc), TR_EV(bdp_update), circ, cc, curr_rtt_usec); } return ret; } @@ -1199,27 +972,12 @@ congestion_control_update_circuit_bdp(congestion_control_t *cc, */ int congestion_control_dispatch_cc_alg(congestion_control_t *cc, - circuit_t *circ, - const crypt_path_t *layer_hint) + circuit_t *circ) { int ret = -END_CIRC_REASON_INTERNAL; - switch (cc->cc_alg) { - case CC_ALG_WESTWOOD: - ret = congestion_control_westwood_process_sendme(cc, circ, layer_hint); - break; - - case CC_ALG_VEGAS: - ret = congestion_control_vegas_process_sendme(cc, circ, layer_hint); - break; - - case CC_ALG_NOLA: - ret = congestion_control_nola_process_sendme(cc, circ, layer_hint); - break; - case CC_ALG_SENDME: - default: - tor_assert(0); - } + tor_assert_nonfatal_once(cc->cc_alg == CC_ALG_VEGAS); + ret = congestion_control_vegas_process_sendme(cc, circ); if (cc->cwnd > cwnd_max) { static ratelim_t cwnd_limit = RATELIM_INIT(60); diff --git a/src/core/or/congestion_control_common.h b/src/core/or/congestion_control_common.h index 92c78c5ebd..e185a5d29e 100644 --- a/src/core/or/congestion_control_common.h +++ b/src/core/or/congestion_control_common.h @@ -46,16 +46,14 @@ congestion_control_t *congestion_control_new( cc_path_t path); int congestion_control_dispatch_cc_alg(congestion_control_t *cc, - circuit_t *circ, - const crypt_path_t *layer_hint); + circuit_t *circ); void congestion_control_note_cell_sent(congestion_control_t *cc, const circuit_t *circ, const crypt_path_t *cpath); bool congestion_control_update_circuit_estimates(congestion_control_t *, - const circuit_t *, - const crypt_path_t *); + const circuit_t *); int congestion_control_get_package_window(const circuit_t *, const crypt_path_t *); diff --git a/src/core/or/congestion_control_nola.c b/src/core/or/congestion_control_nola.c deleted file mode 100644 index d8ad69a78c..0000000000 --- a/src/core/or/congestion_control_nola.c +++ /dev/null @@ -1,139 +0,0 @@ -/* Copyright (c) 2019-2021, The Tor Project, Inc. */ -/* See LICENSE for licensing information */ - -/** - * \file congestion_control_nola.c - * \brief Code that implements the TOR_NOLA congestion control algorithm - * from Proposal #324. - */ - -#define TOR_CONGESTION_CONTROL_NOLA_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_nola.h" -#include "core/or/circuituse.h" -#include "core/or/circuitlist.h" -#include "core/or/origin_circuit_st.h" -#include "core/or/channel.h" -#include "feature/nodelist/networkstatus.h" -#include "feature/control/control_events.h" - -#define NOLA_BDP_OVERSHOOT 100 - -/** - * Cache NOLA consensus parameters. - */ -void -congestion_control_nola_set_params(congestion_control_t *cc) -{ - tor_assert(cc->cc_alg == CC_ALG_NOLA); - - cc->nola_params.bdp_overshoot = - networkstatus_get_param(NULL, "cc_nola_overshoot", - NOLA_BDP_OVERSHOOT, - 0, - 1000); -} - -/** -* Process a SENDME and update the congestion window according to the -* rules specified in TOR_NOLA of Proposal #324. -* -* TOR_NOLA updates the congestion window to match the current -* BDP estimate, every sendme. Because this can result in downward -* drift, a fixed overhead is added to the BDP estimate. This will -* cause some queuing, but ensures that the algorithm always uses -* the full BDP. -* -* To handle the case where the local orconn blocks, TOR_NOLA uses -* the 'piecewise' BDP estimate, which uses more a conservative BDP -* estimate method when blocking occurs, but a more aggressive BDP -* estimate when there is no local blocking. This minimizes local -* client queues. -*/ -int -congestion_control_nola_process_sendme(congestion_control_t *cc, - const circuit_t *circ, - const crypt_path_t *layer_hint) -{ - tor_assert(cc && cc->cc_alg == CC_ALG_NOLA); - tor_assert(circ); - - if (cc->next_cc_event) - cc->next_cc_event--; - - /* If we get a congestion event, the only thing NOLA - * does is note this as if we exited slow-start - * (which for NOLA just means we finished our ICW). */ - if (cc->next_cc_event == 0) { - if (cc->in_slow_start) { - cc->in_slow_start = 0; - - /* 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)); - } - } - } - - /* If we did not successfully update BDP, we must return. Otherwise, - * NOLA can drift downwards */ - if (!congestion_control_update_circuit_estimates(cc, circ, layer_hint)) { - cc->inflight = cc->inflight - cc->sendme_inc; - return 0; - } - - /* We overshoot the BDP by the cwnd_inc param amount, because BDP - * may otherwise drift down. This helps us probe for more capacity. - * But there is no sense to do it if the local channel is blocked. */ - if (cc->blocked_chan) - cc->cwnd = cc->bdp[cc->bdp_alg]; - else - cc->cwnd = cc->bdp[cc->bdp_alg] + cc->nola_params.bdp_overshoot; - - /* cwnd can never fall below 1 increment */ - cc->cwnd = MAX(cc->cwnd, cc->cwnd_min); - - if (CIRCUIT_IS_ORIGIN(circ)) { - log_info(LD_CIRC, - "CC TOR_NOLA: Circuit %d " - "CWND: %"PRIu64", " - "INFL: %"PRIu64", " - "NCCE: %"PRIu16", " - "SS: %d", - CONST_TO_ORIGIN_CIRCUIT(circ)->global_identifier, - cc->cwnd, - cc->inflight, - cc->next_cc_event, - cc->in_slow_start - ); - } else { - log_info(LD_CIRC, - "CC TOR_NOLA: Circuit %"PRIu64":%d " - "CWND: %"PRIu64", " - "INFL: %"PRIu64", " - "NCCE: %"PRIu16", " - "SS: %d", - CONST_TO_OR_CIRCUIT(circ)->p_chan->global_identifier, - CONST_TO_OR_CIRCUIT(circ)->p_circ_id, - cc->cwnd, - cc->inflight, - cc->next_cc_event, - 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_nola.h b/src/core/or/congestion_control_nola.h deleted file mode 100644 index 9c7d6e0635..0000000000 --- a/src/core/or/congestion_control_nola.h +++ /dev/null @@ -1,33 +0,0 @@ -/* Copyright (c) 2019-2021, The Tor Project, Inc. */ -/* See LICENSE for licensing information */ - -/** - * \file congestion_control_nola.h - * \brief Private-ish APIs for the TOR_NOLA congestion control algorithm - **/ - -#ifndef TOR_CONGESTION_CONTROL_NOLA_H -#define TOR_CONGESTION_CONTROL_NOLA_H - -#include "core/or/crypt_path_st.h" -#include "core/or/circuit_st.h" - -/* Processing SENDME cell. */ -int congestion_control_nola_process_sendme(struct congestion_control_t *cc, - const circuit_t *circ, - const crypt_path_t *layer_hint); -void congestion_control_nola_set_params(struct congestion_control_t *cc); - -/* Private section starts. */ -#ifdef TOR_CONGESTION_CONTROL_NOLA_PRIVATE - -/* - * Unit tests declaractions. - */ -#ifdef TOR_UNIT_TESTS - -#endif /* defined(TOR_UNIT_TESTS) */ - -#endif /* defined(TOR_CONGESTION_CONTROL_NOLA_PRIVATE) */ - -#endif /* !defined(TOR_CONGESTION_CONTROL_NOLA_H) */ diff --git a/src/core/or/congestion_control_st.h b/src/core/or/congestion_control_st.h index 84d36868de..b87d230c2f 100644 --- a/src/core/or/congestion_control_st.h +++ b/src/core/or/congestion_control_st.h @@ -79,22 +79,6 @@ typedef enum { /** Total number of BDP algs in bdp_alg_t enum */ #define NUM_BDP_ALGS (BDP_ALG_PIECEWISE+1) -/** Westwood algorithm parameters */ -struct westwood_params_t { - /** Cwnd backoff multiplier upon congestion (as percent) */ - uint8_t cwnd_backoff_m; - /** Max RTT backoff multiplier upon congestion (as percent) */ - uint8_t rtt_backoff_m; - - /** Threshold between min and max RTT, to signal congestion (percent) */ - uint8_t rtt_thresh; - - /** - * If true, use minimum of BDP and backoff multiplication in backoff. - * If false, use maximum of BDP and backoff multiplication in backoff. */ - bool min_backoff; -}; - /** Vegas algorithm parameters. */ struct vegas_params_t { /** The slow-start cwnd cap for RFC3742 */ @@ -114,12 +98,6 @@ struct vegas_params_t { uint8_t bdp_mix_pct; }; -/** NOLA consensus params */ -struct nola_params_t { - /** How many cells to add to BDP estimate to obtain cwnd */ - uint16_t bdp_overshoot; -}; - /** Fields common to all congestion control algorithms */ struct congestion_control_t { /** @@ -128,19 +106,13 @@ struct congestion_control_t { * sendme_last_digests. */ smartlist_t *sendme_pending_timestamps; - /** - * Smartlist of uint64_t monotime timestamp of when sendme's arrived. - * FIFO queue that is managed similar to sendme_last_digests. - * Used to estimate circuitbandwidth and BDP. */ - smartlist_t *sendme_arrival_timestamps; - /** RTT time data for congestion control. */ uint64_t ewma_rtt_usec; uint64_t min_rtt_usec; uint64_t max_rtt_usec; - /* BDP estimates by algorithm */ - uint64_t bdp[NUM_BDP_ALGS]; + /* Vegas BDP estimate */ + uint64_t bdp; /** Congestion window */ uint64_t cwnd; @@ -203,15 +175,9 @@ struct congestion_control_t { * consensus parameter during circuit setup. */ bdp_alg_t bdp_alg; - /** Algorithm-specific parameters. The specific struct that is used - * depends upon the algorithm selected by the cc_alg parameter. - * These should not be accessed anywhere other than the algorithm-specific - * files. */ - union { - struct westwood_params_t westwood_params; - struct vegas_params_t vegas_params; - struct nola_params_t nola_params; - }; + /** Vegas-specific parameters. These should not be accessed anywhere + * other than the congestion_control_vegas.c file. */ + struct vegas_params_t vegas_params; }; /** diff --git a/src/core/or/congestion_control_vegas.c b/src/core/or/congestion_control_vegas.c index b611fc50c4..97f1dc0a0e 100644 --- a/src/core/or/congestion_control_vegas.c +++ b/src/core/or/congestion_control_vegas.c @@ -98,7 +98,7 @@ uint64_t cc_stats_vegas_circ_exited_ss = 0; static inline uint64_t vegas_bdp(const congestion_control_t *cc) { - return cc->bdp[BDP_ALG_CWND_RTT]; + return cc->bdp; } /** @@ -405,8 +405,7 @@ cwnd_full_reset(const congestion_control_t *cc) */ int congestion_control_vegas_process_sendme(congestion_control_t *cc, - const circuit_t *circ, - const crypt_path_t *layer_hint) + const circuit_t *circ) { uint64_t queue_use; @@ -422,7 +421,7 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, cc->next_cwnd_event--; /* Compute BDP and RTT. If we did not update, don't run the alg */ - if (!congestion_control_update_circuit_estimates(cc, circ, layer_hint)) { + if (!congestion_control_update_circuit_estimates(cc, circ)) { cc->inflight = cc->inflight - cc->sendme_inc; return 0; } diff --git a/src/core/or/congestion_control_vegas.h b/src/core/or/congestion_control_vegas.h index 84070664c8..24af16822c 100644 --- a/src/core/or/congestion_control_vegas.h +++ b/src/core/or/congestion_control_vegas.h @@ -35,8 +35,7 @@ extern uint64_t cc_stats_vegas_circ_exited_ss; /* Processing SENDME cell. */ int congestion_control_vegas_process_sendme(struct congestion_control_t *cc, - const circuit_t *circ, - const crypt_path_t *layer_hint); + const circuit_t *circ); void congestion_control_vegas_set_params(struct congestion_control_t *cc, cc_path_t path); diff --git a/src/core/or/congestion_control_westwood.c b/src/core/or/congestion_control_westwood.c deleted file mode 100644 index d28ddf3442..0000000000 --- a/src/core/or/congestion_control_westwood.c +++ /dev/null @@ -1,241 +0,0 @@ -/* 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" -#include "feature/control/control_events.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 threshold that signals congestion. - * - * Computed from the threshold parameter that specifies a - * percent between the min and max RTT observed 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 threshold, - * 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 threshold of 'rtt_thresh', which - * is a midpoint between the min and max RTT. If the RTT exceeds this - * threshold, then queue delay due to congestion is assumed to be present, - * and the algorithm reduces the congestion window. If the RTT is below the - * threshold, 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); - - /* 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)); - } - } - - /* 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: %"PRIu16", " - "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: %"PRIu16", " - "WRTT: %"PRIu64", " - "WSIG: %"PRIu64", " - "SS: %d", - CONST_TO_OR_CIRCUIT(circ)->p_chan->global_identifier, - CONST_TO_OR_CIRCUIT(circ)->p_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 deleted file mode 100644 index c6fd596df4..0000000000 --- a/src/core/or/congestion_control_westwood.h +++ /dev/null @@ -1,33 +0,0 @@ -/* 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) */ diff --git a/src/core/or/include.am b/src/core/or/include.am index 12456b98dd..d0dffd5d3b 100644 --- a/src/core/or/include.am +++ b/src/core/or/include.am @@ -36,8 +36,6 @@ LIBTOR_APP_A_SOURCES += \ src/core/or/sendme.c \ src/core/or/congestion_control_common.c \ src/core/or/congestion_control_vegas.c \ - src/core/or/congestion_control_nola.c \ - src/core/or/congestion_control_westwood.c \ src/core/or/congestion_control_flow.c \ src/core/or/conflux.c \ src/core/or/conflux_cell.c \ @@ -112,8 +110,6 @@ noinst_HEADERS += \ src/core/or/congestion_control_flow.h \ src/core/or/congestion_control_common.h \ src/core/or/congestion_control_vegas.h \ - src/core/or/congestion_control_nola.h \ - src/core/or/congestion_control_westwood.h \ src/core/or/conflux.h \ src/core/or/conflux_cell.h \ src/core/or/conflux_params.h \ diff --git a/src/core/or/lttng_cc.inc b/src/core/or/lttng_cc.inc index de06fa026f..d315be91f7 100644 --- a/src/core/or/lttng_cc.inc +++ b/src/core/or/lttng_cc.inc @@ -142,7 +142,7 @@ TRACEPOINT_EVENT(tor_cc, flow_decide_xoff_sending, /* Emitted when the BDP value has been updated. */ TRACEPOINT_EVENT(tor_cc, bdp_update, TP_ARGS(const circuit_t *, circ, const congestion_control_t *, cc, - uint64_t, curr_rtt_usec, uint64_t, sendme_rate_bdp), + uint64_t, curr_rtt_usec), TP_FIELDS( ctf_integer(uint64_t, circuit_ptr, circ) ctf_integer(uint32_t, n_circ_id, circ->n_circ_id) @@ -150,11 +150,7 @@ TRACEPOINT_EVENT(tor_cc, bdp_update, ctf_integer(uint64_t, curr_rtt_usec, curr_rtt_usec) ctf_integer(uint64_t, ewma_rtt_usec, cc->ewma_rtt_usec) ctf_integer(uint64_t, max_rtt_usec, cc->max_rtt_usec) - ctf_integer(uint64_t, bdp_inflight_rtt, cc->bdp[BDP_ALG_INFLIGHT_RTT]) - ctf_integer(uint64_t, bdp_cwnd_rtt, cc->bdp[BDP_ALG_CWND_RTT]) - ctf_integer(uint64_t, bdp_sendme_rate, cc->bdp[BDP_ALG_SENDME_RATE]) - ctf_integer(uint64_t, bdp_piecewise, cc->bdp[BDP_ALG_PIECEWISE]) - ctf_integer(uint64_t, sendme_rate_bdp, sendme_rate_bdp) + ctf_integer(uint64_t, bdp_cwnd_rtt, cc->bdp) ) ) diff --git a/src/core/or/sendme.c b/src/core/or/sendme.c index 4bb5c268b0..03af990484 100644 --- a/src/core/or/sendme.c +++ b/src/core/or/sendme.c @@ -491,7 +491,7 @@ sendme_process_circuit_level(crypt_path_t *layer_hint, return sendme_process_circuit_level_impl(layer_hint, circ); } - return congestion_control_dispatch_cc_alg(cc, circ, layer_hint); + return congestion_control_dispatch_cc_alg(cc, circ); } /** diff --git a/src/test/test_conflux_pool.c b/src/test/test_conflux_pool.c index ad78283fe3..fc30677377 100644 --- a/src/test/test_conflux_pool.c +++ b/src/test/test_conflux_pool.c @@ -128,7 +128,6 @@ circuit_establish_circuit_conflux_mock(const uint8_t *conflux_nonce, simulate_single_hop_extend(circ, 0); simulate_single_hop_extend(circ, 1); circ->cpath->prev->ccontrol = tor_malloc_zero(sizeof(congestion_control_t)); - circ->cpath->prev->ccontrol->sendme_arrival_timestamps = smartlist_new(); circ->cpath->prev->ccontrol->sendme_pending_timestamps = smartlist_new(); circ->cpath->prev->ccontrol->sendme_inc = 31; @@ -499,7 +498,6 @@ simulate_circuit_build(circuit_t *client_circ) relay_side->purpose = CIRCUIT_PURPOSE_OR; relay_side->n_chan = NULL; // No next hop relay_side->ccontrol = tor_malloc_zero(sizeof(congestion_control_t)); - relay_side->ccontrol->sendme_arrival_timestamps = smartlist_new(); relay_side->ccontrol->sendme_pending_timestamps = smartlist_new(); relay_side->ccontrol->sendme_inc = 31; smartlist_add(exit_circs, relay_side); diff --git a/src/test/test_congestion_control.c b/src/test/test_congestion_control.c index f494515e99..26095d310a 100644 --- a/src/test/test_congestion_control.c +++ b/src/test/test_congestion_control.c @@ -216,7 +216,7 @@ run_vegas_cwnd_test_vec(congestion_control_t *cc, circ->circuit_blocked_on_p_chan = vec[i].or_conn_blocked_in; cc->inflight = vec[i].inflight_in; - congestion_control_vegas_process_sendme(cc, circ, NULL); + congestion_control_vegas_process_sendme(cc, circ); /* If the or conn was blocked, ensure we updated our * CC state */ |