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
10 #include <linux/module.h>
13 #define ALPHA_BASE (1<<7) /* 1.0 with shift << 7 */
14 #define BETA_MIN (1<<6) /* 0.5 with shift << 7 */
15 #define BETA_MAX 102 /* 0.8 with shift << 7 */
17 static int use_rtt_scaling __read_mostly
= 1;
18 module_param(use_rtt_scaling
, int, 0644);
19 MODULE_PARM_DESC(use_rtt_scaling
, "turn on/off RTT scaling");
21 static int use_bandwidth_switch __read_mostly
= 1;
22 module_param(use_bandwidth_switch
, int, 0644);
23 MODULE_PARM_DESC(use_bandwidth_switch
, "turn on/off bandwidth switcher");
26 u32 alpha
; /* Fixed point arith, << 7 */
27 u8 beta
; /* Fixed point arith, << 7 */
28 u8 modeswitch
; /* Delay modeswitch
29 until we had at least one congestion event */
34 u32 last_cong
; /* Time since last congestion event end */
40 /* Bandwidth estimation */
48 static inline u32
htcp_cong_time(const struct htcp
*ca
)
50 return jiffies
- ca
->last_cong
;
53 static inline u32
htcp_ccount(const struct htcp
*ca
)
55 return htcp_cong_time(ca
) / ca
->minRTT
;
58 static inline void htcp_reset(struct htcp
*ca
)
60 ca
->undo_last_cong
= ca
->last_cong
;
61 ca
->undo_maxRTT
= ca
->maxRTT
;
62 ca
->undo_old_maxB
= ca
->old_maxB
;
64 ca
->last_cong
= jiffies
;
67 static u32
htcp_cwnd_undo(struct sock
*sk
)
69 const struct tcp_sock
*tp
= tcp_sk(sk
);
70 struct htcp
*ca
= inet_csk_ca(sk
);
72 if (ca
->undo_last_cong
) {
73 ca
->last_cong
= ca
->undo_last_cong
;
74 ca
->maxRTT
= ca
->undo_maxRTT
;
75 ca
->old_maxB
= ca
->undo_old_maxB
;
76 ca
->undo_last_cong
= 0;
79 return max(tp
->snd_cwnd
, (tp
->snd_ssthresh
<< 7) / ca
->beta
);
82 static inline void measure_rtt(struct sock
*sk
, u32 srtt
)
84 const struct inet_connection_sock
*icsk
= inet_csk(sk
);
85 struct htcp
*ca
= inet_csk_ca(sk
);
87 /* keep track of minimum RTT seen so far, minRTT is zero at first */
88 if (ca
->minRTT
> srtt
|| !ca
->minRTT
)
92 if (icsk
->icsk_ca_state
== TCP_CA_Open
) {
93 if (ca
->maxRTT
< ca
->minRTT
)
94 ca
->maxRTT
= ca
->minRTT
;
95 if (ca
->maxRTT
< srtt
&&
96 srtt
<= ca
->maxRTT
+ msecs_to_jiffies(20))
101 static void measure_achieved_throughput(struct sock
*sk
, u32 pkts_acked
, s32 rtt
)
103 const struct inet_connection_sock
*icsk
= inet_csk(sk
);
104 const struct tcp_sock
*tp
= tcp_sk(sk
);
105 struct htcp
*ca
= inet_csk_ca(sk
);
106 u32 now
= tcp_time_stamp
;
108 if (icsk
->icsk_ca_state
== TCP_CA_Open
)
109 ca
->pkts_acked
= pkts_acked
;
112 measure_rtt(sk
, usecs_to_jiffies(rtt
));
114 if (!use_bandwidth_switch
)
117 /* achieved throughput calculations */
118 if (!((1 << icsk
->icsk_ca_state
) & (TCPF_CA_Open
| TCPF_CA_Disorder
))) {
124 ca
->packetcount
+= pkts_acked
;
126 if (ca
->packetcount
>= tp
->snd_cwnd
- (ca
->alpha
>> 7 ? : 1) &&
127 now
- ca
->lasttime
>= ca
->minRTT
&&
129 __u32 cur_Bi
= ca
->packetcount
* HZ
/ (now
- ca
->lasttime
);
131 if (htcp_ccount(ca
) <= 3) {
132 /* just after backoff */
133 ca
->minB
= ca
->maxB
= ca
->Bi
= cur_Bi
;
135 ca
->Bi
= (3 * ca
->Bi
+ cur_Bi
) / 4;
136 if (ca
->Bi
> ca
->maxB
)
138 if (ca
->minB
> ca
->maxB
)
146 static inline void htcp_beta_update(struct htcp
*ca
, u32 minRTT
, u32 maxRTT
)
148 if (use_bandwidth_switch
) {
150 u32 old_maxB
= ca
->old_maxB
;
151 ca
->old_maxB
= ca
->maxB
;
153 if (!between(5 * maxB
, 4 * old_maxB
, 6 * old_maxB
)) {
160 if (ca
->modeswitch
&& minRTT
> msecs_to_jiffies(10) && maxRTT
) {
161 ca
->beta
= (minRTT
<< 7) / maxRTT
;
162 if (ca
->beta
< BETA_MIN
)
164 else if (ca
->beta
> BETA_MAX
)
172 static inline void htcp_alpha_update(struct htcp
*ca
)
174 u32 minRTT
= ca
->minRTT
;
176 u32 diff
= htcp_cong_time(ca
);
180 factor
= 1 + (10 * diff
+ ((diff
/ 2) * (diff
/ 2) / HZ
)) / HZ
;
183 if (use_rtt_scaling
&& minRTT
) {
184 u32 scale
= (HZ
<< 3) / (10 * minRTT
);
186 /* clamping ratio to interval [0.5,10]<<3 */
187 scale
= min(max(scale
, 1U << 2), 10U << 3);
188 factor
= (factor
<< 3) / scale
;
193 ca
->alpha
= 2 * factor
* ((1 << 7) - ca
->beta
);
195 ca
->alpha
= ALPHA_BASE
;
199 * After we have the rtt data to calculate beta, we'd still prefer to wait one
200 * rtt before we adjust our beta to ensure we are working from a consistent
203 * This function should be called when we hit a congestion event since only at
204 * that point do we really have a real sense of maxRTT (the queues en route
205 * were getting just too full now).
207 static void htcp_param_update(struct sock
*sk
)
209 struct htcp
*ca
= inet_csk_ca(sk
);
210 u32 minRTT
= ca
->minRTT
;
211 u32 maxRTT
= ca
->maxRTT
;
213 htcp_beta_update(ca
, minRTT
, maxRTT
);
214 htcp_alpha_update(ca
);
216 /* add slowly fading memory for maxRTT to accommodate routing changes */
217 if (minRTT
> 0 && maxRTT
> minRTT
)
218 ca
->maxRTT
= minRTT
+ ((maxRTT
- minRTT
) * 95) / 100;
221 static u32
htcp_recalc_ssthresh(struct sock
*sk
)
223 const struct tcp_sock
*tp
= tcp_sk(sk
);
224 const struct htcp
*ca
= inet_csk_ca(sk
);
226 htcp_param_update(sk
);
227 return max((tp
->snd_cwnd
* ca
->beta
) >> 7, 2U);
230 static void htcp_cong_avoid(struct sock
*sk
, u32 ack
, u32 acked
, u32 in_flight
)
232 struct tcp_sock
*tp
= tcp_sk(sk
);
233 struct htcp
*ca
= inet_csk_ca(sk
);
235 if (!tcp_is_cwnd_limited(sk
, in_flight
))
238 if (tp
->snd_cwnd
<= tp
->snd_ssthresh
)
239 tcp_slow_start(tp
, acked
);
241 /* In dangerous area, increase slowly.
242 * In theory this is tp->snd_cwnd += alpha / tp->snd_cwnd
244 if ((tp
->snd_cwnd_cnt
* ca
->alpha
)>>7 >= tp
->snd_cwnd
) {
245 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
247 tp
->snd_cwnd_cnt
= 0;
248 htcp_alpha_update(ca
);
250 tp
->snd_cwnd_cnt
+= ca
->pkts_acked
;
256 static void htcp_init(struct sock
*sk
)
258 struct htcp
*ca
= inet_csk_ca(sk
);
260 memset(ca
, 0, sizeof(struct htcp
));
261 ca
->alpha
= ALPHA_BASE
;
264 ca
->last_cong
= jiffies
;
267 static void htcp_state(struct sock
*sk
, u8 new_state
)
272 struct htcp
*ca
= inet_csk_ca(sk
);
273 if (ca
->undo_last_cong
) {
274 ca
->last_cong
= jiffies
;
275 ca
->undo_last_cong
= 0;
280 case TCP_CA_Recovery
:
282 htcp_reset(inet_csk_ca(sk
));
287 static struct tcp_congestion_ops htcp __read_mostly
= {
289 .ssthresh
= htcp_recalc_ssthresh
,
290 .cong_avoid
= htcp_cong_avoid
,
291 .set_state
= htcp_state
,
292 .undo_cwnd
= htcp_cwnd_undo
,
293 .pkts_acked
= measure_achieved_throughput
,
294 .owner
= THIS_MODULE
,
298 static int __init
htcp_register(void)
300 BUILD_BUG_ON(sizeof(struct htcp
) > ICSK_CA_PRIV_SIZE
);
301 BUILD_BUG_ON(BETA_MIN
>= BETA_MAX
);
302 return tcp_register_congestion_control(&htcp
);
305 static void __exit
htcp_unregister(void)
307 tcp_unregister_congestion_control(&htcp
);
310 module_init(htcp_register
);
311 module_exit(htcp_unregister
);
313 MODULE_AUTHOR("Baruch Even");
314 MODULE_LICENSE("GPL");
315 MODULE_DESCRIPTION("H-TCP");