1/*-
2 * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994, 1995
3 * The Regents of the University of California.
4 * Copyright (c) 2007-2008,2010
5 * Swinburne University of Technology, Melbourne, Australia.
6 * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
7 * Copyright (c) 2010 The FreeBSD Foundation
8 * All rights reserved.
9 *
10 * This software was developed at the Centre for Advanced Internet
11 * Architectures, Swinburne University of Technology, by Lawrence Stewart, James
12 * Healy and David Hayes, made possible in part by a grant from the Cisco
13 * University Research Program Fund at Community Foundation Silicon Valley.
14 *
15 * Portions of this software were developed at the Centre for Advanced
16 * Internet Architectures, Swinburne University of Technology, Melbourne,
17 * Australia by David Hayes under sponsorship from the FreeBSD Foundation.
18 *
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions
21 * are met:
22 * 1. Redistributions of source code must retain the above copyright
23 * notice, this list of conditions and the following disclaimer.
24 * 2. Redistributions in binary form must reproduce the above copyright
25 * notice, this list of conditions and the following disclaimer in the
26 * documentation and/or other materials provided with the distribution.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 * SUCH DAMAGE.
39 */
40
41/*
42 * This software was first released in 2007 by James Healy and Lawrence Stewart
43 * whilst working on the NewTCP research project at Swinburne University of
44 * Technology's Centre for Advanced Internet Architectures, Melbourne,
45 * Australia, which was made possible in part by a grant from the Cisco
46 * University Research Program Fund at Community Foundation Silicon Valley.
47 * More details are available at:
48 * http://caia.swin.edu.au/urp/newtcp/
49 */
50
51#include <sys/cdefs.h>
| 1/*-
2 * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994, 1995
3 * The Regents of the University of California.
4 * Copyright (c) 2007-2008,2010
5 * Swinburne University of Technology, Melbourne, Australia.
6 * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
7 * Copyright (c) 2010 The FreeBSD Foundation
8 * All rights reserved.
9 *
10 * This software was developed at the Centre for Advanced Internet
11 * Architectures, Swinburne University of Technology, by Lawrence Stewart, James
12 * Healy and David Hayes, made possible in part by a grant from the Cisco
13 * University Research Program Fund at Community Foundation Silicon Valley.
14 *
15 * Portions of this software were developed at the Centre for Advanced
16 * Internet Architectures, Swinburne University of Technology, Melbourne,
17 * Australia by David Hayes under sponsorship from the FreeBSD Foundation.
18 *
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions
21 * are met:
22 * 1. Redistributions of source code must retain the above copyright
23 * notice, this list of conditions and the following disclaimer.
24 * 2. Redistributions in binary form must reproduce the above copyright
25 * notice, this list of conditions and the following disclaimer in the
26 * documentation and/or other materials provided with the distribution.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 * SUCH DAMAGE.
39 */
40
41/*
42 * This software was first released in 2007 by James Healy and Lawrence Stewart
43 * whilst working on the NewTCP research project at Swinburne University of
44 * Technology's Centre for Advanced Internet Architectures, Melbourne,
45 * Australia, which was made possible in part by a grant from the Cisco
46 * University Research Program Fund at Community Foundation Silicon Valley.
47 * More details are available at:
48 * http://caia.swin.edu.au/urp/newtcp/
49 */
50
51#include <sys/cdefs.h>
|
69#include <netinet/cc/cc_module.h>
70
71static void newreno_ack_received(struct cc_var *ccv, uint16_t type);
72static void newreno_after_idle(struct cc_var *ccv);
73static void newreno_cong_signal(struct cc_var *ccv, uint32_t type);
74static void newreno_post_recovery(struct cc_var *ccv);
75
76struct cc_algo newreno_cc_algo = {
77 .name = "newreno",
78 .ack_received = newreno_ack_received,
79 .after_idle = newreno_after_idle,
80 .cong_signal = newreno_cong_signal,
81 .post_recovery = newreno_post_recovery,
82};
83
84static void
85newreno_ack_received(struct cc_var *ccv, uint16_t type)
86{
87 if (type == CC_ACK && !IN_RECOVERY(CCV(ccv, t_flags)) &&
88 (ccv->flags & CCF_CWND_LIMITED)) {
89 u_int cw = CCV(ccv, snd_cwnd);
90 u_int incr = CCV(ccv, t_maxseg);
91
92 /*
93 * Regular in-order ACK, open the congestion window.
94 * Method depends on which congestion control state we're
95 * in (slow start or cong avoid) and if ABC (RFC 3465) is
96 * enabled.
97 *
98 * slow start: cwnd <= ssthresh
99 * cong avoid: cwnd > ssthresh
100 *
101 * slow start and ABC (RFC 3465):
102 * Grow cwnd exponentially by the amount of data
103 * ACKed capping the max increment per ACK to
104 * (abc_l_var * maxseg) bytes.
105 *
106 * slow start without ABC (RFC 5681):
107 * Grow cwnd exponentially by maxseg per ACK.
108 *
109 * cong avoid and ABC (RFC 3465):
110 * Grow cwnd linearly by maxseg per RTT for each
111 * cwnd worth of ACKed data.
112 *
113 * cong avoid without ABC (RFC 5681):
114 * Grow cwnd linearly by approximately maxseg per RTT using
115 * maxseg^2 / cwnd per ACK as the increment.
116 * If cwnd > maxseg^2, fix the cwnd increment at 1 byte to
117 * avoid capping cwnd.
118 */
119 if (cw > CCV(ccv, snd_ssthresh)) {
120 if (V_tcp_do_rfc3465) {
121 if (ccv->flags & CCF_ABC_SENTAWND)
122 ccv->flags &= ~CCF_ABC_SENTAWND;
123 else
124 incr = 0;
125 } else
126 incr = max((incr * incr / cw), 1);
127 } else if (V_tcp_do_rfc3465) {
128 /*
129 * In slow-start with ABC enabled and no RTO in sight?
130 * (Must not use abc_l_var > 1 if slow starting after
131 * an RTO. On RTO, snd_nxt = snd_una, so the
132 * snd_nxt == snd_max check is sufficient to
133 * handle this).
134 *
135 * XXXLAS: Find a way to signal SS after RTO that
136 * doesn't rely on tcpcb vars.
137 */
138 if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max))
139 incr = min(ccv->bytes_this_ack,
140 V_tcp_abc_l_var * CCV(ccv, t_maxseg));
141 else
142 incr = min(ccv->bytes_this_ack, CCV(ccv, t_maxseg));
143 }
144 /* ABC is on by default, so incr equals 0 frequently. */
145 if (incr > 0)
146 CCV(ccv, snd_cwnd) = min(cw + incr,
147 TCP_MAXWIN << CCV(ccv, snd_scale));
148 }
149}
150
151static void
152newreno_after_idle(struct cc_var *ccv)
153{
154 int rw;
155
156 /*
157 * If we've been idle for more than one retransmit timeout the old
158 * congestion window is no longer current and we have to reduce it to
159 * the restart window before we can transmit again.
160 *
161 * The restart window is the initial window or the last CWND, whichever
162 * is smaller.
163 *
164 * This is done to prevent us from flooding the path with a full CWND at
165 * wirespeed, overloading router and switch buffers along the way.
166 *
167 * See RFC5681 Section 4.1. "Restarting Idle Connections".
168 */
169 if (V_tcp_do_rfc3390)
170 rw = min(4 * CCV(ccv, t_maxseg),
171 max(2 * CCV(ccv, t_maxseg), 4380));
172 else
173 rw = CCV(ccv, t_maxseg) * 2;
174
175 CCV(ccv, snd_cwnd) = min(rw, CCV(ccv, snd_cwnd));
176}
177
178/*
179 * Perform any necessary tasks before we enter congestion recovery.
180 */
181static void
182newreno_cong_signal(struct cc_var *ccv, uint32_t type)
183{
184 u_int win;
185
186 /* Catch algos which mistakenly leak private signal types. */
187 KASSERT((type & CC_SIGPRIVMASK) == 0,
188 ("%s: congestion signal type 0x%08x is private\n", __func__, type));
189
190 win = max(CCV(ccv, snd_cwnd) / 2 / CCV(ccv, t_maxseg), 2) *
191 CCV(ccv, t_maxseg);
192
193 switch (type) {
194 case CC_NDUPACK:
195 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) {
196 if (!IN_CONGRECOVERY(CCV(ccv, t_flags)))
197 CCV(ccv, snd_ssthresh) = win;
198 ENTER_RECOVERY(CCV(ccv, t_flags));
199 }
200 break;
201 case CC_ECN:
202 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
203 CCV(ccv, snd_ssthresh) = win;
204 CCV(ccv, snd_cwnd) = win;
205 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
206 }
207 break;
208 }
209}
210
211/*
212 * Perform any necessary tasks before we exit congestion recovery.
213 */
214static void
215newreno_post_recovery(struct cc_var *ccv)
216{
217 int pipe;
218 pipe = 0;
219
220 if (IN_FASTRECOVERY(CCV(ccv, t_flags))) {
221 /*
222 * Fast recovery will conclude after returning from this
223 * function. Window inflation should have left us with
224 * approximately snd_ssthresh outstanding data. But in case we
225 * would be inclined to send a burst, better to do it via the
226 * slow start mechanism.
227 *
228 * XXXLAS: Find a way to do this without needing curack
229 */
230 if (V_tcp_do_rfc6675_pipe)
231 pipe = tcp_compute_pipe(ccv->ccvc.tcp);
232 else
233 pipe = CCV(ccv, snd_max) - ccv->curack;
234
235 if (pipe < CCV(ccv, snd_ssthresh))
236 CCV(ccv, snd_cwnd) = pipe + CCV(ccv, t_maxseg);
237 else
238 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
239 }
240}
241
242
243DECLARE_CC_MODULE(newreno, &newreno_cc_algo);
| 69#include <netinet/cc/cc_module.h>
70
71static void newreno_ack_received(struct cc_var *ccv, uint16_t type);
72static void newreno_after_idle(struct cc_var *ccv);
73static void newreno_cong_signal(struct cc_var *ccv, uint32_t type);
74static void newreno_post_recovery(struct cc_var *ccv);
75
76struct cc_algo newreno_cc_algo = {
77 .name = "newreno",
78 .ack_received = newreno_ack_received,
79 .after_idle = newreno_after_idle,
80 .cong_signal = newreno_cong_signal,
81 .post_recovery = newreno_post_recovery,
82};
83
84static void
85newreno_ack_received(struct cc_var *ccv, uint16_t type)
86{
87 if (type == CC_ACK && !IN_RECOVERY(CCV(ccv, t_flags)) &&
88 (ccv->flags & CCF_CWND_LIMITED)) {
89 u_int cw = CCV(ccv, snd_cwnd);
90 u_int incr = CCV(ccv, t_maxseg);
91
92 /*
93 * Regular in-order ACK, open the congestion window.
94 * Method depends on which congestion control state we're
95 * in (slow start or cong avoid) and if ABC (RFC 3465) is
96 * enabled.
97 *
98 * slow start: cwnd <= ssthresh
99 * cong avoid: cwnd > ssthresh
100 *
101 * slow start and ABC (RFC 3465):
102 * Grow cwnd exponentially by the amount of data
103 * ACKed capping the max increment per ACK to
104 * (abc_l_var * maxseg) bytes.
105 *
106 * slow start without ABC (RFC 5681):
107 * Grow cwnd exponentially by maxseg per ACK.
108 *
109 * cong avoid and ABC (RFC 3465):
110 * Grow cwnd linearly by maxseg per RTT for each
111 * cwnd worth of ACKed data.
112 *
113 * cong avoid without ABC (RFC 5681):
114 * Grow cwnd linearly by approximately maxseg per RTT using
115 * maxseg^2 / cwnd per ACK as the increment.
116 * If cwnd > maxseg^2, fix the cwnd increment at 1 byte to
117 * avoid capping cwnd.
118 */
119 if (cw > CCV(ccv, snd_ssthresh)) {
120 if (V_tcp_do_rfc3465) {
121 if (ccv->flags & CCF_ABC_SENTAWND)
122 ccv->flags &= ~CCF_ABC_SENTAWND;
123 else
124 incr = 0;
125 } else
126 incr = max((incr * incr / cw), 1);
127 } else if (V_tcp_do_rfc3465) {
128 /*
129 * In slow-start with ABC enabled and no RTO in sight?
130 * (Must not use abc_l_var > 1 if slow starting after
131 * an RTO. On RTO, snd_nxt = snd_una, so the
132 * snd_nxt == snd_max check is sufficient to
133 * handle this).
134 *
135 * XXXLAS: Find a way to signal SS after RTO that
136 * doesn't rely on tcpcb vars.
137 */
138 if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max))
139 incr = min(ccv->bytes_this_ack,
140 V_tcp_abc_l_var * CCV(ccv, t_maxseg));
141 else
142 incr = min(ccv->bytes_this_ack, CCV(ccv, t_maxseg));
143 }
144 /* ABC is on by default, so incr equals 0 frequently. */
145 if (incr > 0)
146 CCV(ccv, snd_cwnd) = min(cw + incr,
147 TCP_MAXWIN << CCV(ccv, snd_scale));
148 }
149}
150
151static void
152newreno_after_idle(struct cc_var *ccv)
153{
154 int rw;
155
156 /*
157 * If we've been idle for more than one retransmit timeout the old
158 * congestion window is no longer current and we have to reduce it to
159 * the restart window before we can transmit again.
160 *
161 * The restart window is the initial window or the last CWND, whichever
162 * is smaller.
163 *
164 * This is done to prevent us from flooding the path with a full CWND at
165 * wirespeed, overloading router and switch buffers along the way.
166 *
167 * See RFC5681 Section 4.1. "Restarting Idle Connections".
168 */
169 if (V_tcp_do_rfc3390)
170 rw = min(4 * CCV(ccv, t_maxseg),
171 max(2 * CCV(ccv, t_maxseg), 4380));
172 else
173 rw = CCV(ccv, t_maxseg) * 2;
174
175 CCV(ccv, snd_cwnd) = min(rw, CCV(ccv, snd_cwnd));
176}
177
178/*
179 * Perform any necessary tasks before we enter congestion recovery.
180 */
181static void
182newreno_cong_signal(struct cc_var *ccv, uint32_t type)
183{
184 u_int win;
185
186 /* Catch algos which mistakenly leak private signal types. */
187 KASSERT((type & CC_SIGPRIVMASK) == 0,
188 ("%s: congestion signal type 0x%08x is private\n", __func__, type));
189
190 win = max(CCV(ccv, snd_cwnd) / 2 / CCV(ccv, t_maxseg), 2) *
191 CCV(ccv, t_maxseg);
192
193 switch (type) {
194 case CC_NDUPACK:
195 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) {
196 if (!IN_CONGRECOVERY(CCV(ccv, t_flags)))
197 CCV(ccv, snd_ssthresh) = win;
198 ENTER_RECOVERY(CCV(ccv, t_flags));
199 }
200 break;
201 case CC_ECN:
202 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
203 CCV(ccv, snd_ssthresh) = win;
204 CCV(ccv, snd_cwnd) = win;
205 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
206 }
207 break;
208 }
209}
210
211/*
212 * Perform any necessary tasks before we exit congestion recovery.
213 */
214static void
215newreno_post_recovery(struct cc_var *ccv)
216{
217 int pipe;
218 pipe = 0;
219
220 if (IN_FASTRECOVERY(CCV(ccv, t_flags))) {
221 /*
222 * Fast recovery will conclude after returning from this
223 * function. Window inflation should have left us with
224 * approximately snd_ssthresh outstanding data. But in case we
225 * would be inclined to send a burst, better to do it via the
226 * slow start mechanism.
227 *
228 * XXXLAS: Find a way to do this without needing curack
229 */
230 if (V_tcp_do_rfc6675_pipe)
231 pipe = tcp_compute_pipe(ccv->ccvc.tcp);
232 else
233 pipe = CCV(ccv, snd_max) - ccv->curack;
234
235 if (pipe < CCV(ccv, snd_ssthresh))
236 CCV(ccv, snd_cwnd) = pipe + CCV(ccv, t_maxseg);
237 else
238 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
239 }
240}
241
242
243DECLARE_CC_MODULE(newreno, &newreno_cc_algo);
|