aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDavid Goulet <dgoulet@torproject.org>2023-06-28 17:05:47 +0000
committerDavid Goulet <dgoulet@torproject.org>2023-06-28 17:05:47 +0000
commit05624b578152f3bdcc2e7ee8f49a87839839c22c (patch)
treefe740664ece478cb176807dad5cfae099e5315bb
parentbcbc5b5ba0b8d1a72128dd6d2fa8d350110944b4 (diff)
parent5867ddefaedb63933c579101315e8978f4cdcab2 (diff)
downloadtor-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/ticket405664
-rw-r--r--src/core/or/congestion_control_common.c292
-rw-r--r--src/core/or/congestion_control_common.h6
-rw-r--r--src/core/or/congestion_control_nola.c139
-rw-r--r--src/core/or/congestion_control_nola.h33
-rw-r--r--src/core/or/congestion_control_st.h44
-rw-r--r--src/core/or/congestion_control_vegas.c7
-rw-r--r--src/core/or/congestion_control_vegas.h3
-rw-r--r--src/core/or/congestion_control_westwood.c241
-rw-r--r--src/core/or/congestion_control_westwood.h33
-rw-r--r--src/core/or/include.am4
-rw-r--r--src/core/or/lttng_cc.inc8
-rw-r--r--src/core/or/sendme.c2
-rw-r--r--src/test/test_conflux_pool.c2
-rw-r--r--src/test/test_congestion_control.c2
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 */