2 * Copyright (c) 2007-2008
3 * Swinburne University of Technology, Melbourne, Australia
4 * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
5 * Copyright (c) 2014 Midori Kato <katoon@sfc.wide.ad.jp>
6 * Copyright (c) 2014 The FreeBSD Foundation
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * An implementation of the DCTCP algorithm for FreeBSD, based on
33 * "Data Center TCP (DCTCP)" by M. Alizadeh, A. Greenberg, D. A. Maltz,
34 * J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan.,
35 * in ACM Conference on SIGCOMM 2010, New York, USA,
36 * Originally released as the contribution of Microsoft Research project.
39 #include <sys/cdefs.h>
40 __FBSDID("$FreeBSD$");
42 #include <sys/param.h>
43 #include <sys/kernel.h>
44 #include <sys/malloc.h>
45 #include <sys/module.h>
46 #include <sys/socket.h>
47 #include <sys/socketvar.h>
48 #include <sys/sysctl.h>
49 #include <sys/systm.h>
53 #include <netinet/tcp.h>
54 #include <netinet/tcp_seq.h>
55 #include <netinet/tcp_var.h>
56 #include <netinet/cc/cc.h>
57 #include <netinet/cc/cc_module.h>
59 #define DCTCP_SHIFT 10
60 #define MAX_ALPHA_VALUE (1<<DCTCP_SHIFT)
61 VNET_DEFINE_STATIC(uint32_t, dctcp_alpha) = MAX_ALPHA_VALUE;
62 #define V_dctcp_alpha VNET(dctcp_alpha)
63 VNET_DEFINE_STATIC(uint32_t, dctcp_shift_g) = 4;
64 #define V_dctcp_shift_g VNET(dctcp_shift_g)
65 VNET_DEFINE_STATIC(uint32_t, dctcp_slowstart) = 0;
66 #define V_dctcp_slowstart VNET(dctcp_slowstart)
69 uint32_t bytes_ecn; /* # of marked bytes during a RTT */
70 uint32_t bytes_total; /* # of acked bytes during a RTT */
71 int alpha; /* the fraction of marked bytes */
72 int ce_prev; /* CE state of the last segment */
73 tcp_seq save_sndnxt; /* end sequence number of the current window */
74 int ece_curr; /* ECE flag in this segment */
75 int ece_prev; /* ECE flag in the last segment */
76 uint32_t num_cong_events; /* # of congestion events */
79 static MALLOC_DEFINE(M_dctcp, "dctcp data",
80 "Per connection data required for the dctcp algorithm");
82 static void dctcp_ack_received(struct cc_var *ccv, uint16_t type);
83 static void dctcp_after_idle(struct cc_var *ccv);
84 static void dctcp_cb_destroy(struct cc_var *ccv);
85 static int dctcp_cb_init(struct cc_var *ccv);
86 static void dctcp_cong_signal(struct cc_var *ccv, uint32_t type);
87 static void dctcp_conn_init(struct cc_var *ccv);
88 static void dctcp_post_recovery(struct cc_var *ccv);
89 static void dctcp_ecnpkt_handler(struct cc_var *ccv);
90 static void dctcp_update_alpha(struct cc_var *ccv);
92 struct cc_algo dctcp_cc_algo = {
94 .ack_received = dctcp_ack_received,
95 .cb_destroy = dctcp_cb_destroy,
96 .cb_init = dctcp_cb_init,
97 .cong_signal = dctcp_cong_signal,
98 .conn_init = dctcp_conn_init,
99 .post_recovery = dctcp_post_recovery,
100 .ecnpkt_handler = dctcp_ecnpkt_handler,
101 .after_idle = dctcp_after_idle,
105 dctcp_ack_received(struct cc_var *ccv, uint16_t type)
107 struct dctcp *dctcp_data;
110 dctcp_data = ccv->cc_data;
112 if (CCV(ccv, t_flags) & TF_ECN_PERMIT) {
114 * DCTCP doesn't treat receipt of ECN marked packet as a
115 * congestion event. Thus, DCTCP always executes the ACK
116 * processing out of congestion recovery.
118 if (IN_CONGRECOVERY(CCV(ccv, t_flags))) {
119 EXIT_CONGRECOVERY(CCV(ccv, t_flags));
120 newreno_cc_algo.ack_received(ccv, type);
121 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
123 newreno_cc_algo.ack_received(ccv, type);
125 if (type == CC_DUPACK)
126 bytes_acked = min(ccv->bytes_this_ack, CCV(ccv, t_maxseg));
129 bytes_acked = ccv->bytes_this_ack;
131 /* Update total bytes. */
132 dctcp_data->bytes_total += bytes_acked;
134 /* Update total marked bytes. */
135 if (dctcp_data->ece_curr) {
136 //XXRMS: For fluid-model DCTCP, update
137 //cwnd here during for RTT fairness
138 if (!dctcp_data->ece_prev
139 && bytes_acked > CCV(ccv, t_maxseg)) {
140 dctcp_data->bytes_ecn +=
141 (bytes_acked - CCV(ccv, t_maxseg));
143 dctcp_data->bytes_ecn += bytes_acked;
144 dctcp_data->ece_prev = 1;
146 if (dctcp_data->ece_prev
147 && bytes_acked > CCV(ccv, t_maxseg))
148 dctcp_data->bytes_ecn += CCV(ccv, t_maxseg);
149 dctcp_data->ece_prev = 0;
151 dctcp_data->ece_curr = 0;
154 * Update the fraction of marked bytes at the end of
155 * current window size.
157 if (!IN_FASTRECOVERY(CCV(ccv, t_flags)) &&
158 SEQ_GT(ccv->curack, dctcp_data->save_sndnxt))
159 dctcp_update_alpha(ccv);
161 newreno_cc_algo.ack_received(ccv, type);
165 dctcp_after_idle(struct cc_var *ccv)
167 struct dctcp *dctcp_data;
169 if (CCV(ccv, t_flags) & TF_ECN_PERMIT) {
170 dctcp_data = ccv->cc_data;
172 /* Initialize internal parameters after idle time */
173 dctcp_data->bytes_ecn = 0;
174 dctcp_data->bytes_total = 0;
175 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
176 dctcp_data->alpha = V_dctcp_alpha;
177 dctcp_data->ece_curr = 0;
178 dctcp_data->ece_prev = 0;
179 dctcp_data->num_cong_events = 0;
182 newreno_cc_algo.after_idle(ccv);
186 dctcp_cb_destroy(struct cc_var *ccv)
188 free(ccv->cc_data, M_dctcp);
192 dctcp_cb_init(struct cc_var *ccv)
194 struct dctcp *dctcp_data;
196 dctcp_data = malloc(sizeof(struct dctcp), M_dctcp, M_NOWAIT|M_ZERO);
198 if (dctcp_data == NULL)
201 /* Initialize some key variables with sensible defaults. */
202 dctcp_data->bytes_ecn = 0;
203 dctcp_data->bytes_total = 0;
205 * When alpha is set to 0 in the beginning, DCTCP sender transfers as
206 * much data as possible until the value converges which may expand the
207 * queueing delay at the switch. When alpha is set to 1, queueing delay
209 * Throughput-sensitive applications should have alpha = 0
210 * Latency-sensitive applications should have alpha = 1
212 * Note: DCTCP draft suggests initial alpha to be 1 but we've decided to
213 * keep it 0 as default.
215 dctcp_data->alpha = V_dctcp_alpha;
216 dctcp_data->save_sndnxt = 0;
217 dctcp_data->ce_prev = 0;
218 dctcp_data->ece_curr = 0;
219 dctcp_data->ece_prev = 0;
220 dctcp_data->num_cong_events = 0;
222 ccv->cc_data = dctcp_data;
227 * Perform any necessary tasks before we enter congestion recovery.
230 dctcp_cong_signal(struct cc_var *ccv, uint32_t type)
232 struct dctcp *dctcp_data;
235 if (CCV(ccv, t_flags) & TF_ECN_PERMIT) {
236 dctcp_data = ccv->cc_data;
237 cwin = CCV(ccv, snd_cwnd);
238 mss = CCV(ccv, t_maxseg);
242 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) {
243 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
244 CCV(ccv, snd_ssthresh) =
245 max(cwin / 2, 2 * mss);
246 dctcp_data->num_cong_events++;
248 /* cwnd has already updated as congestion
249 * recovery. Reverse cwnd value using
250 * snd_cwnd_prev and recalculate snd_ssthresh
252 cwin = CCV(ccv, snd_cwnd_prev);
253 CCV(ccv, snd_ssthresh) =
254 max(cwin / 2, 2 * mss);
256 ENTER_RECOVERY(CCV(ccv, t_flags));
261 * Save current snd_cwnd when the host encounters both
262 * congestion recovery and fast recovery.
264 CCV(ccv, snd_cwnd_prev) = cwin;
265 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
266 if (V_dctcp_slowstart &&
267 dctcp_data->num_cong_events++ == 0) {
268 CCV(ccv, snd_ssthresh) =
269 max(cwin / 2, 2 * mss);
270 dctcp_data->alpha = MAX_ALPHA_VALUE;
271 dctcp_data->bytes_ecn = 0;
272 dctcp_data->bytes_total = 0;
273 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
275 CCV(ccv, snd_ssthresh) =
276 max((cwin - (((uint64_t)cwin *
277 dctcp_data->alpha) >> (DCTCP_SHIFT+1))),
279 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
280 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
282 dctcp_data->ece_curr = 1;
285 CCV(ccv, t_flags) |= TF_ECN_SND_CWR;
286 dctcp_update_alpha(ccv);
287 dctcp_data->save_sndnxt += CCV(ccv, t_maxseg);
288 dctcp_data->num_cong_events++;
292 newreno_cc_algo.cong_signal(ccv, type);
296 dctcp_conn_init(struct cc_var *ccv)
298 struct dctcp *dctcp_data;
300 dctcp_data = ccv->cc_data;
302 if (CCV(ccv, t_flags) & TF_ECN_PERMIT)
303 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
307 * Perform any necessary tasks before we exit congestion recovery.
310 dctcp_post_recovery(struct cc_var *ccv)
312 newreno_cc_algo.post_recovery(ccv);
314 if (CCV(ccv, t_flags) & TF_ECN_PERMIT)
315 dctcp_update_alpha(ccv);
319 * Execute an additional ECN processing using ECN field in IP header and the CWR
322 * delay_ack == 0 - Delayed ACK disabled
323 * delay_ack == 1 - Delayed ACK enabled
327 dctcp_ecnpkt_handler(struct cc_var *ccv)
329 struct dctcp *dctcp_data;
333 dctcp_data = ccv->cc_data;
338 * DCTCP responds with an ACK immediately when the CE state
339 * in between this segment and the last segment has changed.
341 if (ccflag & CCF_IPHDR_CE) {
342 if (!dctcp_data->ce_prev && (ccflag & CCF_DELACK))
344 dctcp_data->ce_prev = 1;
345 CCV(ccv, t_flags) |= TF_ECN_SND_ECE;
347 if (dctcp_data->ce_prev && (ccflag & CCF_DELACK))
349 dctcp_data->ce_prev = 0;
350 CCV(ccv, t_flags) &= ~TF_ECN_SND_ECE;
353 /* DCTCP sets delayed ack when this segment sets the CWR flag. */
354 if ((ccflag & CCF_DELACK) && (ccflag & CCF_TCPHDR_CWR))
358 ccv->flags |= CCF_ACKNOW;
362 * Update the fraction of marked bytes represented as 'alpha'.
363 * Also initialize several internal parameters at the end of this function.
366 dctcp_update_alpha(struct cc_var *ccv)
368 struct dctcp *dctcp_data;
371 dctcp_data = ccv->cc_data;
372 alpha_prev = dctcp_data->alpha;
373 dctcp_data->bytes_total = max(dctcp_data->bytes_total, 1);
376 * Update alpha: alpha = (1 - g) * alpha + g * M.
379 * recommaded to be set to 1/16
380 * small g = slow convergence between competitive DCTCP flows
381 * large g = impacts low utilization of bandwidth at switches
382 * M is fraction of marked segments in last RTT
384 * Alpha must be round to 0 - MAX_ALPHA_VALUE.
386 dctcp_data->alpha = ulmin(alpha_prev - (alpha_prev >> V_dctcp_shift_g) +
387 ((uint64_t)dctcp_data->bytes_ecn << (DCTCP_SHIFT - V_dctcp_shift_g)) /
388 dctcp_data->bytes_total, MAX_ALPHA_VALUE);
390 /* Initialize internal parameters for next alpha calculation */
391 dctcp_data->bytes_ecn = 0;
392 dctcp_data->bytes_total = 0;
393 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
397 dctcp_alpha_handler(SYSCTL_HANDLER_ARGS)
403 error = sysctl_handle_int(oidp, &new, 0, req);
404 if (error == 0 && req->newptr != NULL) {
405 if (new > MAX_ALPHA_VALUE)
415 dctcp_shift_g_handler(SYSCTL_HANDLER_ARGS)
420 new = V_dctcp_shift_g;
421 error = sysctl_handle_int(oidp, &new, 0, req);
422 if (error == 0 && req->newptr != NULL) {
423 if (new > DCTCP_SHIFT)
426 V_dctcp_shift_g = new;
433 dctcp_slowstart_handler(SYSCTL_HANDLER_ARGS)
438 new = V_dctcp_slowstart;
439 error = sysctl_handle_int(oidp, &new, 0, req);
440 if (error == 0 && req->newptr != NULL) {
444 V_dctcp_slowstart = new;
450 SYSCTL_DECL(_net_inet_tcp_cc_dctcp);
451 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, dctcp, CTLFLAG_RW, NULL,
452 "dctcp congestion control related settings");
454 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, alpha,
455 CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_alpha), 0,
456 &dctcp_alpha_handler,
457 "IU", "dctcp alpha parameter at start of session");
459 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, shift_g,
460 CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_shift_g), 4,
461 &dctcp_shift_g_handler,
462 "IU", "dctcp shift parameter");
464 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, slowstart,
465 CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_slowstart), 0,
466 &dctcp_slowstart_handler,
467 "IU", "half CWND reduction after the first slow start");
469 DECLARE_CC_MODULE(dctcp, &dctcp_cc_algo);