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
9 #include <linux/config.h>
11 #include <linux/module.h>
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 */
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");
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");
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 */
40 /* Bandwidth estimation */
48 static inline void htcp_reset(struct htcp
*ca
)
50 ca
->undo_ccount
= ca
->ccount
;
51 ca
->undo_maxRTT
= ca
->maxRTT
;
52 ca
->undo_old_maxB
= ca
->old_maxB
;
55 ca
->snd_cwnd_cnt2
= 0;
58 static u32
htcp_cwnd_undo(struct tcp_sock
*tp
)
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
);
67 static inline void measure_rtt(struct tcp_sock
*tp
)
69 struct htcp
*ca
= tcp_ca(tp
);
70 u32 srtt
= tp
->srtt
>>3;
72 /* keep track of minimum RTT seen so far, minRTT is zero at first */
73 if (ca
->minRTT
> srtt
|| !ca
->minRTT
)
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)
85 static void measure_achieved_throughput(struct tcp_sock
*tp
, u32 pkts_acked
)
87 struct htcp
*ca
= tcp_ca(tp
);
88 u32 now
= tcp_time_stamp
;
90 /* achieved throughput calculations */
91 if (tp
->ca_state
!= TCP_CA_Open
&& tp
->ca_state
!= TCP_CA_Disorder
) {
97 ca
->packetcount
+= pkts_acked
;
99 if (ca
->packetcount
>= tp
->snd_cwnd
- (ca
->alpha
>>7? : 1)
100 && now
- ca
->lasttime
>= ca
->minRTT
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
;
107 ca
->Bi
= (3*ca
->Bi
+ cur_Bi
)/4;
108 if (ca
->Bi
> ca
->maxB
)
110 if (ca
->minB
> ca
->maxB
)
118 static inline void htcp_beta_update(struct htcp
*ca
, u32 minRTT
, u32 maxRTT
)
120 if (use_bandwidth_switch
) {
122 u32 old_maxB
= ca
->old_maxB
;
123 ca
->old_maxB
= ca
->maxB
;
125 if (!between(5*maxB
, 4*old_maxB
, 6*old_maxB
)) {
132 if (ca
->modeswitch
&& minRTT
> max(HZ
/100, 1) && maxRTT
) {
133 ca
->beta
= (minRTT
<<7)/maxRTT
;
134 if (ca
->beta
< BETA_MIN
)
136 else if (ca
->beta
> BETA_MAX
)
144 static inline void htcp_alpha_update(struct htcp
*ca
)
146 u32 minRTT
= ca
->minRTT
;
148 u32 diff
= ca
->ccount
* minRTT
; /* time since last backoff */
152 factor
= 1+ ( 10*diff
+ ((diff
/2)*(diff
/2)/HZ
) )/HZ
;
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
;
163 ca
->alpha
= 2*factor
*((1<<7)-ca
->beta
);
165 ca
->alpha
= ALPHA_BASE
;
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
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).
176 static void htcp_param_update(struct tcp_sock
*tp
)
178 struct htcp
*ca
= tcp_ca(tp
);
179 u32 minRTT
= ca
->minRTT
;
180 u32 maxRTT
= ca
->maxRTT
;
182 htcp_beta_update(ca
, minRTT
, maxRTT
);
183 htcp_alpha_update(ca
);
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;
190 static u32
htcp_recalc_ssthresh(struct tcp_sock
*tp
)
192 struct htcp
*ca
= tcp_ca(tp
);
193 htcp_param_update(tp
);
194 return max((tp
->snd_cwnd
* ca
->beta
) >> 7, 2U);
197 static void htcp_cong_avoid(struct tcp_sock
*tp
, u32 ack
, u32 rtt
,
198 u32 in_flight
, int data_acked
)
200 struct htcp
*ca
= tcp_ca(tp
);
202 if (in_flight
< tp
->snd_cwnd
)
205 if (tp
->snd_cwnd
<= tp
->snd_ssthresh
) {
206 /* In "safe" area, increase. */
207 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
212 /* keep track of number of round-trip times since last backoff event */
213 if (ca
->snd_cwnd_cnt2
++ > tp
->snd_cwnd
) {
215 ca
->snd_cwnd_cnt2
= 0;
216 htcp_alpha_update(ca
);
219 /* In dangerous area, increase slowly.
220 * In theory this is tp->snd_cwnd += alpha / tp->snd_cwnd
222 if ((tp
->snd_cwnd_cnt
++ * ca
->alpha
)>>7 >= tp
->snd_cwnd
) {
223 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
225 tp
->snd_cwnd_cnt
= 0;
231 /* Lower bound on congestion window. */
232 static u32
htcp_min_cwnd(struct tcp_sock
*tp
)
234 return tp
->snd_ssthresh
;
238 static void htcp_init(struct tcp_sock
*tp
)
240 struct htcp
*ca
= tcp_ca(tp
);
242 memset(ca
, 0, sizeof(struct htcp
));
243 ca
->alpha
= ALPHA_BASE
;
247 static void htcp_state(struct tcp_sock
*tp
, u8 new_state
)
251 case TCP_CA_Recovery
:
253 htcp_reset(tcp_ca(tp
));
258 static struct tcp_congestion_ops htcp
= {
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
,
270 static int __init
htcp_register(void)
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
);
279 static void __exit
htcp_unregister(void)
281 tcp_unregister_congestion_control(&htcp
);
284 module_init(htcp_register
);
285 module_exit(htcp_unregister
);
287 MODULE_AUTHOR("Baruch Even");
288 MODULE_LICENSE("GPL");
289 MODULE_DESCRIPTION("H-TCP");