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