Root/
1 | /* |
2 | * Binary Increase Congestion control for TCP |
3 | * Home page: |
4 | * http://netsrv.csc.ncsu.edu/twiki/bin/view/Main/BIC |
5 | * This is from the implementation of BICTCP in |
6 | * Lison-Xu, Kahaled Harfoush, and Injong Rhee. |
7 | * "Binary Increase Congestion Control for Fast, Long Distance |
8 | * Networks" in InfoComm 2004 |
9 | * Available from: |
10 | * http://netsrv.csc.ncsu.edu/export/bitcp.pdf |
11 | * |
12 | * Unless BIC is enabled and congestion window is large |
13 | * this behaves the same as the original Reno. |
14 | */ |
15 | |
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; |
30 | static int max_increment = 16; |
31 | static int low_window = 14; |
32 | static int beta = 819; /* = 819/1024 (BICTCP_BETA_SCALE) */ |
33 | static int initial_ssthresh; |
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"); |
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 */ |
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; |
69 | ca->epoch_start = 0; |
70 | ca->delayed_ack = 2 << ACK_RATIO_SHIFT; |
71 | } |
72 | |
73 | static void bictcp_init(struct sock *sk) |
74 | { |
75 | bictcp_reset(inet_csk_ca(sk)); |
76 | if (initial_ssthresh) |
77 | tcp_sk(sk)->snd_ssthresh = initial_ssthresh; |
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)) |
123 | / (cwnd - ca->last_max_cwnd); |
124 | else |
125 | /* linear increase */ |
126 | ca->cnt = cwnd / max_increment; |
127 | } |
128 | |
129 | /* if in slow start or link utilization is very low */ |
130 | if (ca->loss_cwnd == 0) { |
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 | |
140 | static void bictcp_cong_avoid(struct sock *sk, u32 ack, u32 in_flight) |
141 | { |
142 | struct tcp_sock *tp = tcp_sk(sk); |
143 | struct bictcp *ca = inet_csk_ca(sk); |
144 | |
145 | if (!tcp_is_cwnd_limited(sk, in_flight)) |
146 | return; |
147 | |
148 | if (tp->snd_cwnd <= tp->snd_ssthresh) |
149 | tcp_slow_start(tp); |
150 | else { |
151 | bictcp_update(ca, tp->snd_cwnd); |
152 | tcp_cong_avoid_ai(tp, ca->cnt); |
153 | } |
154 | |
155 | } |
156 | |
157 | /* |
158 | * behave like Reno until low_window is reached, |
159 | * then increase congestion window slowly |
160 | */ |
161 | static u32 bictcp_recalc_ssthresh(struct sock *sk) |
162 | { |
163 | const struct tcp_sock *tp = tcp_sk(sk); |
164 | struct bictcp *ca = inet_csk_ca(sk); |
165 | |
166 | ca->epoch_start = 0; /* end of epoch */ |
167 | |
168 | /* Wmax and fast convergence */ |
169 | if (tp->snd_cwnd < ca->last_max_cwnd && fast_convergence) |
170 | ca->last_max_cwnd = (tp->snd_cwnd * (BICTCP_BETA_SCALE + beta)) |
171 | / (2 * BICTCP_BETA_SCALE); |
172 | else |
173 | ca->last_max_cwnd = tp->snd_cwnd; |
174 | |
175 | ca->loss_cwnd = tp->snd_cwnd; |
176 | |
177 | |
178 | if (tp->snd_cwnd <= low_window) |
179 | return max(tp->snd_cwnd >> 1U, 2U); |
180 | else |
181 | return max((tp->snd_cwnd * beta) / BICTCP_BETA_SCALE, 2U); |
182 | } |
183 | |
184 | static u32 bictcp_undo_cwnd(struct sock *sk) |
185 | { |
186 | const struct tcp_sock *tp = tcp_sk(sk); |
187 | const struct bictcp *ca = inet_csk_ca(sk); |
188 | return max(tp->snd_cwnd, ca->last_max_cwnd); |
189 | } |
190 | |
191 | static void bictcp_state(struct sock *sk, u8 new_state) |
192 | { |
193 | if (new_state == TCP_CA_Loss) |
194 | bictcp_reset(inet_csk_ca(sk)); |
195 | } |
196 | |
197 | /* Track delayed acknowledgment ratio using sliding window |
198 | * ratio = (15*ratio + sample) / 16 |
199 | */ |
200 | static void bictcp_acked(struct sock *sk, u32 cnt, s32 rtt) |
201 | { |
202 | const struct inet_connection_sock *icsk = inet_csk(sk); |
203 | |
204 | if (icsk->icsk_ca_state == TCP_CA_Open) { |
205 | struct bictcp *ca = inet_csk_ca(sk); |
206 | cnt -= ca->delayed_ack >> ACK_RATIO_SHIFT; |
207 | ca->delayed_ack += cnt; |
208 | } |
209 | } |
210 | |
211 | |
212 | static struct tcp_congestion_ops bictcp = { |
213 | .init = bictcp_init, |
214 | .ssthresh = bictcp_recalc_ssthresh, |
215 | .cong_avoid = bictcp_cong_avoid, |
216 | .set_state = bictcp_state, |
217 | .undo_cwnd = bictcp_undo_cwnd, |
218 | .pkts_acked = bictcp_acked, |
219 | .owner = THIS_MODULE, |
220 | .name = "bic", |
221 | }; |
222 | |
223 | static int __init bictcp_register(void) |
224 | { |
225 | BUILD_BUG_ON(sizeof(struct bictcp) > ICSK_CA_PRIV_SIZE); |
226 | return tcp_register_congestion_control(&bictcp); |
227 | } |
228 | |
229 | static void __exit bictcp_unregister(void) |
230 | { |
231 | tcp_unregister_congestion_control(&bictcp); |
232 | } |
233 | |
234 | module_init(bictcp_register); |
235 | module_exit(bictcp_unregister); |
236 | |
237 | MODULE_AUTHOR("Stephen Hemminger"); |
238 | MODULE_LICENSE("GPL"); |
239 | MODULE_DESCRIPTION("BIC TCP"); |
240 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9