Commit | Line | Data |
---|---|---|
5ef81475 AC |
1 | /* |
2 | * | |
3 | * YeAH TCP | |
4 | * | |
5 | * For further details look at: | |
6 | * http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf | |
7 | * | |
8 | */ | |
9 | ||
10 | #include "tcp_yeah.h" | |
11 | ||
12 | /* Default values of the Vegas variables, in fixed-point representation | |
13 | * with V_PARAM_SHIFT bits to the right of the binary point. | |
14 | */ | |
15 | #define V_PARAM_SHIFT 1 | |
16 | ||
17 | #define TCP_YEAH_ALPHA 80 //lin number of packets queued at the bottleneck | |
18 | #define TCP_YEAH_GAMMA 1 //lin fraction of queue to be removed per rtt | |
19 | #define TCP_YEAH_DELTA 3 //log minimum fraction of cwnd to be removed on loss | |
20 | #define TCP_YEAH_EPSILON 1 //log maximum fraction to be removed on early decongestion | |
21 | #define TCP_YEAH_PHY 8 //lin maximum delta from base | |
22 | #define TCP_YEAH_RHO 16 //lin minumum number of consecutive rtt to consider competition on loss | |
23 | #define TCP_YEAH_ZETA 50 //lin minimum number of state switchs to reset reno_count | |
24 | ||
25 | #define TCP_SCALABLE_AI_CNT 100U | |
26 | ||
27 | /* YeAH variables */ | |
28 | struct yeah { | |
29 | /* Vegas */ | |
30 | u32 beg_snd_nxt; /* right edge during last RTT */ | |
31 | u32 beg_snd_una; /* left edge during last RTT */ | |
32 | u32 beg_snd_cwnd; /* saves the size of the cwnd */ | |
33 | u8 doing_vegas_now;/* if true, do vegas for this RTT */ | |
34 | u16 cntRTT; /* # of RTTs measured within last RTT */ | |
35 | u32 minRTT; /* min of RTTs measured within last RTT (in usec) */ | |
36 | u32 baseRTT; /* the min of all Vegas RTT measurements seen (in usec) */ | |
37 | ||
38 | /* YeAH */ | |
39 | u32 lastQ; | |
40 | u32 doing_reno_now; | |
41 | ||
42 | u32 reno_count; | |
43 | u32 fast_count; | |
44 | ||
45 | u32 pkts_acked; | |
46 | }; | |
47 | ||
48 | static void tcp_yeah_init(struct sock *sk) | |
49 | { | |
50 | struct tcp_sock *tp = tcp_sk(sk); | |
51 | struct yeah *yeah = inet_csk_ca(sk); | |
52 | ||
53 | tcp_vegas_init(sk); | |
54 | ||
55 | yeah->doing_reno_now = 0; | |
56 | yeah->lastQ = 0; | |
57 | ||
58 | yeah->reno_count = 2; | |
59 | ||
60 | /* Ensure the MD arithmetic works. This is somewhat pedantic, | |
61 | * since I don't think we will see a cwnd this large. :) */ | |
62 | tp->snd_cwnd_clamp = min_t(u32, tp->snd_cwnd_clamp, 0xffffffff/128); | |
63 | ||
64 | } | |
65 | ||
66 | ||
67 | static void tcp_yeah_pkts_acked(struct sock *sk, u32 pkts_acked) | |
68 | { | |
69 | const struct inet_connection_sock *icsk = inet_csk(sk); | |
70 | struct yeah *yeah = inet_csk_ca(sk); | |
71 | ||
72 | if (icsk->icsk_ca_state == TCP_CA_Open) | |
73 | yeah->pkts_acked = pkts_acked; | |
74 | } | |
75 | ||
5ef81475 | 76 | static void tcp_yeah_cong_avoid(struct sock *sk, u32 ack, |
43e68392 | 77 | u32 seq_rtt, u32 in_flight, int flag) |
5ef81475 AC |
78 | { |
79 | struct tcp_sock *tp = tcp_sk(sk); | |
80 | struct yeah *yeah = inet_csk_ca(sk); | |
81 | ||
82 | if (!tcp_is_cwnd_limited(sk, in_flight)) | |
83 | return; | |
84 | ||
85 | if (tp->snd_cwnd <= tp->snd_ssthresh) { | |
86 | tcp_slow_start(tp); | |
87 | } else if (!yeah->doing_reno_now) { | |
88 | /* Scalable */ | |
89 | ||
90 | tp->snd_cwnd_cnt+=yeah->pkts_acked; | |
91 | if (tp->snd_cwnd_cnt > min(tp->snd_cwnd, TCP_SCALABLE_AI_CNT)){ | |
92 | if (tp->snd_cwnd < tp->snd_cwnd_clamp) | |
93 | tp->snd_cwnd++; | |
94 | tp->snd_cwnd_cnt = 0; | |
95 | } | |
96 | ||
97 | yeah->pkts_acked = 1; | |
98 | ||
99 | } else { | |
100 | /* Reno */ | |
101 | ||
102 | if (tp->snd_cwnd_cnt < tp->snd_cwnd) | |
103 | tp->snd_cwnd_cnt++; | |
104 | ||
105 | if (tp->snd_cwnd_cnt >= tp->snd_cwnd) { | |
106 | tp->snd_cwnd++; | |
107 | tp->snd_cwnd_cnt = 0; | |
108 | } | |
109 | } | |
110 | ||
111 | /* The key players are v_beg_snd_una and v_beg_snd_nxt. | |
112 | * | |
113 | * These are so named because they represent the approximate values | |
114 | * of snd_una and snd_nxt at the beginning of the current RTT. More | |
115 | * precisely, they represent the amount of data sent during the RTT. | |
116 | * At the end of the RTT, when we receive an ACK for v_beg_snd_nxt, | |
117 | * we will calculate that (v_beg_snd_nxt - v_beg_snd_una) outstanding | |
118 | * bytes of data have been ACKed during the course of the RTT, giving | |
119 | * an "actual" rate of: | |
120 | * | |
121 | * (v_beg_snd_nxt - v_beg_snd_una) / (rtt duration) | |
122 | * | |
123 | * Unfortunately, v_beg_snd_una is not exactly equal to snd_una, | |
124 | * because delayed ACKs can cover more than one segment, so they | |
125 | * don't line up yeahly with the boundaries of RTTs. | |
126 | * | |
127 | * Another unfortunate fact of life is that delayed ACKs delay the | |
128 | * advance of the left edge of our send window, so that the number | |
129 | * of bytes we send in an RTT is often less than our cwnd will allow. | |
130 | * So we keep track of our cwnd separately, in v_beg_snd_cwnd. | |
131 | */ | |
132 | ||
133 | if (after(ack, yeah->beg_snd_nxt)) { | |
134 | ||
135 | /* We do the Vegas calculations only if we got enough RTT | |
136 | * samples that we can be reasonably sure that we got | |
137 | * at least one RTT sample that wasn't from a delayed ACK. | |
138 | * If we only had 2 samples total, | |
139 | * then that means we're getting only 1 ACK per RTT, which | |
140 | * means they're almost certainly delayed ACKs. | |
141 | * If we have 3 samples, we should be OK. | |
142 | */ | |
143 | ||
144 | if (yeah->cntRTT > 2) { | |
43e68392 SH |
145 | u32 rtt, queue; |
146 | u64 bw; | |
5ef81475 AC |
147 | |
148 | /* We have enough RTT samples, so, using the Vegas | |
149 | * algorithm, we determine if we should increase or | |
150 | * decrease cwnd, and by how much. | |
151 | */ | |
152 | ||
153 | /* Pluck out the RTT we are using for the Vegas | |
154 | * calculations. This is the min RTT seen during the | |
155 | * last RTT. Taking the min filters out the effects | |
156 | * of delayed ACKs, at the cost of noticing congestion | |
157 | * a bit later. | |
158 | */ | |
159 | rtt = yeah->minRTT; | |
160 | ||
43e68392 SH |
161 | /* Compute excess number of packets above bandwidth |
162 | * Avoid doing full 64 bit divide. | |
163 | */ | |
164 | bw = tp->snd_cwnd; | |
165 | bw *= rtt - yeah->baseRTT; | |
166 | do_div(bw, rtt); | |
167 | queue = bw; | |
168 | ||
169 | if (queue > TCP_YEAH_ALPHA || | |
170 | rtt - yeah->baseRTT > (yeah->baseRTT / TCP_YEAH_PHY)) { | |
171 | if (queue > TCP_YEAH_ALPHA | |
172 | && tp->snd_cwnd > yeah->reno_count) { | |
173 | u32 reduction = min(queue / TCP_YEAH_GAMMA , | |
174 | tp->snd_cwnd >> TCP_YEAH_EPSILON); | |
5ef81475 AC |
175 | |
176 | tp->snd_cwnd -= reduction; | |
177 | ||
43e68392 SH |
178 | tp->snd_cwnd = max(tp->snd_cwnd, |
179 | yeah->reno_count); | |
5ef81475 AC |
180 | |
181 | tp->snd_ssthresh = tp->snd_cwnd; | |
43e68392 | 182 | } |
5ef81475 AC |
183 | |
184 | if (yeah->reno_count <= 2) | |
43e68392 | 185 | yeah->reno_count = max(tp->snd_cwnd>>1, 2U); |
5ef81475 AC |
186 | else |
187 | yeah->reno_count++; | |
188 | ||
43e68392 SH |
189 | yeah->doing_reno_now = min(yeah->doing_reno_now + 1, |
190 | 0xffffffU); | |
5ef81475 AC |
191 | } else { |
192 | yeah->fast_count++; | |
193 | ||
194 | if (yeah->fast_count > TCP_YEAH_ZETA) { | |
195 | yeah->reno_count = 2; | |
196 | yeah->fast_count = 0; | |
197 | } | |
198 | ||
199 | yeah->doing_reno_now = 0; | |
200 | } | |
201 | ||
202 | yeah->lastQ = queue; | |
203 | ||
204 | } | |
205 | ||
206 | /* Save the extent of the current window so we can use this | |
207 | * at the end of the next RTT. | |
208 | */ | |
209 | yeah->beg_snd_una = yeah->beg_snd_nxt; | |
210 | yeah->beg_snd_nxt = tp->snd_nxt; | |
211 | yeah->beg_snd_cwnd = tp->snd_cwnd; | |
212 | ||
213 | /* Wipe the slate clean for the next RTT. */ | |
214 | yeah->cntRTT = 0; | |
215 | yeah->minRTT = 0x7fffffff; | |
216 | } | |
217 | } | |
218 | ||
219 | static u32 tcp_yeah_ssthresh(struct sock *sk) { | |
220 | const struct tcp_sock *tp = tcp_sk(sk); | |
221 | struct yeah *yeah = inet_csk_ca(sk); | |
222 | u32 reduction; | |
223 | ||
224 | if (yeah->doing_reno_now < TCP_YEAH_RHO) { | |
225 | reduction = yeah->lastQ; | |
226 | ||
227 | reduction = min( reduction, max(tp->snd_cwnd>>1, 2U) ); | |
228 | ||
229 | reduction = max( reduction, tp->snd_cwnd >> TCP_YEAH_DELTA); | |
230 | } else | |
231 | reduction = max(tp->snd_cwnd>>1,2U); | |
232 | ||
233 | yeah->fast_count = 0; | |
234 | yeah->reno_count = max(yeah->reno_count>>1, 2U); | |
235 | ||
236 | return tp->snd_cwnd - reduction; | |
237 | } | |
238 | ||
239 | static struct tcp_congestion_ops tcp_yeah = { | |
240 | .init = tcp_yeah_init, | |
241 | .ssthresh = tcp_yeah_ssthresh, | |
242 | .cong_avoid = tcp_yeah_cong_avoid, | |
243 | .min_cwnd = tcp_reno_min_cwnd, | |
244 | .rtt_sample = tcp_vegas_rtt_calc, | |
245 | .set_state = tcp_vegas_state, | |
246 | .cwnd_event = tcp_vegas_cwnd_event, | |
247 | .get_info = tcp_vegas_get_info, | |
248 | .pkts_acked = tcp_yeah_pkts_acked, | |
249 | ||
250 | .owner = THIS_MODULE, | |
251 | .name = "yeah", | |
252 | }; | |
253 | ||
254 | static int __init tcp_yeah_register(void) | |
255 | { | |
256 | BUG_ON(sizeof(struct yeah) > ICSK_CA_PRIV_SIZE); | |
257 | tcp_register_congestion_control(&tcp_yeah); | |
258 | return 0; | |
259 | } | |
260 | ||
261 | static void __exit tcp_yeah_unregister(void) | |
262 | { | |
263 | tcp_unregister_congestion_control(&tcp_yeah); | |
264 | } | |
265 | ||
266 | module_init(tcp_yeah_register); | |
267 | module_exit(tcp_yeah_unregister); | |
268 | ||
269 | MODULE_AUTHOR("Angelo P. Castellani"); | |
270 | MODULE_LICENSE("GPL"); | |
271 | MODULE_DESCRIPTION("YeAH TCP"); |