Commit | Line | Data |
---|---|---|
83803034 SH |
1 | /* |
2 | * Binary Increase Congestion control for TCP | |
3 | * | |
4 | * This is from the implementation of BICTCP in | |
5 | * Lison-Xu, Kahaled Harfoush, and Injong Rhee. | |
6 | * "Binary Increase Congestion Control for Fast, Long Distance | |
7 | * Networks" in InfoComm 2004 | |
8 | * Available from: | |
9 | * http://www.csc.ncsu.edu/faculty/rhee/export/bitcp.pdf | |
10 | * | |
11 | * Unless BIC is enabled and congestion window is large | |
12 | * this behaves the same as the original Reno. | |
13 | */ | |
14 | ||
15 | #include <linux/config.h> | |
16 | #include <linux/mm.h> | |
17 | #include <linux/module.h> | |
18 | #include <net/tcp.h> | |
19 | ||
20 | ||
21 | #define BICTCP_BETA_SCALE 1024 /* Scale factor beta calculation | |
22 | * max_cwnd = snd_cwnd * beta | |
23 | */ | |
24 | #define BICTCP_B 4 /* | |
25 | * In binary search, | |
26 | * go to point (max+min)/N | |
27 | */ | |
28 | ||
29 | static int fast_convergence = 1; | |
450b5b18 | 30 | static int max_increment = 16; |
83803034 SH |
31 | static int low_window = 14; |
32 | static int beta = 819; /* = 819/1024 (BICTCP_BETA_SCALE) */ | |
83803034 SH |
33 | static int initial_ssthresh = 100; |
34 | static int smooth_part = 20; | |
35 | ||
36 | module_param(fast_convergence, int, 0644); | |
37 | MODULE_PARM_DESC(fast_convergence, "turn on/off fast convergence"); | |
38 | module_param(max_increment, int, 0644); | |
39 | MODULE_PARM_DESC(max_increment, "Limit on increment allowed during binary search"); | |
40 | module_param(low_window, int, 0644); | |
41 | MODULE_PARM_DESC(low_window, "lower bound on congestion window (for TCP friendliness)"); | |
42 | module_param(beta, int, 0644); | |
43 | MODULE_PARM_DESC(beta, "beta for multiplicative increase"); | |
83803034 SH |
44 | module_param(initial_ssthresh, int, 0644); |
45 | MODULE_PARM_DESC(initial_ssthresh, "initial value of slow start threshold"); | |
46 | module_param(smooth_part, int, 0644); | |
47 | MODULE_PARM_DESC(smooth_part, "log(B/(B*Smin))/log(B/(B-1))+B, # of RTT from Wmax-B to Wmax"); | |
48 | ||
49 | ||
50 | /* BIC TCP Parameters */ | |
51 | struct bictcp { | |
52 | u32 cnt; /* increase cwnd by 1 after ACKs */ | |
53 | u32 last_max_cwnd; /* last maximum snd_cwnd */ | |
54 | u32 loss_cwnd; /* congestion window at last loss */ | |
55 | u32 last_cwnd; /* the last snd_cwnd */ | |
56 | u32 last_time; /* time when updated last_cwnd */ | |
83803034 SH |
57 | u32 epoch_start; /* beginning of an epoch */ |
58 | #define ACK_RATIO_SHIFT 4 | |
59 | u32 delayed_ack; /* estimate the ratio of Packets/ACKs << 4 */ | |
60 | }; | |
61 | ||
62 | static inline void bictcp_reset(struct bictcp *ca) | |
63 | { | |
64 | ca->cnt = 0; | |
65 | ca->last_max_cwnd = 0; | |
66 | ca->loss_cwnd = 0; | |
67 | ca->last_cwnd = 0; | |
68 | ca->last_time = 0; | |
83803034 SH |
69 | ca->epoch_start = 0; |
70 | ca->delayed_ack = 2 << ACK_RATIO_SHIFT; | |
71 | } | |
72 | ||
6687e988 | 73 | static void bictcp_init(struct sock *sk) |
83803034 | 74 | { |
6687e988 | 75 | bictcp_reset(inet_csk_ca(sk)); |
83803034 | 76 | if (initial_ssthresh) |
6687e988 | 77 | tcp_sk(sk)->snd_ssthresh = initial_ssthresh; |
83803034 SH |
78 | } |
79 | ||
80 | /* | |
81 | * Compute congestion window to use. | |
82 | */ | |
83 | static inline void bictcp_update(struct bictcp *ca, u32 cwnd) | |
84 | { | |
85 | if (ca->last_cwnd == cwnd && | |
86 | (s32)(tcp_time_stamp - ca->last_time) <= HZ / 32) | |
87 | return; | |
88 | ||
89 | ca->last_cwnd = cwnd; | |
90 | ca->last_time = tcp_time_stamp; | |
91 | ||
92 | if (ca->epoch_start == 0) /* record the beginning of an epoch */ | |
93 | ca->epoch_start = tcp_time_stamp; | |
94 | ||
95 | /* start off normal */ | |
96 | if (cwnd <= low_window) { | |
97 | ca->cnt = cwnd; | |
98 | return; | |
99 | } | |
100 | ||
101 | /* binary increase */ | |
102 | if (cwnd < ca->last_max_cwnd) { | |
103 | __u32 dist = (ca->last_max_cwnd - cwnd) | |
104 | / BICTCP_B; | |
105 | ||
106 | if (dist > max_increment) | |
107 | /* linear increase */ | |
108 | ca->cnt = cwnd / max_increment; | |
109 | else if (dist <= 1U) | |
110 | /* binary search increase */ | |
111 | ca->cnt = (cwnd * smooth_part) / BICTCP_B; | |
112 | else | |
113 | /* binary search increase */ | |
114 | ca->cnt = cwnd / dist; | |
115 | } else { | |
116 | /* slow start AMD linear increase */ | |
117 | if (cwnd < ca->last_max_cwnd + BICTCP_B) | |
118 | /* slow start */ | |
119 | ca->cnt = (cwnd * smooth_part) / BICTCP_B; | |
120 | else if (cwnd < ca->last_max_cwnd + max_increment*(BICTCP_B-1)) | |
121 | /* slow start */ | |
122 | ca->cnt = (cwnd * (BICTCP_B-1)) | |
42a39450 | 123 | / (cwnd - ca->last_max_cwnd); |
83803034 SH |
124 | else |
125 | /* linear increase */ | |
126 | ca->cnt = cwnd / max_increment; | |
127 | } | |
128 | ||
129 | /* if in slow start or link utilization is very low */ | |
018da8f4 | 130 | if (ca->loss_cwnd == 0) { |
83803034 SH |
131 | if (ca->cnt > 20) /* increase cwnd 5% per RTT */ |
132 | ca->cnt = 20; | |
133 | } | |
134 | ||
135 | ca->cnt = (ca->cnt << ACK_RATIO_SHIFT) / ca->delayed_ack; | |
136 | if (ca->cnt == 0) /* cannot be zero */ | |
137 | ca->cnt = 1; | |
138 | } | |
139 | ||
6687e988 | 140 | static void bictcp_cong_avoid(struct sock *sk, u32 ack, |
83803034 SH |
141 | u32 seq_rtt, u32 in_flight, int data_acked) |
142 | { | |
6687e988 ACM |
143 | struct tcp_sock *tp = tcp_sk(sk); |
144 | struct bictcp *ca = inet_csk_ca(sk); | |
83803034 | 145 | |
f4805ede | 146 | if (!tcp_is_cwnd_limited(sk, in_flight)) |
83803034 SH |
147 | return; |
148 | ||
7faffa1c SH |
149 | if (tp->snd_cwnd <= tp->snd_ssthresh) |
150 | tcp_slow_start(tp); | |
151 | else { | |
83803034 SH |
152 | bictcp_update(ca, tp->snd_cwnd); |
153 | ||
7faffa1c | 154 | /* In dangerous area, increase slowly. |
83803034 SH |
155 | * In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd |
156 | */ | |
157 | if (tp->snd_cwnd_cnt >= ca->cnt) { | |
158 | if (tp->snd_cwnd < tp->snd_cwnd_clamp) | |
159 | tp->snd_cwnd++; | |
160 | tp->snd_cwnd_cnt = 0; | |
161 | } else | |
162 | tp->snd_cwnd_cnt++; | |
163 | } | |
164 | ||
165 | } | |
166 | ||
167 | /* | |
168 | * behave like Reno until low_window is reached, | |
169 | * then increase congestion window slowly | |
170 | */ | |
6687e988 | 171 | static u32 bictcp_recalc_ssthresh(struct sock *sk) |
83803034 | 172 | { |
6687e988 ACM |
173 | const struct tcp_sock *tp = tcp_sk(sk); |
174 | struct bictcp *ca = inet_csk_ca(sk); | |
83803034 SH |
175 | |
176 | ca->epoch_start = 0; /* end of epoch */ | |
177 | ||
83803034 SH |
178 | /* Wmax and fast convergence */ |
179 | if (tp->snd_cwnd < ca->last_max_cwnd && fast_convergence) | |
180 | ca->last_max_cwnd = (tp->snd_cwnd * (BICTCP_BETA_SCALE + beta)) | |
181 | / (2 * BICTCP_BETA_SCALE); | |
182 | else | |
183 | ca->last_max_cwnd = tp->snd_cwnd; | |
184 | ||
185 | ca->loss_cwnd = tp->snd_cwnd; | |
186 | ||
187 | ||
188 | if (tp->snd_cwnd <= low_window) | |
189 | return max(tp->snd_cwnd >> 1U, 2U); | |
190 | else | |
191 | return max((tp->snd_cwnd * beta) / BICTCP_BETA_SCALE, 2U); | |
192 | } | |
193 | ||
6687e988 | 194 | static u32 bictcp_undo_cwnd(struct sock *sk) |
83803034 | 195 | { |
6687e988 ACM |
196 | const struct tcp_sock *tp = tcp_sk(sk); |
197 | const struct bictcp *ca = inet_csk_ca(sk); | |
83803034 SH |
198 | return max(tp->snd_cwnd, ca->last_max_cwnd); |
199 | } | |
200 | ||
6687e988 | 201 | static u32 bictcp_min_cwnd(struct sock *sk) |
83803034 | 202 | { |
6687e988 | 203 | const struct tcp_sock *tp = tcp_sk(sk); |
83803034 SH |
204 | return tp->snd_ssthresh; |
205 | } | |
206 | ||
6687e988 | 207 | static void bictcp_state(struct sock *sk, u8 new_state) |
83803034 SH |
208 | { |
209 | if (new_state == TCP_CA_Loss) | |
6687e988 | 210 | bictcp_reset(inet_csk_ca(sk)); |
83803034 SH |
211 | } |
212 | ||
05d05450 | 213 | /* Track delayed acknowledgment ratio using sliding window |
83803034 SH |
214 | * ratio = (15*ratio + sample) / 16 |
215 | */ | |
6687e988 | 216 | static void bictcp_acked(struct sock *sk, u32 cnt) |
83803034 | 217 | { |
6687e988 ACM |
218 | const struct inet_connection_sock *icsk = inet_csk(sk); |
219 | ||
05d05450 | 220 | if (cnt > 0 && icsk->icsk_ca_state == TCP_CA_Open) { |
6687e988 | 221 | struct bictcp *ca = inet_csk_ca(sk); |
83803034 SH |
222 | cnt -= ca->delayed_ack >> ACK_RATIO_SHIFT; |
223 | ca->delayed_ack += cnt; | |
224 | } | |
225 | } | |
226 | ||
227 | ||
228 | static struct tcp_congestion_ops bictcp = { | |
229 | .init = bictcp_init, | |
230 | .ssthresh = bictcp_recalc_ssthresh, | |
231 | .cong_avoid = bictcp_cong_avoid, | |
232 | .set_state = bictcp_state, | |
233 | .undo_cwnd = bictcp_undo_cwnd, | |
234 | .min_cwnd = bictcp_min_cwnd, | |
235 | .pkts_acked = bictcp_acked, | |
236 | .owner = THIS_MODULE, | |
237 | .name = "bic", | |
238 | }; | |
239 | ||
240 | static int __init bictcp_register(void) | |
241 | { | |
6687e988 | 242 | BUG_ON(sizeof(struct bictcp) > ICSK_CA_PRIV_SIZE); |
83803034 SH |
243 | return tcp_register_congestion_control(&bictcp); |
244 | } | |
245 | ||
246 | static void __exit bictcp_unregister(void) | |
247 | { | |
248 | tcp_unregister_congestion_control(&bictcp); | |
249 | } | |
250 | ||
251 | module_init(bictcp_register); | |
252 | module_exit(bictcp_unregister); | |
253 | ||
254 | MODULE_AUTHOR("Stephen Hemminger"); | |
255 | MODULE_LICENSE("GPL"); | |
256 | MODULE_DESCRIPTION("BIC TCP"); |