aboutsummaryrefslogtreecommitdiffstats
path: root/net/ipv4
diff options
context:
space:
mode:
authorStephen Hemminger <shemminger@linux-foundation.org>2007-04-20 20:07:51 -0400
committerDavid S. Miller <davem@sunset.davemloft.net>2007-04-26 01:29:23 -0400
commitc462238d6a6d8ee855bda10f9fff442971540ed2 (patch)
treecaa527f56bb23759bb7c2c4591eb49db21d76f1a /net/ipv4
parent9be9a6b983314dd57e2c5ba548dee8b53d338ac3 (diff)
[TCP]: TCP Illinois congestion control (rev3)
This is an implementation of TCP Illinois invented by Shao Liu at University of Illinois. It is a another variant of Reno which adapts the alpha and beta parameters based on RTT. The basic idea is to increase window less rapidly as delay approaches the maximum. See the papers and talks to get a more complete description. Signed-off-by: Stephen Hemminger <shemminger@linux-foundation.org> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/ipv4')
-rw-r--r--net/ipv4/Kconfig13
-rw-r--r--net/ipv4/Makefile1
-rw-r--r--net/ipv4/tcp_illinois.c284
3 files changed, 298 insertions, 0 deletions
diff --git a/net/ipv4/Kconfig b/net/ipv4/Kconfig
index dc61e6641624..e62aee0ec4c5 100644
--- a/net/ipv4/Kconfig
+++ b/net/ipv4/Kconfig
@@ -588,6 +588,19 @@ config TCP_CONG_YEAH
588 For further details look here: 588 For further details look here:
589 http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf 589 http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf
590 590
591config TCP_CONG_ILLINOIS
592 tristate "TCP Illinois"
593 depends on EXPERIMENTAL
594 default n
595 ---help---
596 TCP-Illinois is a sender-side modificatio of TCP Reno for
597 high speed long delay links. It uses round-trip-time to
598 adjust the alpha and beta parameters to achieve a higher average
599 throughput and maintain fairness.
600
601 For further details see:
602 http://www.ews.uiuc.edu/~shaoliu/tcpillinois/index.html
603
591choice 604choice
592 prompt "Default TCP congestion control" 605 prompt "Default TCP congestion control"
593 default DEFAULT_CUBIC 606 default DEFAULT_CUBIC
diff --git a/net/ipv4/Makefile b/net/ipv4/Makefile
index eeb94d5cac96..4ff6c151d7f3 100644
--- a/net/ipv4/Makefile
+++ b/net/ipv4/Makefile
@@ -50,6 +50,7 @@ obj-$(CONFIG_TCP_CONG_VENO) += tcp_veno.o
50obj-$(CONFIG_TCP_CONG_SCALABLE) += tcp_scalable.o 50obj-$(CONFIG_TCP_CONG_SCALABLE) += tcp_scalable.o
51obj-$(CONFIG_TCP_CONG_LP) += tcp_lp.o 51obj-$(CONFIG_TCP_CONG_LP) += tcp_lp.o
52obj-$(CONFIG_TCP_CONG_YEAH) += tcp_yeah.o 52obj-$(CONFIG_TCP_CONG_YEAH) += tcp_yeah.o
53obj-$(CONFIG_TCP_CONG_ILLINOIS) += tcp_illinois.o
53obj-$(CONFIG_NETLABEL) += cipso_ipv4.o 54obj-$(CONFIG_NETLABEL) += cipso_ipv4.o
54 55
55obj-$(CONFIG_XFRM) += xfrm4_policy.o xfrm4_state.o xfrm4_input.o \ 56obj-$(CONFIG_XFRM) += xfrm4_policy.o xfrm4_state.o xfrm4_input.o \
diff --git a/net/ipv4/tcp_illinois.c b/net/ipv4/tcp_illinois.c
new file mode 100644
index 000000000000..91a2a34604cd
--- /dev/null
+++ b/net/ipv4/tcp_illinois.c
@@ -0,0 +1,284 @@
1/*
2 * TCP Illinois congestion control.
3 * Home page:
4 * http://www.ews.uiuc.edu/~shaoliu/tcpillinois/index.html
5 *
6 * The algorithm is described in:
7 * "TCP-Illinois: A Loss and Delay-Based Congestion Control Algorithm
8 * for High-Speed Networks"
9 * http://www.ews.uiuc.edu/~shaoliu/papersandslides/liubassri06perf.pdf
10 *
11 * Implemented from description in paper and ns-2 simulation.
12 * Copyright (C) 2007 Stephen Hemminger <shemminger@linux-foundation.org>
13 */
14
15#include <linux/module.h>
16#include <linux/skbuff.h>
17#include <linux/inet_diag.h>
18#include <asm/div64.h>
19#include <net/tcp.h>
20
21#define ALPHA_SHIFT 7
22#define ALPHA_SCALE (1u<<ALPHA_SHIFT)
23#define ALPHA_MIN ((3*ALPHA_SCALE)/10) /* ~0.3 */
24#define ALPHA_MAX (10*ALPHA_SCALE) /* 10.0 */
25#define ALPHA_BASE ALPHA_SCALE /* 1.0 */
26
27#define BETA_SHIFT 6
28#define BETA_SCALE (1u<<BETA_SHIFT)
29#define BETA_MIN (BETA_SCALE/8) /* 0.8 */
30#define BETA_MAX (BETA_SCALE/2)
31#define BETA_BASE BETA_MAX /* 0.5 */
32
33#define THETA 5
34
35static int win_thresh __read_mostly = 15;
36module_param(win_thresh, int, 0644);
37MODULE_PARM_DESC(win_thresh, "Window threshold for starting adaptive sizing");
38
39#define MAX_RTT 0x7fffffff
40
41/* TCP Illinois Parameters */
42struct tcp_illinois {
43 u32 last_alpha;
44 u32 min_rtt;
45 u32 max_rtt;
46 u32 rtt_low;
47 u32 rtt_cnt;
48 u64 sum_rtt;
49};
50
51static void tcp_illinois_init(struct sock *sk)
52{
53 struct tcp_illinois *ca = inet_csk_ca(sk);
54
55 ca->last_alpha = ALPHA_BASE;
56 ca->min_rtt = 0x7fffffff;
57}
58
59/*
60 * Keep track of min, max and average RTT
61 */
62static void tcp_illinois_rtt_calc(struct sock *sk, u32 rtt)
63{
64 struct tcp_illinois *ca = inet_csk_ca(sk);
65
66 if (rtt < ca->min_rtt)
67 ca->min_rtt = rtt;
68 if (rtt > ca->max_rtt)
69 ca->max_rtt = rtt;
70
71 if (++ca->rtt_cnt == 1)
72 ca->sum_rtt = rtt;
73 else
74 ca->sum_rtt += rtt;
75}
76
77/* max queuing delay */
78static inline u32 max_delay(const struct tcp_illinois *ca)
79{
80 return ca->max_rtt - ca->min_rtt;
81}
82
83/* average queueing delay */
84static u32 avg_delay(struct tcp_illinois *ca)
85{
86 u64 avg_rtt = ca->sum_rtt;
87
88 do_div(avg_rtt, ca->rtt_cnt);
89
90 ca->sum_rtt = 0;
91 ca->rtt_cnt = 0;
92
93 return avg_rtt - ca->min_rtt;
94}
95
96/*
97 * Compute value of alpha used for additive increase.
98 * If small window then use 1.0, equivalent to Reno.
99 *
100 * For larger windows, adjust based on average delay.
101 * A. If average delay is at minimum (we are uncongested),
102 * then use large alpha (10.0) to increase faster.
103 * B. If average delay is at maximum (getting congested)
104 * then use small alpha (1.0)
105 *
106 * The result is a convex window growth curve.
107 */
108static u32 alpha(const struct sock *sk)
109{
110 struct tcp_sock *tp = tcp_sk(sk);
111 struct tcp_illinois *ca = inet_csk_ca(sk);
112 u32 dm = max_delay(ca);
113 u32 da = avg_delay(ca);
114 u32 d1, a;
115
116 if (tp->snd_cwnd < win_thresh)
117 return ALPHA_BASE; /* same as Reno (1.0) */
118
119 d1 = dm / 100;
120 if (da <= d1) {
121 /* Don't let noise force agressive response */
122 if (ca->rtt_low < THETA) {
123 ++ca->rtt_low;
124 return ca->last_alpha;
125 } else
126 return ALPHA_MAX;
127 }
128
129 ca->rtt_low = 0;
130
131 /*
132 * Based on:
133 *
134 * (dm - d1) amin amax
135 * k1 = -------------------
136 * amax - amin
137 *
138 * (dm - d1) amin
139 * k2 = ---------------- - d1
140 * amax - amin
141 *
142 * k1
143 * alpha = ----------
144 * k2 + da
145 */
146
147 dm -= d1;
148 da -= d1;
149
150 a = (dm * ALPHA_MAX) / (dm - (da * (ALPHA_MAX - ALPHA_MIN)) / ALPHA_MIN);
151 ca->last_alpha = a;
152 return a;
153}
154
155/*
156 * Increase window in response to successful acknowledgment.
157 */
158static void tcp_illinois_cong_avoid(struct sock *sk, u32 ack, u32 rtt,
159 u32 in_flight, int flag)
160{
161 struct tcp_sock *tp = tcp_sk(sk);
162
163 /* RFC2861 only increase cwnd if fully utilized */
164 if (!tcp_is_cwnd_limited(sk, in_flight))
165 return;
166
167 /* In slow start */
168 if (tp->snd_cwnd <= tp->snd_ssthresh)
169 tcp_slow_start(tp);
170
171 else {
172 /* additive increase cwnd += alpha / cwnd */
173 if ((tp->snd_cwnd_cnt * alpha(sk)) >> ALPHA_SHIFT >= tp->snd_cwnd) {
174 if (tp->snd_cwnd < tp->snd_cwnd_clamp)
175 tp->snd_cwnd++;
176 tp->snd_cwnd_cnt = 0;
177 } else
178 tp->snd_cwnd_cnt++;
179 }
180}
181
182/*
183 * Beta used for multiplicative decrease.
184 * For small window sizes returns same value as Reno (0.5)
185 *
186 * If delay is small (10% of max) then beta = 1/8
187 * If delay is up to 80% of max then beta = 1/2
188 * In between is a linear function
189 */
190static inline u32 beta(struct sock *sk)
191{
192 struct tcp_sock *tp = tcp_sk(sk);
193 struct tcp_illinois *ca = inet_csk_ca(sk);
194 u32 dm = max_delay(ca);
195 u32 da = avg_delay(ca);
196 u32 d2, d3;
197
198 if (tp->snd_cwnd < win_thresh)
199 return BETA_BASE;
200
201 d2 = dm / 10;
202 if (da <= d2)
203 return BETA_MIN;
204 d3 = (8 * dm) / 10;
205 if (da >= d3 || d3 <= d2)
206 return BETA_MAX;
207
208 /*
209 * Based on:
210 *
211 * bmin d3 - bmax d2
212 * k3 = -------------------
213 * d3 - d2
214 *
215 * bmax - bmin
216 * k4 = -------------
217 * d3 - d2
218 *
219 * b = k3 + k4 da
220 */
221 return (BETA_MIN * d3 - BETA_MAX * d2 + (BETA_MAX - BETA_MIN) * da)
222 / (d3 - d2);
223}
224
225static u32 tcp_illinois_ssthresh(struct sock *sk)
226{
227 struct tcp_sock *tp = tcp_sk(sk);
228
229 /* Multiplicative decrease */
230 return max((tp->snd_cwnd * beta(sk)) >> BETA_SHIFT, 2U);
231}
232
233/* Extract info for TCP socket info provided via netlink.
234 * We aren't really doing Vegas, but we can provide RTT info
235 */
236static void tcp_illinois_get_info(struct sock *sk, u32 ext,
237 struct sk_buff *skb)
238{
239 const struct tcp_illinois *ca = inet_csk_ca(sk);
240
241 if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) {
242 struct tcpvegas_info info = {
243 .tcpv_enabled = 1,
244 .tcpv_rttcnt = ca->rtt_cnt,
245 .tcpv_minrtt = ca->min_rtt,
246 };
247 u64 avg_rtt = ca->sum_rtt;
248 do_div(avg_rtt, ca->rtt_cnt);
249 info.tcpv_rtt = avg_rtt;
250
251 nla_put(skb, INET_DIAG_VEGASINFO, sizeof(info), &info);
252 }
253}
254
255static struct tcp_congestion_ops tcp_illinois = {
256 .init = tcp_illinois_init,
257 .ssthresh = tcp_illinois_ssthresh,
258 .min_cwnd = tcp_reno_min_cwnd,
259 .cong_avoid = tcp_illinois_cong_avoid,
260 .rtt_sample = tcp_illinois_rtt_calc,
261 .get_info = tcp_illinois_get_info,
262
263 .owner = THIS_MODULE,
264 .name = "illinois",
265};
266
267static int __init tcp_illinois_register(void)
268{
269 BUILD_BUG_ON(sizeof(struct tcp_illinois) > ICSK_CA_PRIV_SIZE);
270 return tcp_register_congestion_control(&tcp_illinois);
271}
272
273static void __exit tcp_illinois_unregister(void)
274{
275 tcp_unregister_congestion_control(&tcp_illinois);
276}
277
278module_init(tcp_illinois_register);
279module_exit(tcp_illinois_unregister);
280
281MODULE_AUTHOR("Stephen Hemminger, Shao Liu");
282MODULE_LICENSE("GPL");
283MODULE_DESCRIPTION("TCP Illinois");
284MODULE_VERSION("0.3");