Blame view
net/ipv4/tcp_illinois.c
8.15 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" |
631dd1a88 Update broken web... |
9 |
* http://www.ifp.illinois.edu/~srikant/Papers/liubassri06perf.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 27 |
#define U32_MAX ((u32)~0U) #define RTT_MAX (U32_MAX / ALPHA_MAX) /* 3.3 secs */ |
c462238d6 [TCP]: TCP Illino... |
28 29 30 |
#define BETA_SHIFT 6 #define BETA_SCALE (1u<<BETA_SHIFT) |
65d1b4a7e [TCP]: TCP Illino... |
31 32 33 |
#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... |
34 35 |
static int win_thresh __read_mostly = 15; |
65d1b4a7e [TCP]: TCP Illino... |
36 |
module_param(win_thresh, int, 0); |
c462238d6 [TCP]: TCP Illino... |
37 |
MODULE_PARM_DESC(win_thresh, "Window threshold for starting adaptive sizing"); |
65d1b4a7e [TCP]: TCP Illino... |
38 39 40 |
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... |
41 42 |
/* TCP Illinois Parameters */ |
65d1b4a7e [TCP]: TCP Illino... |
43 44 45 46 47 48 49 50 51 52 53 |
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... |
54 |
}; |
65d1b4a7e [TCP]: TCP Illino... |
55 56 57 58 59 60 61 62 63 64 65 |
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... |
66 67 |
static void tcp_illinois_init(struct sock *sk) { |
65d1b4a7e [TCP]: TCP Illino... |
68 69 70 71 72 73 74 75 76 77 |
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... |
78 |
|
65d1b4a7e [TCP]: TCP Illino... |
79 |
rtt_reset(sk); |
c462238d6 [TCP]: TCP Illino... |
80 |
} |
65d1b4a7e [TCP]: TCP Illino... |
81 |
/* Measure RTT for each ack. */ |
30cfd0baf [TCP]: congestion... |
82 |
static void tcp_illinois_acked(struct sock *sk, u32 pkts_acked, s32 rtt) |
c462238d6 [TCP]: TCP Illino... |
83 |
{ |
65d1b4a7e [TCP]: TCP Illino... |
84 |
struct illinois *ca = inet_csk_ca(sk); |
164891aad [TCP]: Congestion... |
85 86 |
ca->acked = pkts_acked; |
30cfd0baf [TCP]: congestion... |
87 88 |
/* dup ack, no rtt sample */ if (rtt < 0) |
b9ce204f0 [TCP]: Congestion... |
89 |
return; |
65d1b4a7e [TCP]: TCP Illino... |
90 91 92 |
/* ignore bogus values, this prevents wraparound in alpha math */ if (rtt > RTT_MAX) rtt = RTT_MAX; |
c462238d6 [TCP]: TCP Illino... |
93 |
|
65d1b4a7e [TCP]: TCP Illino... |
94 95 96 97 98 99 |
/* keep track of minimum RTT seen so far */ if (ca->base_rtt > rtt) ca->base_rtt = rtt; /* and max */ if (ca->max_rtt < rtt) |
c462238d6 [TCP]: TCP Illino... |
100 |
ca->max_rtt = rtt; |
65d1b4a7e [TCP]: TCP Illino... |
101 102 |
++ca->cnt_rtt; ca->sum_rtt += rtt; |
c462238d6 [TCP]: TCP Illino... |
103 |
} |
65d1b4a7e [TCP]: TCP Illino... |
104 105 |
/* Maximum queuing delay */ static inline u32 max_delay(const struct illinois *ca) |
c462238d6 [TCP]: TCP Illino... |
106 |
{ |
65d1b4a7e [TCP]: TCP Illino... |
107 108 |
return ca->max_rtt - ca->base_rtt; } |
c462238d6 [TCP]: TCP Illino... |
109 |
|
65d1b4a7e [TCP]: TCP Illino... |
110 111 112 113 |
/* Average queuing delay */ static inline u32 avg_delay(const struct illinois *ca) { u64 t = ca->sum_rtt; |
c462238d6 [TCP]: TCP Illino... |
114 |
|
65d1b4a7e [TCP]: TCP Illino... |
115 116 |
do_div(t, ca->cnt_rtt); return t - ca->base_rtt; |
c462238d6 [TCP]: TCP Illino... |
117 118 119 120 121 122 123 124 125 126 |
} /* * 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... |
127 |
* then use small alpha (0.3) |
c462238d6 [TCP]: TCP Illino... |
128 129 130 |
* * The result is a convex window growth curve. */ |
65d1b4a7e [TCP]: TCP Illino... |
131 |
static u32 alpha(struct illinois *ca, u32 da, u32 dm) |
c462238d6 [TCP]: TCP Illino... |
132 |
{ |
65d1b4a7e [TCP]: TCP Illino... |
133 |
u32 d1 = dm / 100; /* Low threshold */ |
c462238d6 [TCP]: TCP Illino... |
134 |
|
c462238d6 [TCP]: TCP Illino... |
135 |
if (da <= d1) { |
65d1b4a7e [TCP]: TCP Illino... |
136 137 |
/* If never got out of low delay zone, then use max */ if (!ca->rtt_above) |
c462238d6 [TCP]: TCP Illino... |
138 |
return ALPHA_MAX; |
65d1b4a7e [TCP]: TCP Illino... |
139 140 141 142 143 144 145 146 147 148 |
/* 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... |
149 |
} |
65d1b4a7e [TCP]: TCP Illino... |
150 |
ca->rtt_above = 1; |
c462238d6 [TCP]: TCP Illino... |
151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 |
/* * 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... |
170 171 |
return (dm * ALPHA_MAX) / (dm + (da * (ALPHA_MAX - ALPHA_MIN)) / ALPHA_MIN); |
c462238d6 [TCP]: TCP Illino... |
172 173 174 175 176 177 178 179 180 181 |
} /* * 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... |
182 |
static u32 beta(u32 da, u32 dm) |
c462238d6 [TCP]: TCP Illino... |
183 |
{ |
c462238d6 [TCP]: TCP Illino... |
184 |
u32 d2, d3; |
c462238d6 [TCP]: TCP Illino... |
185 186 187 |
d2 = dm / 10; if (da <= d2) return BETA_MIN; |
65d1b4a7e [TCP]: TCP Illino... |
188 |
|
c462238d6 [TCP]: TCP Illino... |
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 |
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... |
209 210 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 |
/* 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. */ |
c3a05c605 [TCP]: Cong.ctrl ... |
248 |
static void tcp_illinois_cong_avoid(struct sock *sk, u32 ack, u32 in_flight) |
65d1b4a7e [TCP]: TCP Illino... |
249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 |
{ 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 */ if (!tcp_is_cwnd_limited(sk, in_flight)) return; /* In slow start */ if (tp->snd_cwnd <= tp->snd_ssthresh) tcp_slow_start(tp); 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, (u32) tp->snd_cwnd_clamp); tp->snd_cwnd_cnt = 0; } } } |
c462238d6 [TCP]: TCP Illino... |
282 283 284 |
static u32 tcp_illinois_ssthresh(struct sock *sk) { struct tcp_sock *tp = tcp_sk(sk); |
65d1b4a7e [TCP]: TCP Illino... |
285 |
struct illinois *ca = inet_csk_ca(sk); |
c462238d6 [TCP]: TCP Illino... |
286 287 |
/* Multiplicative decrease */ |
a357dde9d [TCP] illinois: I... |
288 |
return max(tp->snd_cwnd - ((tp->snd_cwnd * ca->beta) >> BETA_SHIFT), 2U); |
c462238d6 [TCP]: TCP Illino... |
289 |
} |
65d1b4a7e [TCP]: TCP Illino... |
290 291 292 293 |
/* Extract info for Tcp socket info provided via netlink. */ static void tcp_illinois_info(struct sock *sk, u32 ext, struct sk_buff *skb) |
c462238d6 [TCP]: TCP Illino... |
294 |
{ |
65d1b4a7e [TCP]: TCP Illino... |
295 |
const struct illinois *ca = inet_csk_ca(sk); |
c462238d6 [TCP]: TCP Illino... |
296 297 298 299 |
if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) { struct tcpvegas_info info = { .tcpv_enabled = 1, |
65d1b4a7e [TCP]: TCP Illino... |
300 301 |
.tcpv_rttcnt = ca->cnt_rtt, .tcpv_minrtt = ca->base_rtt, |
c462238d6 [TCP]: TCP Illino... |
302 |
}; |
65d1b4a7e [TCP]: TCP Illino... |
303 304 305 306 |
u64 t = ca->sum_rtt; do_div(t, ca->cnt_rtt); info.tcpv_rtt = t; |
c462238d6 [TCP]: TCP Illino... |
307 308 309 310 |
nla_put(skb, INET_DIAG_VEGASINFO, sizeof(info), &info); } } |
a252bebe2 tcp: mark tcp_con... |
311 |
static struct tcp_congestion_ops tcp_illinois __read_mostly = { |
164891aad [TCP]: Congestion... |
312 |
.flags = TCP_CONG_RTT_STAMP, |
c462238d6 [TCP]: TCP Illino... |
313 314 315 316 |
.init = tcp_illinois_init, .ssthresh = tcp_illinois_ssthresh, .min_cwnd = tcp_reno_min_cwnd, .cong_avoid = tcp_illinois_cong_avoid, |
65d1b4a7e [TCP]: TCP Illino... |
317 |
.set_state = tcp_illinois_state, |
65d1b4a7e [TCP]: TCP Illino... |
318 319 |
.get_info = tcp_illinois_info, .pkts_acked = tcp_illinois_acked, |
c462238d6 [TCP]: TCP Illino... |
320 321 322 323 324 325 326 |
.owner = THIS_MODULE, .name = "illinois", }; static int __init tcp_illinois_register(void) { |
65d1b4a7e [TCP]: TCP Illino... |
327 |
BUILD_BUG_ON(sizeof(struct illinois) > ICSK_CA_PRIV_SIZE); |
c462238d6 [TCP]: TCP Illino... |
328 329 330 331 332 333 334 335 336 337 338 339 340 341 |
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... |
342 |
MODULE_VERSION("1.0"); |