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
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.
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.
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions
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.
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
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/
51 #include <sys/cdefs.h>
52 __FBSDID("$FreeBSD$");
54 #include <sys/param.h>
55 #include <sys/kernel.h>
56 #include <sys/malloc.h>
57 #include <sys/module.h>
58 #include <sys/socket.h>
59 #include <sys/socketvar.h>
60 #include <sys/sysctl.h>
61 #include <sys/systm.h>
65 #include <netinet/tcp.h>
66 #include <netinet/tcp_seq.h>
67 #include <netinet/tcp_var.h>
68 #include <netinet/cc/cc.h>
69 #include <netinet/cc/cc_module.h>
71 static void newreno_ack_received(struct cc_var *ccv, uint16_t type);
72 static void newreno_after_idle(struct cc_var *ccv);
73 static void newreno_cong_signal(struct cc_var *ccv, uint32_t type);
74 static void newreno_post_recovery(struct cc_var *ccv);
76 struct cc_algo newreno_cc_algo = {
78 .ack_received = newreno_ack_received,
79 .after_idle = newreno_after_idle,
80 .cong_signal = newreno_cong_signal,
81 .post_recovery = newreno_post_recovery,
85 newreno_ack_received(struct cc_var *ccv, uint16_t type)
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);
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
98 * slow start: cwnd <= ssthresh
99 * cong avoid: cwnd > ssthresh
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.
106 * slow start without ABC (RFC 5681):
107 * Grow cwnd exponentially by maxseg per ACK.
109 * cong avoid and ABC (RFC 3465):
110 * Grow cwnd linearly by maxseg per RTT for each
111 * cwnd worth of ACKed data.
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.
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;
126 incr = max((incr * incr / cw), 1);
127 } else if (V_tcp_do_rfc3465) {
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
135 * XXXLAS: Find a way to signal SS after RTO that
136 * doesn't rely on tcpcb vars.
138 if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max))
139 incr = min(ccv->bytes_this_ack,
140 ccv->nsegs * V_tcp_abc_l_var *
143 incr = min(ccv->bytes_this_ack, CCV(ccv, t_maxseg));
145 /* ABC is on by default, so incr equals 0 frequently. */
147 CCV(ccv, snd_cwnd) = min(cw + incr,
148 TCP_MAXWIN << CCV(ccv, snd_scale));
153 newreno_after_idle(struct cc_var *ccv)
158 * If we've been idle for more than one retransmit timeout the old
159 * congestion window is no longer current and we have to reduce it to
160 * the restart window before we can transmit again.
162 * The restart window is the initial window or the last CWND, whichever
165 * This is done to prevent us from flooding the path with a full CWND at
166 * wirespeed, overloading router and switch buffers along the way.
168 * See RFC5681 Section 4.1. "Restarting Idle Connections".
170 if (V_tcp_do_rfc3390)
171 rw = min(4 * CCV(ccv, t_maxseg),
172 max(2 * CCV(ccv, t_maxseg), 4380));
174 rw = CCV(ccv, t_maxseg) * 2;
176 CCV(ccv, snd_cwnd) = min(rw, CCV(ccv, snd_cwnd));
180 * Perform any necessary tasks before we enter congestion recovery.
183 newreno_cong_signal(struct cc_var *ccv, uint32_t type)
185 uint32_t cwin, ssthresh_on_loss;
188 cwin = CCV(ccv, snd_cwnd);
189 mss = CCV(ccv, t_maxseg);
191 max((CCV(ccv, snd_max) - CCV(ccv, snd_una)) / 2 / mss, 2)
194 /* Catch algos which mistakenly leak private signal types. */
195 KASSERT((type & CC_SIGPRIVMASK) == 0,
196 ("%s: congestion signal type 0x%08x is private\n", __func__, type));
198 cwin = max(cwin / 2 / mss, 2) * mss;
202 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) {
203 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
204 CCV(ccv, snd_ssthresh) = ssthresh_on_loss;
205 CCV(ccv, snd_cwnd) = cwin;
207 ENTER_RECOVERY(CCV(ccv, t_flags));
211 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
212 CCV(ccv, snd_ssthresh) = ssthresh_on_loss;
213 CCV(ccv, snd_cwnd) = cwin;
214 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
218 CCV(ccv, snd_ssthresh) = ssthresh_on_loss;
219 CCV(ccv, snd_cwnd) = mss;
225 * Perform any necessary tasks before we exit congestion recovery.
228 newreno_post_recovery(struct cc_var *ccv)
233 if (IN_FASTRECOVERY(CCV(ccv, t_flags))) {
235 * Fast recovery will conclude after returning from this
236 * function. Window inflation should have left us with
237 * approximately snd_ssthresh outstanding data. But in case we
238 * would be inclined to send a burst, better to do it via the
239 * slow start mechanism.
241 * XXXLAS: Find a way to do this without needing curack
243 if (V_tcp_do_rfc6675_pipe)
244 pipe = tcp_compute_pipe(ccv->ccvc.tcp);
246 pipe = CCV(ccv, snd_max) - ccv->curack;
248 if (pipe < CCV(ccv, snd_ssthresh))
249 CCV(ccv, snd_cwnd) = pipe + CCV(ccv, t_maxseg);
251 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
256 DECLARE_CC_MODULE(newreno, &newreno_cc_algo);