Blame view
net/ipv4/tcp_illinois.c
8.26 KB
c462238d6 [TCP]: TCP Illino... |
1 2 3 4 5 6 7 8 |
/* * TCP Illinois congestion control. * Home page: * http://www.ews.uiuc.edu/~shaoliu/tcpillinois/index.html * * The algorithm is described in: * "TCP-Illinois: A Loss and Delay-Based Congestion Control Algorithm * for High-Speed Networks" |
c6885fb45 net/tcp/illinois:... |
9 |
* http://tamerbasar.csl.illinois.edu/LiuBasarSrikantPerfEvalArtJun2008.pdf |
c462238d6 [TCP]: TCP Illino... |
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
* * Implemented from description in paper and ns-2 simulation. * Copyright (C) 2007 Stephen Hemminger <shemminger@linux-foundation.org> */ #include <linux/module.h> #include <linux/skbuff.h> #include <linux/inet_diag.h> #include <asm/div64.h> #include <net/tcp.h> #define ALPHA_SHIFT 7 #define ALPHA_SCALE (1u<<ALPHA_SHIFT) #define ALPHA_MIN ((3*ALPHA_SCALE)/10) /* ~0.3 */ #define ALPHA_MAX (10*ALPHA_SCALE) /* 10.0 */ #define ALPHA_BASE ALPHA_SCALE /* 1.0 */ |
65d1b4a7e [TCP]: TCP Illino... |
26 |
#define RTT_MAX (U32_MAX / ALPHA_MAX) /* 3.3 secs */ |
c462238d6 [TCP]: TCP Illino... |
27 28 29 |
#define BETA_SHIFT 6 #define BETA_SCALE (1u<<BETA_SHIFT) |
65d1b4a7e [TCP]: TCP Illino... |
30 31 32 |
#define BETA_MIN (BETA_SCALE/8) /* 0.125 */ #define BETA_MAX (BETA_SCALE/2) /* 0.5 */ #define BETA_BASE BETA_MAX |
c462238d6 [TCP]: TCP Illino... |
33 34 |
static int win_thresh __read_mostly = 15; |
65d1b4a7e [TCP]: TCP Illino... |
35 |
module_param(win_thresh, int, 0); |
c462238d6 [TCP]: TCP Illino... |
36 |
MODULE_PARM_DESC(win_thresh, "Window threshold for starting adaptive sizing"); |
65d1b4a7e [TCP]: TCP Illino... |
37 38 39 |
static int theta __read_mostly = 5; module_param(theta, int, 0); MODULE_PARM_DESC(theta, "# of fast RTT's before full growth"); |
c462238d6 [TCP]: TCP Illino... |
40 41 |
/* TCP Illinois Parameters */ |
65d1b4a7e [TCP]: TCP Illino... |
42 43 44 45 46 47 48 49 50 51 52 |
struct illinois { u64 sum_rtt; /* sum of rtt's measured within last rtt */ u16 cnt_rtt; /* # of rtts measured within last rtt */ u32 base_rtt; /* min of all rtt in usec */ u32 max_rtt; /* max of all rtt in usec */ u32 end_seq; /* right edge of current RTT */ u32 alpha; /* Additive increase */ u32 beta; /* Muliplicative decrease */ u16 acked; /* # packets acked by current ACK */ u8 rtt_above; /* average rtt has gone above threshold */ u8 rtt_low; /* # of rtts measurements below threshold */ |
c462238d6 [TCP]: TCP Illino... |
53 |
}; |
65d1b4a7e [TCP]: TCP Illino... |
54 55 56 57 58 59 60 61 62 63 64 |
static void rtt_reset(struct sock *sk) { struct tcp_sock *tp = tcp_sk(sk); struct illinois *ca = inet_csk_ca(sk); ca->end_seq = tp->snd_nxt; ca->cnt_rtt = 0; ca->sum_rtt = 0; /* TODO: age max_rtt? */ } |
c462238d6 [TCP]: TCP Illino... |
65 66 |
static void tcp_illinois_init(struct sock *sk) { |
65d1b4a7e [TCP]: TCP Illino... |
67 68 69 70 71 72 73 74 75 76 |
struct illinois *ca = inet_csk_ca(sk); ca->alpha = ALPHA_MAX; ca->beta = BETA_BASE; ca->base_rtt = 0x7fffffff; ca->max_rtt = 0; ca->acked = 0; ca->rtt_low = 0; ca->rtt_above = 0; |
c462238d6 [TCP]: TCP Illino... |
77 |
|
65d1b4a7e [TCP]: TCP Illino... |
78 |
rtt_reset(sk); |
c462238d6 [TCP]: TCP Illino... |
79 |
} |
65d1b4a7e [TCP]: TCP Illino... |
80 |
/* Measure RTT for each ack. */ |
756ee1729 tcp: replace cnt ... |
81 |
static void tcp_illinois_acked(struct sock *sk, const struct ack_sample *sample) |
c462238d6 [TCP]: TCP Illino... |
82 |
{ |
65d1b4a7e [TCP]: TCP Illino... |
83 |
struct illinois *ca = inet_csk_ca(sk); |
756ee1729 tcp: replace cnt ... |
84 |
s32 rtt_us = sample->rtt_us; |
164891aad [TCP]: Congestion... |
85 |
|
756ee1729 tcp: replace cnt ... |
86 |
ca->acked = sample->pkts_acked; |
164891aad [TCP]: Congestion... |
87 |
|
30cfd0baf [TCP]: congestion... |
88 |
/* dup ack, no rtt sample */ |
756ee1729 tcp: replace cnt ... |
89 |
if (rtt_us < 0) |
b9ce204f0 [TCP]: Congestion... |
90 |
return; |
65d1b4a7e [TCP]: TCP Illino... |
91 |
/* ignore bogus values, this prevents wraparound in alpha math */ |
756ee1729 tcp: replace cnt ... |
92 93 |
if (rtt_us > RTT_MAX) rtt_us = RTT_MAX; |
c462238d6 [TCP]: TCP Illino... |
94 |
|
65d1b4a7e [TCP]: TCP Illino... |
95 |
/* keep track of minimum RTT seen so far */ |
756ee1729 tcp: replace cnt ... |
96 97 |
if (ca->base_rtt > rtt_us) ca->base_rtt = rtt_us; |
65d1b4a7e [TCP]: TCP Illino... |
98 99 |
/* and max */ |
756ee1729 tcp: replace cnt ... |
100 101 |
if (ca->max_rtt < rtt_us) ca->max_rtt = rtt_us; |
c462238d6 [TCP]: TCP Illino... |
102 |
|
65d1b4a7e [TCP]: TCP Illino... |
103 |
++ca->cnt_rtt; |
756ee1729 tcp: replace cnt ... |
104 |
ca->sum_rtt += rtt_us; |
c462238d6 [TCP]: TCP Illino... |
105 |
} |
65d1b4a7e [TCP]: TCP Illino... |
106 107 |
/* Maximum queuing delay */ static inline u32 max_delay(const struct illinois *ca) |
c462238d6 [TCP]: TCP Illino... |
108 |
{ |
65d1b4a7e [TCP]: TCP Illino... |
109 110 |
return ca->max_rtt - ca->base_rtt; } |
c462238d6 [TCP]: TCP Illino... |
111 |
|
65d1b4a7e [TCP]: TCP Illino... |
112 113 114 115 |
/* Average queuing delay */ static inline u32 avg_delay(const struct illinois *ca) { u64 t = ca->sum_rtt; |
c462238d6 [TCP]: TCP Illino... |
116 |
|
65d1b4a7e [TCP]: TCP Illino... |
117 118 |
do_div(t, ca->cnt_rtt); return t - ca->base_rtt; |
c462238d6 [TCP]: TCP Illino... |
119 120 121 122 123 124 125 126 127 128 |
} /* * Compute value of alpha used for additive increase. * If small window then use 1.0, equivalent to Reno. * * For larger windows, adjust based on average delay. * A. If average delay is at minimum (we are uncongested), * then use large alpha (10.0) to increase faster. * B. If average delay is at maximum (getting congested) |
65d1b4a7e [TCP]: TCP Illino... |
129 |
* then use small alpha (0.3) |
c462238d6 [TCP]: TCP Illino... |
130 131 132 |
* * The result is a convex window growth curve. */ |
65d1b4a7e [TCP]: TCP Illino... |
133 |
static u32 alpha(struct illinois *ca, u32 da, u32 dm) |
c462238d6 [TCP]: TCP Illino... |
134 |
{ |
65d1b4a7e [TCP]: TCP Illino... |
135 |
u32 d1 = dm / 100; /* Low threshold */ |
c462238d6 [TCP]: TCP Illino... |
136 |
|
c462238d6 [TCP]: TCP Illino... |
137 |
if (da <= d1) { |
65d1b4a7e [TCP]: TCP Illino... |
138 139 |
/* If never got out of low delay zone, then use max */ if (!ca->rtt_above) |
c462238d6 [TCP]: TCP Illino... |
140 |
return ALPHA_MAX; |
65d1b4a7e [TCP]: TCP Illino... |
141 142 143 144 145 146 147 148 149 150 |
/* Wait for 5 good RTT's before allowing alpha to go alpha max. * This prevents one good RTT from causing sudden window increase. */ if (++ca->rtt_low < theta) return ca->alpha; ca->rtt_low = 0; ca->rtt_above = 0; return ALPHA_MAX; |
c462238d6 [TCP]: TCP Illino... |
151 |
} |
65d1b4a7e [TCP]: TCP Illino... |
152 |
ca->rtt_above = 1; |
c462238d6 [TCP]: TCP Illino... |
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 |
/* * Based on: * * (dm - d1) amin amax * k1 = ------------------- * amax - amin * * (dm - d1) amin * k2 = ---------------- - d1 * amax - amin * * k1 * alpha = ---------- * k2 + da */ dm -= d1; da -= d1; |
65d1b4a7e [TCP]: TCP Illino... |
172 173 |
return (dm * ALPHA_MAX) / (dm + (da * (ALPHA_MAX - ALPHA_MIN)) / ALPHA_MIN); |
c462238d6 [TCP]: TCP Illino... |
174 175 176 177 178 179 180 181 182 183 |
} /* * Beta used for multiplicative decrease. * For small window sizes returns same value as Reno (0.5) * * If delay is small (10% of max) then beta = 1/8 * If delay is up to 80% of max then beta = 1/2 * In between is a linear function */ |
65d1b4a7e [TCP]: TCP Illino... |
184 |
static u32 beta(u32 da, u32 dm) |
c462238d6 [TCP]: TCP Illino... |
185 |
{ |
c462238d6 [TCP]: TCP Illino... |
186 |
u32 d2, d3; |
c462238d6 [TCP]: TCP Illino... |
187 188 189 |
d2 = dm / 10; if (da <= d2) return BETA_MIN; |
65d1b4a7e [TCP]: TCP Illino... |
190 |
|
c462238d6 [TCP]: TCP Illino... |
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 |
d3 = (8 * dm) / 10; if (da >= d3 || d3 <= d2) return BETA_MAX; /* * Based on: * * bmin d3 - bmax d2 * k3 = ------------------- * d3 - d2 * * bmax - bmin * k4 = ------------- * d3 - d2 * * b = k3 + k4 da */ return (BETA_MIN * d3 - BETA_MAX * d2 + (BETA_MAX - BETA_MIN) * da) / (d3 - d2); } |
65d1b4a7e [TCP]: TCP Illino... |
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 |
/* Update alpha and beta values once per RTT */ static void update_params(struct sock *sk) { struct tcp_sock *tp = tcp_sk(sk); struct illinois *ca = inet_csk_ca(sk); if (tp->snd_cwnd < win_thresh) { ca->alpha = ALPHA_BASE; ca->beta = BETA_BASE; } else if (ca->cnt_rtt > 0) { u32 dm = max_delay(ca); u32 da = avg_delay(ca); ca->alpha = alpha(ca, da, dm); ca->beta = beta(da, dm); } rtt_reset(sk); } /* * In case of loss, reset to default values */ static void tcp_illinois_state(struct sock *sk, u8 new_state) { struct illinois *ca = inet_csk_ca(sk); if (new_state == TCP_CA_Loss) { ca->alpha = ALPHA_BASE; ca->beta = BETA_BASE; ca->rtt_low = 0; ca->rtt_above = 0; rtt_reset(sk); } } /* * Increase window in response to successful acknowledgment. */ |
249015515 tcp: remove in_fl... |
250 |
static void tcp_illinois_cong_avoid(struct sock *sk, u32 ack, u32 acked) |
65d1b4a7e [TCP]: TCP Illino... |
251 252 253 254 255 256 257 258 |
{ struct tcp_sock *tp = tcp_sk(sk); struct illinois *ca = inet_csk_ca(sk); if (after(ack, ca->end_seq)) update_params(sk); /* RFC2861 only increase cwnd if fully utilized */ |
249015515 tcp: remove in_fl... |
259 |
if (!tcp_is_cwnd_limited(sk)) |
65d1b4a7e [TCP]: TCP Illino... |
260 261 262 |
return; /* In slow start */ |
071d5080e tcp: add tcp_in_s... |
263 |
if (tcp_in_slow_start(tp)) |
9f9843a75 tcp: properly han... |
264 |
tcp_slow_start(tp, acked); |
65d1b4a7e [TCP]: TCP Illino... |
265 266 267 268 269 270 271 272 273 274 275 276 277 278 |
else { u32 delta; /* snd_cwnd_cnt is # of packets since last cwnd increment */ tp->snd_cwnd_cnt += ca->acked; ca->acked = 1; /* This is close approximation of: * tp->snd_cwnd += alpha/tp->snd_cwnd */ delta = (tp->snd_cwnd_cnt * ca->alpha) >> ALPHA_SHIFT; if (delta >= tp->snd_cwnd) { tp->snd_cwnd = min(tp->snd_cwnd + delta / tp->snd_cwnd, |
688d1945b tcp: whitespace f... |
279 |
(u32)tp->snd_cwnd_clamp); |
65d1b4a7e [TCP]: TCP Illino... |
280 281 282 283 |
tp->snd_cwnd_cnt = 0; } } } |
c462238d6 [TCP]: TCP Illino... |
284 285 286 |
static u32 tcp_illinois_ssthresh(struct sock *sk) { struct tcp_sock *tp = tcp_sk(sk); |
65d1b4a7e [TCP]: TCP Illino... |
287 |
struct illinois *ca = inet_csk_ca(sk); |
c462238d6 [TCP]: TCP Illino... |
288 289 |
/* Multiplicative decrease */ |
a357dde9d [TCP] illinois: I... |
290 |
return max(tp->snd_cwnd - ((tp->snd_cwnd * ca->beta) >> BETA_SHIFT), 2U); |
c462238d6 [TCP]: TCP Illino... |
291 |
} |
65d1b4a7e [TCP]: TCP Illino... |
292 |
/* Extract info for Tcp socket info provided via netlink. */ |
64f40ff5b tcp: prepare CC g... |
293 294 |
static size_t tcp_illinois_info(struct sock *sk, u32 ext, int *attr, union tcp_cc_info *info) |
c462238d6 [TCP]: TCP Illino... |
295 |
{ |
65d1b4a7e [TCP]: TCP Illino... |
296 |
const struct illinois *ca = inet_csk_ca(sk); |
c462238d6 [TCP]: TCP Illino... |
297 298 |
if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) { |
64f40ff5b tcp: prepare CC g... |
299 300 301 302 |
info->vegas.tcpv_enabled = 1; info->vegas.tcpv_rttcnt = ca->cnt_rtt; info->vegas.tcpv_minrtt = ca->base_rtt; info->vegas.tcpv_rtt = 0; |
65d1b4a7e [TCP]: TCP Illino... |
303 |
|
64f40ff5b tcp: prepare CC g... |
304 |
if (info->vegas.tcpv_rttcnt > 0) { |
8f363b77e net: fix divide b... |
305 |
u64 t = ca->sum_rtt; |
c462238d6 [TCP]: TCP Illino... |
306 |
|
64f40ff5b tcp: prepare CC g... |
307 308 |
do_div(t, info->vegas.tcpv_rttcnt); info->vegas.tcpv_rtt = t; |
8f363b77e net: fix divide b... |
309 |
} |
64f40ff5b tcp: prepare CC g... |
310 311 |
*attr = INET_DIAG_VEGASINFO; return sizeof(struct tcpvegas_info); |
c462238d6 [TCP]: TCP Illino... |
312 |
} |
521f1cf1d inet_diag: fix ac... |
313 |
return 0; |
c462238d6 [TCP]: TCP Illino... |
314 |
} |
a252bebe2 tcp: mark tcp_con... |
315 |
static struct tcp_congestion_ops tcp_illinois __read_mostly = { |
c462238d6 [TCP]: TCP Illino... |
316 317 |
.init = tcp_illinois_init, .ssthresh = tcp_illinois_ssthresh, |
f1722a1be tcp: consolidate ... |
318 |
.undo_cwnd = tcp_reno_undo_cwnd, |
c462238d6 [TCP]: TCP Illino... |
319 |
.cong_avoid = tcp_illinois_cong_avoid, |
65d1b4a7e [TCP]: TCP Illino... |
320 |
.set_state = tcp_illinois_state, |
65d1b4a7e [TCP]: TCP Illino... |
321 322 |
.get_info = tcp_illinois_info, .pkts_acked = tcp_illinois_acked, |
c462238d6 [TCP]: TCP Illino... |
323 324 325 326 327 328 329 |
.owner = THIS_MODULE, .name = "illinois", }; static int __init tcp_illinois_register(void) { |
65d1b4a7e [TCP]: TCP Illino... |
330 |
BUILD_BUG_ON(sizeof(struct illinois) > ICSK_CA_PRIV_SIZE); |
c462238d6 [TCP]: TCP Illino... |
331 332 333 334 335 336 337 338 339 340 341 342 343 344 |
return tcp_register_congestion_control(&tcp_illinois); } static void __exit tcp_illinois_unregister(void) { tcp_unregister_congestion_control(&tcp_illinois); } module_init(tcp_illinois_register); module_exit(tcp_illinois_unregister); MODULE_AUTHOR("Stephen Hemminger, Shao Liu"); MODULE_LICENSE("GPL"); MODULE_DESCRIPTION("TCP Illinois"); |
65d1b4a7e [TCP]: TCP Illino... |
345 |
MODULE_VERSION("1.0"); |