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 */ | |
50bf3e22 BE |
30 | u32 last_cong; /* Time since last congestion event end */ |
31 | u32 undo_last_cong; | |
0bc6d90b BE |
32 | u16 pkts_acked; |
33 | u32 packetcount; | |
a7868ea6 BE |
34 | u32 minRTT; |
35 | u32 maxRTT; | |
a7868ea6 BE |
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 | ||
50bf3e22 BE |
48 | static inline u32 htcp_cong_time(struct htcp *ca) |
49 | { | |
50 | return jiffies - ca->last_cong; | |
51 | } | |
52 | ||
53 | static inline u32 htcp_ccount(struct htcp *ca) | |
54 | { | |
55 | return htcp_cong_time(ca)/ca->minRTT; | |
56 | } | |
57 | ||
a7868ea6 BE |
58 | static inline void htcp_reset(struct htcp *ca) |
59 | { | |
50bf3e22 | 60 | ca->undo_last_cong = ca->last_cong; |
a7868ea6 BE |
61 | ca->undo_maxRTT = ca->maxRTT; |
62 | ca->undo_old_maxB = ca->old_maxB; | |
63 | ||
50bf3e22 | 64 | ca->last_cong = jiffies; |
a7868ea6 BE |
65 | } |
66 | ||
6687e988 | 67 | static u32 htcp_cwnd_undo(struct sock *sk) |
a7868ea6 | 68 | { |
6687e988 ACM |
69 | const struct tcp_sock *tp = tcp_sk(sk); |
70 | struct htcp *ca = inet_csk_ca(sk); | |
50bf3e22 | 71 | ca->last_cong = ca->undo_last_cong; |
a7868ea6 BE |
72 | ca->maxRTT = ca->undo_maxRTT; |
73 | ca->old_maxB = ca->undo_old_maxB; | |
74 | return max(tp->snd_cwnd, (tp->snd_ssthresh<<7)/ca->beta); | |
75 | } | |
76 | ||
6687e988 | 77 | static inline void measure_rtt(struct sock *sk) |
a7868ea6 | 78 | { |
6687e988 ACM |
79 | const struct inet_connection_sock *icsk = inet_csk(sk); |
80 | const struct tcp_sock *tp = tcp_sk(sk); | |
81 | struct htcp *ca = inet_csk_ca(sk); | |
a7868ea6 BE |
82 | u32 srtt = tp->srtt>>3; |
83 | ||
84 | /* keep track of minimum RTT seen so far, minRTT is zero at first */ | |
85 | if (ca->minRTT > srtt || !ca->minRTT) | |
86 | ca->minRTT = srtt; | |
87 | ||
88 | /* max RTT */ | |
50bf3e22 | 89 | if (icsk->icsk_ca_state == TCP_CA_Open && tp->snd_ssthresh < 0xFFFF && htcp_ccount(ca) > 3) { |
a7868ea6 BE |
90 | if (ca->maxRTT < ca->minRTT) |
91 | ca->maxRTT = ca->minRTT; | |
c33ad6e4 | 92 | if (ca->maxRTT < srtt && srtt <= ca->maxRTT+msecs_to_jiffies(20)) |
a7868ea6 BE |
93 | ca->maxRTT = srtt; |
94 | } | |
95 | } | |
96 | ||
6687e988 | 97 | static void measure_achieved_throughput(struct sock *sk, u32 pkts_acked) |
a7868ea6 | 98 | { |
6687e988 ACM |
99 | const struct inet_connection_sock *icsk = inet_csk(sk); |
100 | const struct tcp_sock *tp = tcp_sk(sk); | |
101 | struct htcp *ca = inet_csk_ca(sk); | |
a7868ea6 BE |
102 | u32 now = tcp_time_stamp; |
103 | ||
0bc6d90b BE |
104 | if (icsk->icsk_ca_state == TCP_CA_Open) |
105 | ca->pkts_acked = pkts_acked; | |
106 | ||
107 | if (!use_bandwidth_switch) | |
108 | return; | |
109 | ||
a7868ea6 | 110 | /* achieved throughput calculations */ |
6687e988 ACM |
111 | if (icsk->icsk_ca_state != TCP_CA_Open && |
112 | icsk->icsk_ca_state != TCP_CA_Disorder) { | |
a7868ea6 BE |
113 | ca->packetcount = 0; |
114 | ca->lasttime = now; | |
115 | return; | |
116 | } | |
117 | ||
118 | ca->packetcount += pkts_acked; | |
119 | ||
120 | if (ca->packetcount >= tp->snd_cwnd - (ca->alpha>>7? : 1) | |
121 | && now - ca->lasttime >= ca->minRTT | |
122 | && ca->minRTT > 0) { | |
123 | __u32 cur_Bi = ca->packetcount*HZ/(now - ca->lasttime); | |
50bf3e22 | 124 | if (htcp_ccount(ca) <= 3) { |
a7868ea6 BE |
125 | /* just after backoff */ |
126 | ca->minB = ca->maxB = ca->Bi = cur_Bi; | |
127 | } else { | |
128 | ca->Bi = (3*ca->Bi + cur_Bi)/4; | |
129 | if (ca->Bi > ca->maxB) | |
130 | ca->maxB = ca->Bi; | |
131 | if (ca->minB > ca->maxB) | |
132 | ca->minB = ca->maxB; | |
133 | } | |
134 | ca->packetcount = 0; | |
135 | ca->lasttime = now; | |
136 | } | |
137 | } | |
138 | ||
139 | static inline void htcp_beta_update(struct htcp *ca, u32 minRTT, u32 maxRTT) | |
140 | { | |
141 | if (use_bandwidth_switch) { | |
142 | u32 maxB = ca->maxB; | |
143 | u32 old_maxB = ca->old_maxB; | |
144 | ca->old_maxB = ca->maxB; | |
145 | ||
146 | if (!between(5*maxB, 4*old_maxB, 6*old_maxB)) { | |
147 | ca->beta = BETA_MIN; | |
148 | ca->modeswitch = 0; | |
149 | return; | |
150 | } | |
151 | } | |
152 | ||
c33ad6e4 | 153 | if (ca->modeswitch && minRTT > msecs_to_jiffies(10) && maxRTT) { |
a7868ea6 BE |
154 | ca->beta = (minRTT<<7)/maxRTT; |
155 | if (ca->beta < BETA_MIN) | |
156 | ca->beta = BETA_MIN; | |
157 | else if (ca->beta > BETA_MAX) | |
158 | ca->beta = BETA_MAX; | |
159 | } else { | |
160 | ca->beta = BETA_MIN; | |
161 | ca->modeswitch = 1; | |
162 | } | |
163 | } | |
164 | ||
165 | static inline void htcp_alpha_update(struct htcp *ca) | |
166 | { | |
167 | u32 minRTT = ca->minRTT; | |
168 | u32 factor = 1; | |
50bf3e22 | 169 | u32 diff = htcp_cong_time(ca); |
a7868ea6 BE |
170 | |
171 | if (diff > HZ) { | |
172 | diff -= HZ; | |
173 | factor = 1+ ( 10*diff + ((diff/2)*(diff/2)/HZ) )/HZ; | |
174 | } | |
175 | ||
176 | if (use_rtt_scaling && minRTT) { | |
177 | u32 scale = (HZ<<3)/(10*minRTT); | |
178 | scale = min(max(scale, 1U<<2), 10U<<3); /* clamping ratio to interval [0.5,10]<<3 */ | |
179 | factor = (factor<<3)/scale; | |
180 | if (!factor) | |
181 | factor = 1; | |
182 | } | |
183 | ||
184 | ca->alpha = 2*factor*((1<<7)-ca->beta); | |
185 | if (!ca->alpha) | |
186 | ca->alpha = ALPHA_BASE; | |
187 | } | |
188 | ||
189 | /* After we have the rtt data to calculate beta, we'd still prefer to wait one | |
190 | * rtt before we adjust our beta to ensure we are working from a consistent | |
191 | * data. | |
192 | * | |
193 | * This function should be called when we hit a congestion event since only at | |
194 | * that point do we really have a real sense of maxRTT (the queues en route | |
195 | * were getting just too full now). | |
196 | */ | |
6687e988 | 197 | static void htcp_param_update(struct sock *sk) |
a7868ea6 | 198 | { |
6687e988 | 199 | struct htcp *ca = inet_csk_ca(sk); |
a7868ea6 BE |
200 | u32 minRTT = ca->minRTT; |
201 | u32 maxRTT = ca->maxRTT; | |
202 | ||
203 | htcp_beta_update(ca, minRTT, maxRTT); | |
204 | htcp_alpha_update(ca); | |
205 | ||
206 | /* add slowly fading memory for maxRTT to accommodate routing changes etc */ | |
207 | if (minRTT > 0 && maxRTT > minRTT) | |
208 | ca->maxRTT = minRTT + ((maxRTT-minRTT)*95)/100; | |
209 | } | |
210 | ||
6687e988 | 211 | static u32 htcp_recalc_ssthresh(struct sock *sk) |
a7868ea6 | 212 | { |
6687e988 ACM |
213 | const struct tcp_sock *tp = tcp_sk(sk); |
214 | const struct htcp *ca = inet_csk_ca(sk); | |
215 | htcp_param_update(sk); | |
a7868ea6 BE |
216 | return max((tp->snd_cwnd * ca->beta) >> 7, 2U); |
217 | } | |
218 | ||
6687e988 | 219 | static void htcp_cong_avoid(struct sock *sk, u32 ack, u32 rtt, |
a7868ea6 BE |
220 | u32 in_flight, int data_acked) |
221 | { | |
6687e988 ACM |
222 | struct tcp_sock *tp = tcp_sk(sk); |
223 | struct htcp *ca = inet_csk_ca(sk); | |
a7868ea6 | 224 | |
f4805ede | 225 | if (!tcp_is_cwnd_limited(sk, in_flight)) |
a7868ea6 BE |
226 | return; |
227 | ||
7faffa1c SH |
228 | if (tp->snd_cwnd <= tp->snd_ssthresh) |
229 | tcp_slow_start(tp); | |
230 | else { | |
231 | ||
6687e988 | 232 | measure_rtt(sk); |
a7868ea6 | 233 | |
7faffa1c | 234 | /* In dangerous area, increase slowly. |
a7868ea6 BE |
235 | * In theory this is tp->snd_cwnd += alpha / tp->snd_cwnd |
236 | */ | |
0bc6d90b | 237 | if ((tp->snd_cwnd_cnt * ca->alpha)>>7 >= tp->snd_cwnd) { |
a7868ea6 BE |
238 | if (tp->snd_cwnd < tp->snd_cwnd_clamp) |
239 | tp->snd_cwnd++; | |
240 | tp->snd_cwnd_cnt = 0; | |
50bf3e22 | 241 | htcp_alpha_update(ca); |
0bc6d90b BE |
242 | } else |
243 | tp->snd_cwnd_cnt += ca->pkts_acked; | |
244 | ||
245 | ca->pkts_acked = 1; | |
a7868ea6 BE |
246 | } |
247 | } | |
248 | ||
6687e988 | 249 | static void htcp_init(struct sock *sk) |
a7868ea6 | 250 | { |
6687e988 | 251 | struct htcp *ca = inet_csk_ca(sk); |
a7868ea6 BE |
252 | |
253 | memset(ca, 0, sizeof(struct htcp)); | |
254 | ca->alpha = ALPHA_BASE; | |
255 | ca->beta = BETA_MIN; | |
0bc6d90b | 256 | ca->pkts_acked = 1; |
50bf3e22 | 257 | ca->last_cong = jiffies; |
a7868ea6 BE |
258 | } |
259 | ||
6687e988 | 260 | static void htcp_state(struct sock *sk, u8 new_state) |
a7868ea6 BE |
261 | { |
262 | switch (new_state) { | |
50bf3e22 BE |
263 | case TCP_CA_Open: |
264 | { | |
265 | struct htcp *ca = inet_csk_ca(sk); | |
266 | ca->last_cong = jiffies; | |
267 | } | |
268 | break; | |
a7868ea6 BE |
269 | case TCP_CA_CWR: |
270 | case TCP_CA_Recovery: | |
271 | case TCP_CA_Loss: | |
6687e988 | 272 | htcp_reset(inet_csk_ca(sk)); |
a7868ea6 BE |
273 | break; |
274 | } | |
275 | } | |
276 | ||
277 | static struct tcp_congestion_ops htcp = { | |
278 | .init = htcp_init, | |
279 | .ssthresh = htcp_recalc_ssthresh, | |
a7868ea6 BE |
280 | .cong_avoid = htcp_cong_avoid, |
281 | .set_state = htcp_state, | |
282 | .undo_cwnd = htcp_cwnd_undo, | |
283 | .pkts_acked = measure_achieved_throughput, | |
284 | .owner = THIS_MODULE, | |
285 | .name = "htcp", | |
286 | }; | |
287 | ||
288 | static int __init htcp_register(void) | |
289 | { | |
6687e988 | 290 | BUG_ON(sizeof(struct htcp) > ICSK_CA_PRIV_SIZE); |
a7868ea6 | 291 | BUILD_BUG_ON(BETA_MIN >= BETA_MAX); |
a7868ea6 BE |
292 | return tcp_register_congestion_control(&htcp); |
293 | } | |
294 | ||
295 | static void __exit htcp_unregister(void) | |
296 | { | |
297 | tcp_unregister_congestion_control(&htcp); | |
298 | } | |
299 | ||
300 | module_init(htcp_register); | |
301 | module_exit(htcp_unregister); | |
302 | ||
303 | MODULE_AUTHOR("Baruch Even"); | |
304 | MODULE_LICENSE("GPL"); | |
305 | MODULE_DESCRIPTION("H-TCP"); |