1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
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;
}
|
