1/*-
2 * Copyright (c) 2009-2010
3 * Swinburne University of Technology, Melbourne, Australia
4 * Copyright (c) 2010-2011 The FreeBSD Foundation
5 * All rights reserved.
6 *
7 * This software was developed at the Centre for Advanced Internet
8 * Architectures, Swinburne University of Technology, by David Hayes and
9 * Lawrence Stewart, made possible in part by a grant from the Cisco University
10 * Research Program Fund at Community Foundation Silicon Valley.
11 *
12 * Portions of this software were developed at the Centre for Advanced Internet
13 * Architectures, Swinburne University of Technology, Melbourne, Australia by
14 * David Hayes under sponsorship from the FreeBSD Foundation.
15 *
16 * Redistribution and use in source and binary forms, with or without
17 * modification, are permitted provided that the following conditions
18 * are met:
19 * 1. Redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer.
21 * 2. Redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 */
37
38/*
39 * An implementation of the CAIA-Hamilton delay based congestion control
40 * algorithm, based on "Improved coexistence and loss tolerance for delay based
41 * TCP congestion control" by D. A. Hayes and G. Armitage., in 35th Annual IEEE
42 * Conference on Local Computer Networks (LCN 2010), Denver, Colorado, USA,
43 * 11-14 October 2010.
44 *
45 * Originally released as part of the NewTCP research project at Swinburne
46 * University of Technology's Centre for Advanced Internet Architectures,
47 * Melbourne, Australia, which was made possible in part by a grant from the
48 * Cisco University Research Program Fund at Community Foundation Silicon
49 * Valley. More details are available at:
50 * http://caia.swin.edu.au/urp/newtcp/
51 */
52
53#include <sys/cdefs.h>
| 1/*-
2 * Copyright (c) 2009-2010
3 * Swinburne University of Technology, Melbourne, Australia
4 * Copyright (c) 2010-2011 The FreeBSD Foundation
5 * All rights reserved.
6 *
7 * This software was developed at the Centre for Advanced Internet
8 * Architectures, Swinburne University of Technology, by David Hayes and
9 * Lawrence Stewart, made possible in part by a grant from the Cisco University
10 * Research Program Fund at Community Foundation Silicon Valley.
11 *
12 * Portions of this software were developed at the Centre for Advanced Internet
13 * Architectures, Swinburne University of Technology, Melbourne, Australia by
14 * David Hayes under sponsorship from the FreeBSD Foundation.
15 *
16 * Redistribution and use in source and binary forms, with or without
17 * modification, are permitted provided that the following conditions
18 * are met:
19 * 1. Redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer.
21 * 2. Redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 */
37
38/*
39 * An implementation of the CAIA-Hamilton delay based congestion control
40 * algorithm, based on "Improved coexistence and loss tolerance for delay based
41 * TCP congestion control" by D. A. Hayes and G. Armitage., in 35th Annual IEEE
42 * Conference on Local Computer Networks (LCN 2010), Denver, Colorado, USA,
43 * 11-14 October 2010.
44 *
45 * Originally released as part of the NewTCP research project at Swinburne
46 * University of Technology's Centre for Advanced Internet Architectures,
47 * Melbourne, Australia, which was made possible in part by a grant from the
48 * Cisco University Research Program Fund at Community Foundation Silicon
49 * Valley. More details are available at:
50 * http://caia.swin.edu.au/urp/newtcp/
51 */
52
53#include <sys/cdefs.h>
|
75#include <netinet/cc/cc_module.h>
76
77#include <netinet/khelp/h_ertt.h>
78
79#define CAST_PTR_INT(X) (*((int*)(X)))
80
81/*
82 * Private signal type for rate based congestion signal.
83 * See <netinet/cc.h> for appropriate bit-range to use for private signals.
84 */
85#define CC_CHD_DELAY 0x02000000
86
87/* Largest possible number returned by random(). */
88#define RANDOM_MAX INT_MAX
89
90static void chd_ack_received(struct cc_var *ccv, uint16_t ack_type);
91static void chd_cb_destroy(struct cc_var *ccv);
92static int chd_cb_init(struct cc_var *ccv);
93static void chd_cong_signal(struct cc_var *ccv, uint32_t signal_type);
94static void chd_conn_init(struct cc_var *ccv);
95static int chd_mod_init(void);
96
97struct chd {
98 /*
99 * Shadow window - keeps track of what the NewReno congestion window
100 * would have been if delay-based cwnd backoffs had not been made. This
101 * functionality aids coexistence with loss-based TCP flows which may be
102 * sharing links along the path.
103 */
104 unsigned long shadow_w;
105 /*
106 * Loss-based TCP compatibility flag - When set, it turns on the shadow
107 * window functionality.
108 */
109 int loss_compete;
110 /* The maximum round trip time seen within a measured rtt period. */
111 int maxrtt_in_rtt;
112 /* The previous qdly that caused cwnd to backoff. */
113 int prev_backoff_qdly;
114};
115
116static int ertt_id;
117
118static VNET_DEFINE(uint32_t, chd_qmin) = 5;
119static VNET_DEFINE(uint32_t, chd_pmax) = 50;
120static VNET_DEFINE(uint32_t, chd_loss_fair) = 1;
121static VNET_DEFINE(uint32_t, chd_use_max) = 1;
122static VNET_DEFINE(uint32_t, chd_qthresh) = 20;
123#define V_chd_qthresh VNET(chd_qthresh)
124#define V_chd_qmin VNET(chd_qmin)
125#define V_chd_pmax VNET(chd_pmax)
126#define V_chd_loss_fair VNET(chd_loss_fair)
127#define V_chd_use_max VNET(chd_use_max)
128
129static MALLOC_DEFINE(M_CHD, "chd data",
130 "Per connection data required for the CHD congestion control algorithm");
131
132struct cc_algo chd_cc_algo = {
133 .name = "chd",
134 .ack_received = chd_ack_received,
135 .cb_destroy = chd_cb_destroy,
136 .cb_init = chd_cb_init,
137 .cong_signal = chd_cong_signal,
138 .conn_init = chd_conn_init,
139 .mod_init = chd_mod_init
140};
141
142static __inline void
143chd_window_decrease(struct cc_var *ccv)
144{
145 unsigned long win;
146
147 win = min(CCV(ccv, snd_wnd), CCV(ccv, snd_cwnd)) / CCV(ccv, t_maxseg);
148 win -= max((win / 2), 1);
149 CCV(ccv, snd_ssthresh) = max(win, 2) * CCV(ccv, t_maxseg);
150}
151
152/*
153 * Probabilistic backoff function. Returns 1 if we should backoff or 0
154 * otherwise. The calculation of p is similar to the calculation of p in cc_hd.
155 */
156static __inline int
157should_backoff(int qdly, int maxqdly, struct chd *chd_data)
158{
159 unsigned long p, rand;
160
161 rand = random();
162
163 if (qdly < V_chd_qthresh) {
164 chd_data->loss_compete = 0;
165 p = (((RANDOM_MAX / 100) * V_chd_pmax) /
166 (V_chd_qthresh - V_chd_qmin)) *
167 (qdly - V_chd_qmin);
168 } else {
169 if (qdly > V_chd_qthresh) {
170 p = (((RANDOM_MAX / 100) * V_chd_pmax) /
171 (maxqdly - V_chd_qthresh)) *
172 (maxqdly - qdly);
173 if (V_chd_loss_fair && rand < p)
174 chd_data->loss_compete = 1;
175 } else {
176 p = (RANDOM_MAX / 100) * V_chd_pmax;
177 chd_data->loss_compete = 0;
178 }
179 }
180
181 return (rand < p);
182}
183
184static __inline void
185chd_window_increase(struct cc_var *ccv, int new_measurement)
186{
187 struct chd *chd_data;
188 int incr;
189
190 chd_data = ccv->cc_data;
191 incr = 0;
192
193 if (CCV(ccv, snd_cwnd) <= CCV(ccv, snd_ssthresh)) {
194 /* Adapted from NewReno slow start. */
195 if (V_tcp_do_rfc3465) {
196 /* In slow-start with ABC enabled. */
197 if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max)) {
198 /* Not due to RTO. */
199 incr = min(ccv->bytes_this_ack,
200 V_tcp_abc_l_var * CCV(ccv, t_maxseg));
201 } else {
202 /* Due to RTO. */
203 incr = min(ccv->bytes_this_ack,
204 CCV(ccv, t_maxseg));
205 }
206 } else
207 incr = CCV(ccv, t_maxseg);
208
209 } else { /* Congestion avoidance. */
210 if (V_tcp_do_rfc3465) {
211 if (ccv->flags & CCF_ABC_SENTAWND) {
212 ccv->flags &= ~CCF_ABC_SENTAWND;
213 incr = CCV(ccv, t_maxseg);
214 }
215 } else if (new_measurement)
216 incr = CCV(ccv, t_maxseg);
217 }
218
219 if (chd_data->shadow_w > 0) {
220 /* Track NewReno window. */
221 chd_data->shadow_w = min(chd_data->shadow_w + incr,
222 TCP_MAXWIN << CCV(ccv, snd_scale));
223 }
224
225 CCV(ccv,snd_cwnd) = min(CCV(ccv, snd_cwnd) + incr,
226 TCP_MAXWIN << CCV(ccv, snd_scale));
227}
228
229/*
230 * All ACK signals are used for timing measurements to determine delay-based
231 * congestion. However, window increases are only performed when
232 * ack_type == CC_ACK.
233 */
234static void
235chd_ack_received(struct cc_var *ccv, uint16_t ack_type)
236{
237 struct chd *chd_data;
238 struct ertt *e_t;
239 int backoff, new_measurement, qdly, rtt;
240
241 e_t = khelp_get_osd(CCV(ccv, osd), ertt_id);
242 chd_data = ccv->cc_data;
243 new_measurement = e_t->flags & ERTT_NEW_MEASUREMENT;
244 backoff = qdly = 0;
245
246 chd_data->maxrtt_in_rtt = imax(e_t->rtt, chd_data->maxrtt_in_rtt);
247
248 if (new_measurement) {
249 /*
250 * There is a new per RTT measurement, so check to see if there
251 * is delay based congestion.
252 */
253 rtt = V_chd_use_max ? chd_data->maxrtt_in_rtt : e_t->rtt;
254 chd_data->maxrtt_in_rtt = 0;
255
256 if (rtt && e_t->minrtt && !IN_RECOVERY(CCV(ccv, t_flags))) {
257 qdly = rtt - e_t->minrtt;
258 if (qdly > V_chd_qmin) {
259 /*
260 * Probabilistic delay based congestion
261 * indication.
262 */
263 backoff = should_backoff(qdly,
264 e_t->maxrtt - e_t->minrtt, chd_data);
265 } else
266 chd_data->loss_compete = 0;
267 }
268 /* Reset per RTT measurement flag to start a new measurement. */
269 e_t->flags &= ~ERTT_NEW_MEASUREMENT;
270 }
271
272 if (backoff) {
273 /*
274 * Update shadow_w before delay based backoff.
275 */
276 if (chd_data->loss_compete ||
277 qdly > chd_data->prev_backoff_qdly) {
278 /*
279 * Delay is higher than when we backed off previously,
280 * so it is possible that this flow is competing with
281 * loss based flows.
282 */
283 chd_data->shadow_w = max(CCV(ccv, snd_cwnd),
284 chd_data->shadow_w);
285 } else {
286 /*
287 * Reset shadow_w, as it is probable that this flow is
288 * not competing with loss based flows at the moment.
289 */
290 chd_data->shadow_w = 0;
291 }
292
293 chd_data->prev_backoff_qdly = qdly;
294 /*
295 * Send delay-based congestion signal to the congestion signal
296 * handler.
297 */
298 chd_cong_signal(ccv, CC_CHD_DELAY);
299
300 } else if (ack_type == CC_ACK)
301 chd_window_increase(ccv, new_measurement);
302}
303
304static void
305chd_cb_destroy(struct cc_var *ccv)
306{
307
308 if (ccv->cc_data != NULL)
309 free(ccv->cc_data, M_CHD);
310}
311
312static int
313chd_cb_init(struct cc_var *ccv)
314{
315 struct chd *chd_data;
316
317 chd_data = malloc(sizeof(struct chd), M_CHD, M_NOWAIT);
318 if (chd_data == NULL)
319 return (ENOMEM);
320
321 chd_data->shadow_w = 0;
322 ccv->cc_data = chd_data;
323
324 return (0);
325}
326
327static void
328chd_cong_signal(struct cc_var *ccv, uint32_t signal_type)
329{
330 struct ertt *e_t;
331 struct chd *chd_data;
332 int qdly;
333
334 e_t = khelp_get_osd(CCV(ccv, osd), ertt_id);
335 chd_data = ccv->cc_data;
336 qdly = imax(e_t->rtt, chd_data->maxrtt_in_rtt) - e_t->minrtt;
337
338 switch(signal_type) {
339 case CC_CHD_DELAY:
340 chd_window_decrease(ccv); /* Set new ssthresh. */
341 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
342 CCV(ccv, snd_recover) = CCV(ccv, snd_max);
343 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
344 break;
345
346 case CC_NDUPACK: /* Packet loss. */
347 /*
348 * Only react to loss as a congestion signal if qdly >
349 * V_chd_qthresh. If qdly is less than qthresh, presume that
350 * this is a non congestion related loss. If qdly is greater
351 * than qthresh, assume that we are competing with loss based
352 * tcp flows and restore window from any unnecessary backoffs,
353 * before the decrease.
354 */
355 if (!IN_RECOVERY(CCV(ccv, t_flags)) && qdly > V_chd_qthresh) {
356 if (chd_data->loss_compete) {
357 CCV(ccv, snd_cwnd) = max(CCV(ccv, snd_cwnd),
358 chd_data->shadow_w);
359 }
360 chd_window_decrease(ccv);
361 } else {
362 /*
363 * This loss isn't congestion related, or already
364 * recovering from congestion.
365 */
366 CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd);
367 CCV(ccv, snd_recover) = CCV(ccv, snd_max);
368 }
369
370 if (chd_data->shadow_w > 0) {
371 chd_data->shadow_w = max(chd_data->shadow_w /
372 CCV(ccv, t_maxseg) / 2, 2) * CCV(ccv, t_maxseg);
373 }
374 ENTER_FASTRECOVERY(CCV(ccv, t_flags));
375 break;
376
377 default:
378 newreno_cc_algo.cong_signal(ccv, signal_type);
379 }
380}
381
382static void
383chd_conn_init(struct cc_var *ccv)
384{
385 struct chd *chd_data;
386
387 chd_data = ccv->cc_data;
388 chd_data->prev_backoff_qdly = 0;
389 chd_data->maxrtt_in_rtt = 0;
390 chd_data->loss_compete = 0;
391 /*
392 * Initialise the shadow_cwnd to be equal to snd_cwnd in case we are
393 * competing with loss based flows from the start.
394 */
395 chd_data->shadow_w = CCV(ccv, snd_cwnd);
396}
397
398static int
399chd_mod_init(void)
400{
401
402 ertt_id = khelp_get_id("ertt");
403 if (ertt_id <= 0) {
404 printf("%s: h_ertt module not found\n", __func__);
405 return (ENOENT);
406 }
407
408 chd_cc_algo.after_idle = newreno_cc_algo.after_idle;
409 chd_cc_algo.post_recovery = newreno_cc_algo.post_recovery;
410
411 return (0);
412}
413
414static int
415chd_loss_fair_handler(SYSCTL_HANDLER_ARGS)
416{
417 int error;
418 uint32_t new;
419
420 new = V_chd_loss_fair;
421 error = sysctl_handle_int(oidp, &new, 0, req);
422 if (error == 0 && req->newptr != NULL) {
423 if (CAST_PTR_INT(req->newptr) > 1)
424 error = EINVAL;
425 else
426 V_chd_loss_fair = new;
427 }
428
429 return (error);
430}
431
432static int
433chd_pmax_handler(SYSCTL_HANDLER_ARGS)
434{
435 int error;
436 uint32_t new;
437
438 new = V_chd_pmax;
439 error = sysctl_handle_int(oidp, &new, 0, req);
440 if (error == 0 && req->newptr != NULL) {
441 if (CAST_PTR_INT(req->newptr) == 0 ||
442 CAST_PTR_INT(req->newptr) > 100)
443 error = EINVAL;
444 else
445 V_chd_pmax = new;
446 }
447
448 return (error);
449}
450
451static int
452chd_qthresh_handler(SYSCTL_HANDLER_ARGS)
453{
454 int error;
455 uint32_t new;
456
457 new = V_chd_qthresh;
458 error = sysctl_handle_int(oidp, &new, 0, req);
459 if (error == 0 && req->newptr != NULL) {
460 if (CAST_PTR_INT(req->newptr) <= V_chd_qmin)
461 error = EINVAL;
462 else
463 V_chd_qthresh = new;
464 }
465
466 return (error);
467}
468
469SYSCTL_DECL(_net_inet_tcp_cc_chd);
470SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, chd, CTLFLAG_RW, NULL,
471 "CAIA Hamilton delay-based congestion control related settings");
472
473SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, loss_fair,
474 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
475 &VNET_NAME(chd_loss_fair), 1, &chd_loss_fair_handler,
476 "IU", "Flag to enable shadow window functionality.");
477
478SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, pmax,
479 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
480 &VNET_NAME(chd_pmax), 5, &chd_pmax_handler,
481 "IU", "Per RTT maximum backoff probability as a percentage");
482
483SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, queue_threshold,
484 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
485 &VNET_NAME(chd_qthresh), 20, &chd_qthresh_handler,
486 "IU", "Queueing congestion threshold in ticks");
487
488SYSCTL_UINT(_net_inet_tcp_cc_chd, OID_AUTO, queue_min,
489 CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_qmin), 5,
490 "Minimum queueing delay threshold in ticks");
491
492SYSCTL_UINT(_net_inet_tcp_cc_chd, OID_AUTO, use_max,
493 CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_use_max), 1,
494 "Use the maximum RTT seen within the measurement period (RTT) "
495 "as the basic delay measurement for the algorithm.");
496
497DECLARE_CC_MODULE(chd, &chd_cc_algo);
498MODULE_DEPEND(chd, ertt, 1, 1, 1);
| 75#include <netinet/cc/cc_module.h>
76
77#include <netinet/khelp/h_ertt.h>
78
79#define CAST_PTR_INT(X) (*((int*)(X)))
80
81/*
82 * Private signal type for rate based congestion signal.
83 * See <netinet/cc.h> for appropriate bit-range to use for private signals.
84 */
85#define CC_CHD_DELAY 0x02000000
86
87/* Largest possible number returned by random(). */
88#define RANDOM_MAX INT_MAX
89
90static void chd_ack_received(struct cc_var *ccv, uint16_t ack_type);
91static void chd_cb_destroy(struct cc_var *ccv);
92static int chd_cb_init(struct cc_var *ccv);
93static void chd_cong_signal(struct cc_var *ccv, uint32_t signal_type);
94static void chd_conn_init(struct cc_var *ccv);
95static int chd_mod_init(void);
96
97struct chd {
98 /*
99 * Shadow window - keeps track of what the NewReno congestion window
100 * would have been if delay-based cwnd backoffs had not been made. This
101 * functionality aids coexistence with loss-based TCP flows which may be
102 * sharing links along the path.
103 */
104 unsigned long shadow_w;
105 /*
106 * Loss-based TCP compatibility flag - When set, it turns on the shadow
107 * window functionality.
108 */
109 int loss_compete;
110 /* The maximum round trip time seen within a measured rtt period. */
111 int maxrtt_in_rtt;
112 /* The previous qdly that caused cwnd to backoff. */
113 int prev_backoff_qdly;
114};
115
116static int ertt_id;
117
118static VNET_DEFINE(uint32_t, chd_qmin) = 5;
119static VNET_DEFINE(uint32_t, chd_pmax) = 50;
120static VNET_DEFINE(uint32_t, chd_loss_fair) = 1;
121static VNET_DEFINE(uint32_t, chd_use_max) = 1;
122static VNET_DEFINE(uint32_t, chd_qthresh) = 20;
123#define V_chd_qthresh VNET(chd_qthresh)
124#define V_chd_qmin VNET(chd_qmin)
125#define V_chd_pmax VNET(chd_pmax)
126#define V_chd_loss_fair VNET(chd_loss_fair)
127#define V_chd_use_max VNET(chd_use_max)
128
129static MALLOC_DEFINE(M_CHD, "chd data",
130 "Per connection data required for the CHD congestion control algorithm");
131
132struct cc_algo chd_cc_algo = {
133 .name = "chd",
134 .ack_received = chd_ack_received,
135 .cb_destroy = chd_cb_destroy,
136 .cb_init = chd_cb_init,
137 .cong_signal = chd_cong_signal,
138 .conn_init = chd_conn_init,
139 .mod_init = chd_mod_init
140};
141
142static __inline void
143chd_window_decrease(struct cc_var *ccv)
144{
145 unsigned long win;
146
147 win = min(CCV(ccv, snd_wnd), CCV(ccv, snd_cwnd)) / CCV(ccv, t_maxseg);
148 win -= max((win / 2), 1);
149 CCV(ccv, snd_ssthresh) = max(win, 2) * CCV(ccv, t_maxseg);
150}
151
152/*
153 * Probabilistic backoff function. Returns 1 if we should backoff or 0
154 * otherwise. The calculation of p is similar to the calculation of p in cc_hd.
155 */
156static __inline int
157should_backoff(int qdly, int maxqdly, struct chd *chd_data)
158{
159 unsigned long p, rand;
160
161 rand = random();
162
163 if (qdly < V_chd_qthresh) {
164 chd_data->loss_compete = 0;
165 p = (((RANDOM_MAX / 100) * V_chd_pmax) /
166 (V_chd_qthresh - V_chd_qmin)) *
167 (qdly - V_chd_qmin);
168 } else {
169 if (qdly > V_chd_qthresh) {
170 p = (((RANDOM_MAX / 100) * V_chd_pmax) /
171 (maxqdly - V_chd_qthresh)) *
172 (maxqdly - qdly);
173 if (V_chd_loss_fair && rand < p)
174 chd_data->loss_compete = 1;
175 } else {
176 p = (RANDOM_MAX / 100) * V_chd_pmax;
177 chd_data->loss_compete = 0;
178 }
179 }
180
181 return (rand < p);
182}
183
184static __inline void
185chd_window_increase(struct cc_var *ccv, int new_measurement)
186{
187 struct chd *chd_data;
188 int incr;
189
190 chd_data = ccv->cc_data;
191 incr = 0;
192
193 if (CCV(ccv, snd_cwnd) <= CCV(ccv, snd_ssthresh)) {
194 /* Adapted from NewReno slow start. */
195 if (V_tcp_do_rfc3465) {
196 /* In slow-start with ABC enabled. */
197 if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max)) {
198 /* Not due to RTO. */
199 incr = min(ccv->bytes_this_ack,
200 V_tcp_abc_l_var * CCV(ccv, t_maxseg));
201 } else {
202 /* Due to RTO. */
203 incr = min(ccv->bytes_this_ack,
204 CCV(ccv, t_maxseg));
205 }
206 } else
207 incr = CCV(ccv, t_maxseg);
208
209 } else { /* Congestion avoidance. */
210 if (V_tcp_do_rfc3465) {
211 if (ccv->flags & CCF_ABC_SENTAWND) {
212 ccv->flags &= ~CCF_ABC_SENTAWND;
213 incr = CCV(ccv, t_maxseg);
214 }
215 } else if (new_measurement)
216 incr = CCV(ccv, t_maxseg);
217 }
218
219 if (chd_data->shadow_w > 0) {
220 /* Track NewReno window. */
221 chd_data->shadow_w = min(chd_data->shadow_w + incr,
222 TCP_MAXWIN << CCV(ccv, snd_scale));
223 }
224
225 CCV(ccv,snd_cwnd) = min(CCV(ccv, snd_cwnd) + incr,
226 TCP_MAXWIN << CCV(ccv, snd_scale));
227}
228
229/*
230 * All ACK signals are used for timing measurements to determine delay-based
231 * congestion. However, window increases are only performed when
232 * ack_type == CC_ACK.
233 */
234static void
235chd_ack_received(struct cc_var *ccv, uint16_t ack_type)
236{
237 struct chd *chd_data;
238 struct ertt *e_t;
239 int backoff, new_measurement, qdly, rtt;
240
241 e_t = khelp_get_osd(CCV(ccv, osd), ertt_id);
242 chd_data = ccv->cc_data;
243 new_measurement = e_t->flags & ERTT_NEW_MEASUREMENT;
244 backoff = qdly = 0;
245
246 chd_data->maxrtt_in_rtt = imax(e_t->rtt, chd_data->maxrtt_in_rtt);
247
248 if (new_measurement) {
249 /*
250 * There is a new per RTT measurement, so check to see if there
251 * is delay based congestion.
252 */
253 rtt = V_chd_use_max ? chd_data->maxrtt_in_rtt : e_t->rtt;
254 chd_data->maxrtt_in_rtt = 0;
255
256 if (rtt && e_t->minrtt && !IN_RECOVERY(CCV(ccv, t_flags))) {
257 qdly = rtt - e_t->minrtt;
258 if (qdly > V_chd_qmin) {
259 /*
260 * Probabilistic delay based congestion
261 * indication.
262 */
263 backoff = should_backoff(qdly,
264 e_t->maxrtt - e_t->minrtt, chd_data);
265 } else
266 chd_data->loss_compete = 0;
267 }
268 /* Reset per RTT measurement flag to start a new measurement. */
269 e_t->flags &= ~ERTT_NEW_MEASUREMENT;
270 }
271
272 if (backoff) {
273 /*
274 * Update shadow_w before delay based backoff.
275 */
276 if (chd_data->loss_compete ||
277 qdly > chd_data->prev_backoff_qdly) {
278 /*
279 * Delay is higher than when we backed off previously,
280 * so it is possible that this flow is competing with
281 * loss based flows.
282 */
283 chd_data->shadow_w = max(CCV(ccv, snd_cwnd),
284 chd_data->shadow_w);
285 } else {
286 /*
287 * Reset shadow_w, as it is probable that this flow is
288 * not competing with loss based flows at the moment.
289 */
290 chd_data->shadow_w = 0;
291 }
292
293 chd_data->prev_backoff_qdly = qdly;
294 /*
295 * Send delay-based congestion signal to the congestion signal
296 * handler.
297 */
298 chd_cong_signal(ccv, CC_CHD_DELAY);
299
300 } else if (ack_type == CC_ACK)
301 chd_window_increase(ccv, new_measurement);
302}
303
304static void
305chd_cb_destroy(struct cc_var *ccv)
306{
307
308 if (ccv->cc_data != NULL)
309 free(ccv->cc_data, M_CHD);
310}
311
312static int
313chd_cb_init(struct cc_var *ccv)
314{
315 struct chd *chd_data;
316
317 chd_data = malloc(sizeof(struct chd), M_CHD, M_NOWAIT);
318 if (chd_data == NULL)
319 return (ENOMEM);
320
321 chd_data->shadow_w = 0;
322 ccv->cc_data = chd_data;
323
324 return (0);
325}
326
327static void
328chd_cong_signal(struct cc_var *ccv, uint32_t signal_type)
329{
330 struct ertt *e_t;
331 struct chd *chd_data;
332 int qdly;
333
334 e_t = khelp_get_osd(CCV(ccv, osd), ertt_id);
335 chd_data = ccv->cc_data;
336 qdly = imax(e_t->rtt, chd_data->maxrtt_in_rtt) - e_t->minrtt;
337
338 switch(signal_type) {
339 case CC_CHD_DELAY:
340 chd_window_decrease(ccv); /* Set new ssthresh. */
341 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
342 CCV(ccv, snd_recover) = CCV(ccv, snd_max);
343 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
344 break;
345
346 case CC_NDUPACK: /* Packet loss. */
347 /*
348 * Only react to loss as a congestion signal if qdly >
349 * V_chd_qthresh. If qdly is less than qthresh, presume that
350 * this is a non congestion related loss. If qdly is greater
351 * than qthresh, assume that we are competing with loss based
352 * tcp flows and restore window from any unnecessary backoffs,
353 * before the decrease.
354 */
355 if (!IN_RECOVERY(CCV(ccv, t_flags)) && qdly > V_chd_qthresh) {
356 if (chd_data->loss_compete) {
357 CCV(ccv, snd_cwnd) = max(CCV(ccv, snd_cwnd),
358 chd_data->shadow_w);
359 }
360 chd_window_decrease(ccv);
361 } else {
362 /*
363 * This loss isn't congestion related, or already
364 * recovering from congestion.
365 */
366 CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd);
367 CCV(ccv, snd_recover) = CCV(ccv, snd_max);
368 }
369
370 if (chd_data->shadow_w > 0) {
371 chd_data->shadow_w = max(chd_data->shadow_w /
372 CCV(ccv, t_maxseg) / 2, 2) * CCV(ccv, t_maxseg);
373 }
374 ENTER_FASTRECOVERY(CCV(ccv, t_flags));
375 break;
376
377 default:
378 newreno_cc_algo.cong_signal(ccv, signal_type);
379 }
380}
381
382static void
383chd_conn_init(struct cc_var *ccv)
384{
385 struct chd *chd_data;
386
387 chd_data = ccv->cc_data;
388 chd_data->prev_backoff_qdly = 0;
389 chd_data->maxrtt_in_rtt = 0;
390 chd_data->loss_compete = 0;
391 /*
392 * Initialise the shadow_cwnd to be equal to snd_cwnd in case we are
393 * competing with loss based flows from the start.
394 */
395 chd_data->shadow_w = CCV(ccv, snd_cwnd);
396}
397
398static int
399chd_mod_init(void)
400{
401
402 ertt_id = khelp_get_id("ertt");
403 if (ertt_id <= 0) {
404 printf("%s: h_ertt module not found\n", __func__);
405 return (ENOENT);
406 }
407
408 chd_cc_algo.after_idle = newreno_cc_algo.after_idle;
409 chd_cc_algo.post_recovery = newreno_cc_algo.post_recovery;
410
411 return (0);
412}
413
414static int
415chd_loss_fair_handler(SYSCTL_HANDLER_ARGS)
416{
417 int error;
418 uint32_t new;
419
420 new = V_chd_loss_fair;
421 error = sysctl_handle_int(oidp, &new, 0, req);
422 if (error == 0 && req->newptr != NULL) {
423 if (CAST_PTR_INT(req->newptr) > 1)
424 error = EINVAL;
425 else
426 V_chd_loss_fair = new;
427 }
428
429 return (error);
430}
431
432static int
433chd_pmax_handler(SYSCTL_HANDLER_ARGS)
434{
435 int error;
436 uint32_t new;
437
438 new = V_chd_pmax;
439 error = sysctl_handle_int(oidp, &new, 0, req);
440 if (error == 0 && req->newptr != NULL) {
441 if (CAST_PTR_INT(req->newptr) == 0 ||
442 CAST_PTR_INT(req->newptr) > 100)
443 error = EINVAL;
444 else
445 V_chd_pmax = new;
446 }
447
448 return (error);
449}
450
451static int
452chd_qthresh_handler(SYSCTL_HANDLER_ARGS)
453{
454 int error;
455 uint32_t new;
456
457 new = V_chd_qthresh;
458 error = sysctl_handle_int(oidp, &new, 0, req);
459 if (error == 0 && req->newptr != NULL) {
460 if (CAST_PTR_INT(req->newptr) <= V_chd_qmin)
461 error = EINVAL;
462 else
463 V_chd_qthresh = new;
464 }
465
466 return (error);
467}
468
469SYSCTL_DECL(_net_inet_tcp_cc_chd);
470SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, chd, CTLFLAG_RW, NULL,
471 "CAIA Hamilton delay-based congestion control related settings");
472
473SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, loss_fair,
474 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
475 &VNET_NAME(chd_loss_fair), 1, &chd_loss_fair_handler,
476 "IU", "Flag to enable shadow window functionality.");
477
478SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, pmax,
479 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
480 &VNET_NAME(chd_pmax), 5, &chd_pmax_handler,
481 "IU", "Per RTT maximum backoff probability as a percentage");
482
483SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, queue_threshold,
484 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
485 &VNET_NAME(chd_qthresh), 20, &chd_qthresh_handler,
486 "IU", "Queueing congestion threshold in ticks");
487
488SYSCTL_UINT(_net_inet_tcp_cc_chd, OID_AUTO, queue_min,
489 CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_qmin), 5,
490 "Minimum queueing delay threshold in ticks");
491
492SYSCTL_UINT(_net_inet_tcp_cc_chd, OID_AUTO, use_max,
493 CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_use_max), 1,
494 "Use the maximum RTT seen within the measurement period (RTT) "
495 "as the basic delay measurement for the algorithm.");
496
497DECLARE_CC_MODULE(chd, &chd_cc_algo);
498MODULE_DEPEND(chd, ertt, 1, 1, 1);
|