]>
Commit | Line | Data |
---|---|---|
a7868ea6 BE |
1 | /* |
2 | * H-TCP congestion control. The algorithm is detailed in: | |
3 | * R.N.Shorten, D.J.Leith: | |
4 | * "H-TCP: TCP for high-speed and long-distance networks" | |
5 | * Proc. PFLDnet, Argonne, 2004. | |
6 | * http://www.hamilton.ie/net/htcp3.pdf | |
7 | */ | |
8 | ||
9 | #include <linux/config.h> | |
10 | #include <linux/mm.h> | |
11 | #include <linux/module.h> | |
12 | #include <net/tcp.h> | |
13 | ||
14 | #define ALPHA_BASE (1<<7) /* 1.0 with shift << 7 */ | |
15 | #define BETA_MIN (1<<6) /* 0.5 with shift << 7 */ | |
16 | #define BETA_MAX 102 /* 0.8 with shift << 7 */ | |
17 | ||
18 | static int use_rtt_scaling = 1; | |
19 | module_param(use_rtt_scaling, int, 0644); | |
20 | MODULE_PARM_DESC(use_rtt_scaling, "turn on/off RTT scaling"); | |
21 | ||
22 | static int use_bandwidth_switch = 1; | |
23 | module_param(use_bandwidth_switch, int, 0644); | |
24 | MODULE_PARM_DESC(use_bandwidth_switch, "turn on/off bandwidth switcher"); | |
25 | ||
26 | struct htcp { | |
27 | u16 alpha; /* Fixed point arith, << 7 */ | |
28 | u8 beta; /* Fixed point arith, << 7 */ | |
29 | u8 modeswitch; /* Delay modeswitch until we had at least one congestion event */ | |
30 | u8 ccount; /* Number of RTTs since last congestion event */ | |
31 | u8 undo_ccount; | |
32 | u16 packetcount; | |
33 | u32 minRTT; | |
34 | u32 maxRTT; | |
35 | u32 snd_cwnd_cnt2; | |
36 | ||
37 | u32 undo_maxRTT; | |
38 | u32 undo_old_maxB; | |
39 | ||
40 | /* Bandwidth estimation */ | |
41 | u32 minB; | |
42 | u32 maxB; | |
43 | u32 old_maxB; | |
44 | u32 Bi; | |
45 | u32 lasttime; | |
46 | }; | |
47 | ||
48 | static inline void htcp_reset(struct htcp *ca) | |
49 | { | |
50 | ca->undo_ccount = ca->ccount; | |
51 | ca->undo_maxRTT = ca->maxRTT; | |
52 | ca->undo_old_maxB = ca->old_maxB; | |
53 | ||
54 | ca->ccount = 0; | |
55 | ca->snd_cwnd_cnt2 = 0; | |
56 | } | |
57 | ||
6687e988 | 58 | static u32 htcp_cwnd_undo(struct sock *sk) |
a7868ea6 | 59 | { |
6687e988 ACM |
60 | const struct tcp_sock *tp = tcp_sk(sk); |
61 | struct htcp *ca = inet_csk_ca(sk); | |
a7868ea6 BE |
62 | ca->ccount = ca->undo_ccount; |
63 | ca->maxRTT = ca->undo_maxRTT; | |
64 | ca->old_maxB = ca->undo_old_maxB; | |
65 | return max(tp->snd_cwnd, (tp->snd_ssthresh<<7)/ca->beta); | |
66 | } | |
67 | ||
6687e988 | 68 | static inline void measure_rtt(struct sock *sk) |
a7868ea6 | 69 | { |
6687e988 ACM |
70 | const struct inet_connection_sock *icsk = inet_csk(sk); |
71 | const struct tcp_sock *tp = tcp_sk(sk); | |
72 | struct htcp *ca = inet_csk_ca(sk); | |
a7868ea6 BE |
73 | u32 srtt = tp->srtt>>3; |
74 | ||
75 | /* keep track of minimum RTT seen so far, minRTT is zero at first */ | |
76 | if (ca->minRTT > srtt || !ca->minRTT) | |
77 | ca->minRTT = srtt; | |
78 | ||
79 | /* max RTT */ | |
6687e988 | 80 | if (icsk->icsk_ca_state == TCP_CA_Open && tp->snd_ssthresh < 0xFFFF && ca->ccount > 3) { |
a7868ea6 BE |
81 | if (ca->maxRTT < ca->minRTT) |
82 | ca->maxRTT = ca->minRTT; | |
83 | if (ca->maxRTT < srtt && srtt <= ca->maxRTT+HZ/50) | |
84 | ca->maxRTT = srtt; | |
85 | } | |
86 | } | |
87 | ||
6687e988 | 88 | static void measure_achieved_throughput(struct sock *sk, u32 pkts_acked) |
a7868ea6 | 89 | { |
6687e988 ACM |
90 | const struct inet_connection_sock *icsk = inet_csk(sk); |
91 | const struct tcp_sock *tp = tcp_sk(sk); | |
92 | struct htcp *ca = inet_csk_ca(sk); | |
a7868ea6 BE |
93 | u32 now = tcp_time_stamp; |
94 | ||
95 | /* achieved throughput calculations */ | |
6687e988 ACM |
96 | if (icsk->icsk_ca_state != TCP_CA_Open && |
97 | icsk->icsk_ca_state != TCP_CA_Disorder) { | |
a7868ea6 BE |
98 | ca->packetcount = 0; |
99 | ca->lasttime = now; | |
100 | return; | |
101 | } | |
102 | ||
103 | ca->packetcount += pkts_acked; | |
104 | ||
105 | if (ca->packetcount >= tp->snd_cwnd - (ca->alpha>>7? : 1) | |
106 | && now - ca->lasttime >= ca->minRTT | |
107 | && ca->minRTT > 0) { | |
108 | __u32 cur_Bi = ca->packetcount*HZ/(now - ca->lasttime); | |
109 | if (ca->ccount <= 3) { | |
110 | /* just after backoff */ | |
111 | ca->minB = ca->maxB = ca->Bi = cur_Bi; | |
112 | } else { | |
113 | ca->Bi = (3*ca->Bi + cur_Bi)/4; | |
114 | if (ca->Bi > ca->maxB) | |
115 | ca->maxB = ca->Bi; | |
116 | if (ca->minB > ca->maxB) | |
117 | ca->minB = ca->maxB; | |
118 | } | |
119 | ca->packetcount = 0; | |
120 | ca->lasttime = now; | |
121 | } | |
122 | } | |
123 | ||
124 | static inline void htcp_beta_update(struct htcp *ca, u32 minRTT, u32 maxRTT) | |
125 | { | |
126 | if (use_bandwidth_switch) { | |
127 | u32 maxB = ca->maxB; | |
128 | u32 old_maxB = ca->old_maxB; | |
129 | ca->old_maxB = ca->maxB; | |
130 | ||
131 | if (!between(5*maxB, 4*old_maxB, 6*old_maxB)) { | |
132 | ca->beta = BETA_MIN; | |
133 | ca->modeswitch = 0; | |
134 | return; | |
135 | } | |
136 | } | |
137 | ||
138 | if (ca->modeswitch && minRTT > max(HZ/100, 1) && maxRTT) { | |
139 | ca->beta = (minRTT<<7)/maxRTT; | |
140 | if (ca->beta < BETA_MIN) | |
141 | ca->beta = BETA_MIN; | |
142 | else if (ca->beta > BETA_MAX) | |
143 | ca->beta = BETA_MAX; | |
144 | } else { | |
145 | ca->beta = BETA_MIN; | |
146 | ca->modeswitch = 1; | |
147 | } | |
148 | } | |
149 | ||
150 | static inline void htcp_alpha_update(struct htcp *ca) | |
151 | { | |
152 | u32 minRTT = ca->minRTT; | |
153 | u32 factor = 1; | |
154 | u32 diff = ca->ccount * minRTT; /* time since last backoff */ | |
155 | ||
156 | if (diff > HZ) { | |
157 | diff -= HZ; | |
158 | factor = 1+ ( 10*diff + ((diff/2)*(diff/2)/HZ) )/HZ; | |
159 | } | |
160 | ||
161 | if (use_rtt_scaling && minRTT) { | |
162 | u32 scale = (HZ<<3)/(10*minRTT); | |
163 | scale = min(max(scale, 1U<<2), 10U<<3); /* clamping ratio to interval [0.5,10]<<3 */ | |
164 | factor = (factor<<3)/scale; | |
165 | if (!factor) | |
166 | factor = 1; | |
167 | } | |
168 | ||
169 | ca->alpha = 2*factor*((1<<7)-ca->beta); | |
170 | if (!ca->alpha) | |
171 | ca->alpha = ALPHA_BASE; | |
172 | } | |
173 | ||
174 | /* After we have the rtt data to calculate beta, we'd still prefer to wait one | |
175 | * rtt before we adjust our beta to ensure we are working from a consistent | |
176 | * data. | |
177 | * | |
178 | * This function should be called when we hit a congestion event since only at | |
179 | * that point do we really have a real sense of maxRTT (the queues en route | |
180 | * were getting just too full now). | |
181 | */ | |
6687e988 | 182 | static void htcp_param_update(struct sock *sk) |
a7868ea6 | 183 | { |
6687e988 | 184 | struct htcp *ca = inet_csk_ca(sk); |
a7868ea6 BE |
185 | u32 minRTT = ca->minRTT; |
186 | u32 maxRTT = ca->maxRTT; | |
187 | ||
188 | htcp_beta_update(ca, minRTT, maxRTT); | |
189 | htcp_alpha_update(ca); | |
190 | ||
191 | /* add slowly fading memory for maxRTT to accommodate routing changes etc */ | |
192 | if (minRTT > 0 && maxRTT > minRTT) | |
193 | ca->maxRTT = minRTT + ((maxRTT-minRTT)*95)/100; | |
194 | } | |
195 | ||
6687e988 | 196 | static u32 htcp_recalc_ssthresh(struct sock *sk) |
a7868ea6 | 197 | { |
6687e988 ACM |
198 | const struct tcp_sock *tp = tcp_sk(sk); |
199 | const struct htcp *ca = inet_csk_ca(sk); | |
200 | htcp_param_update(sk); | |
a7868ea6 BE |
201 | return max((tp->snd_cwnd * ca->beta) >> 7, 2U); |
202 | } | |
203 | ||
6687e988 | 204 | static void htcp_cong_avoid(struct sock *sk, u32 ack, u32 rtt, |
a7868ea6 BE |
205 | u32 in_flight, int data_acked) |
206 | { | |
6687e988 ACM |
207 | struct tcp_sock *tp = tcp_sk(sk); |
208 | struct htcp *ca = inet_csk_ca(sk); | |
a7868ea6 | 209 | |
f4805ede | 210 | if (!tcp_is_cwnd_limited(sk, in_flight)) |
a7868ea6 BE |
211 | return; |
212 | ||
213 | if (tp->snd_cwnd <= tp->snd_ssthresh) { | |
214 | /* In "safe" area, increase. */ | |
215 | if (tp->snd_cwnd < tp->snd_cwnd_clamp) | |
216 | tp->snd_cwnd++; | |
217 | } else { | |
6687e988 | 218 | measure_rtt(sk); |
a7868ea6 BE |
219 | |
220 | /* keep track of number of round-trip times since last backoff event */ | |
221 | if (ca->snd_cwnd_cnt2++ > tp->snd_cwnd) { | |
222 | ca->ccount++; | |
223 | ca->snd_cwnd_cnt2 = 0; | |
224 | htcp_alpha_update(ca); | |
225 | } | |
226 | ||
227 | /* In dangerous area, increase slowly. | |
228 | * In theory this is tp->snd_cwnd += alpha / tp->snd_cwnd | |
229 | */ | |
230 | if ((tp->snd_cwnd_cnt++ * ca->alpha)>>7 >= tp->snd_cwnd) { | |
231 | if (tp->snd_cwnd < tp->snd_cwnd_clamp) | |
232 | tp->snd_cwnd++; | |
233 | tp->snd_cwnd_cnt = 0; | |
234 | ca->ccount++; | |
235 | } | |
236 | } | |
237 | } | |
238 | ||
239 | /* Lower bound on congestion window. */ | |
6687e988 | 240 | static u32 htcp_min_cwnd(struct sock *sk) |
a7868ea6 | 241 | { |
6687e988 | 242 | const struct tcp_sock *tp = tcp_sk(sk); |
a7868ea6 BE |
243 | return tp->snd_ssthresh; |
244 | } | |
245 | ||
246 | ||
6687e988 | 247 | static void htcp_init(struct sock *sk) |
a7868ea6 | 248 | { |
6687e988 | 249 | struct htcp *ca = inet_csk_ca(sk); |
a7868ea6 BE |
250 | |
251 | memset(ca, 0, sizeof(struct htcp)); | |
252 | ca->alpha = ALPHA_BASE; | |
253 | ca->beta = BETA_MIN; | |
254 | } | |
255 | ||
6687e988 | 256 | static void htcp_state(struct sock *sk, u8 new_state) |
a7868ea6 BE |
257 | { |
258 | switch (new_state) { | |
259 | case TCP_CA_CWR: | |
260 | case TCP_CA_Recovery: | |
261 | case TCP_CA_Loss: | |
6687e988 | 262 | htcp_reset(inet_csk_ca(sk)); |
a7868ea6 BE |
263 | break; |
264 | } | |
265 | } | |
266 | ||
267 | static struct tcp_congestion_ops htcp = { | |
268 | .init = htcp_init, | |
269 | .ssthresh = htcp_recalc_ssthresh, | |
270 | .min_cwnd = htcp_min_cwnd, | |
271 | .cong_avoid = htcp_cong_avoid, | |
272 | .set_state = htcp_state, | |
273 | .undo_cwnd = htcp_cwnd_undo, | |
274 | .pkts_acked = measure_achieved_throughput, | |
275 | .owner = THIS_MODULE, | |
276 | .name = "htcp", | |
277 | }; | |
278 | ||
279 | static int __init htcp_register(void) | |
280 | { | |
6687e988 | 281 | BUG_ON(sizeof(struct htcp) > ICSK_CA_PRIV_SIZE); |
a7868ea6 BE |
282 | BUILD_BUG_ON(BETA_MIN >= BETA_MAX); |
283 | if (!use_bandwidth_switch) | |
284 | htcp.pkts_acked = NULL; | |
285 | return tcp_register_congestion_control(&htcp); | |
286 | } | |
287 | ||
288 | static void __exit htcp_unregister(void) | |
289 | { | |
290 | tcp_unregister_congestion_control(&htcp); | |
291 | } | |
292 | ||
293 | module_init(htcp_register); | |
294 | module_exit(htcp_unregister); | |
295 | ||
296 | MODULE_AUTHOR("Baruch Even"); | |
297 | MODULE_LICENSE("GPL"); | |
298 | MODULE_DESCRIPTION("H-TCP"); |