2 * TCP Low Priority (TCP-LP)
4 * TCP Low Priority is a distributed algorithm whose goal is to utilize only
5 * the excess network bandwidth as compared to the ``fair share`` of
6 * bandwidth as targeted by TCP.
8 * As of 2.6.13, Linux supports pluggable congestion control algorithms.
9 * Due to the limitation of the API, we take the following changes from
10 * the original TCP-LP implementation:
11 * o We use newReno in most core CA handling. Only add some checking
13 * o Error correcting in remote HZ, therefore remote HZ will be keeped
14 * on checking and updating.
15 * o Handling calculation of One-Way-Delay (OWD) within rtt_sample, sicne
16 * OWD have a similar meaning as RTT. Also correct the buggy formular.
17 * o Handle reaction for Early Congestion Indication (ECI) within
18 * pkts_acked, as mentioned within pseudo code.
19 * o OWD is handled in relative format, where local time stamp will in
20 * tcp_time_stamp format.
23 * Aleksandar Kuzmanovic <akuzma@northwestern.edu>
25 * http://www.ece.rice.edu/~akuzma/Doc/akuzma/TCP-LP.pdf
26 * Original implementation for 2.4.19:
27 * http://www-ece.rice.edu/networks/TCP-LP/
29 * 2.6.x module Authors:
30 * Wong Hoi Sing, Edison <hswong3i@gmail.com>
31 * Hung Hing Lun, Mike <hlhung3i@gmail.com>
32 * SourceForge project page:
33 * http://tcp-lp-mod.sourceforge.net/
35 * Version: $Id: tcp_lp.c,v 1.24 2006/09/05 20:22:53 hswong3i Exp $
38 #include <linux/module.h>
41 /* resolution of owd */
46 * @LP_VALID_RHZ: is remote HZ valid?
47 * @LP_VALID_OWD: is OWD valid?
48 * @LP_WITHIN_THR: are we within threshold?
49 * @LP_WITHIN_INF: are we within inference?
51 * TCP-LP's state flags.
52 * We create this set of state flag mainly for debugging.
55 LP_VALID_RHZ
= (1 << 0),
56 LP_VALID_OWD
= (1 << 1),
57 LP_WITHIN_THR
= (1 << 3),
58 LP_WITHIN_INF
= (1 << 4),
63 * @flag: TCP-LP state flag
64 * @sowd: smoothed OWD << 3
67 * @owd_max_rsv: resrved max owd
68 * @remote_hz: estimated remote HZ
69 * @remote_ref_time: remote reference time
70 * @local_ref_time: local reference time
71 * @last_drop: time for last active drop
72 * @inference: current inference
74 * TCP-LP's private struct.
75 * We get the idea from original TCP-LP implementation where only left those we
76 * found are really useful.
94 * Init all required variables.
95 * Clone the handling from Vegas module implementation.
97 static void tcp_lp_init(struct sock
*sk
)
99 struct lp
*lp
= inet_csk_ca(sk
);
103 lp
->owd_min
= 0xffffffff;
107 lp
->remote_ref_time
= 0;
108 lp
->local_ref_time
= 0;
116 * Implementation of cong_avoid.
117 * Will only call newReno CA when away from inference.
118 * From TCP-LP's paper, this will be handled in additive increasement.
120 static void tcp_lp_cong_avoid(struct sock
*sk
, u32 ack
, u32 rtt
, u32 in_flight
,
123 struct lp
*lp
= inet_csk_ca(sk
);
125 if (!(lp
->flag
& LP_WITHIN_INF
))
126 tcp_reno_cong_avoid(sk
, ack
, rtt
, in_flight
, flag
);
130 * tcp_lp_remote_hz_estimator
132 * Estimate remote HZ.
133 * We keep on updating the estimated value, where original TCP-LP
134 * implementation only guest it for once and use forever.
136 static u32
tcp_lp_remote_hz_estimator(struct sock
*sk
)
138 struct tcp_sock
*tp
= tcp_sk(sk
);
139 struct lp
*lp
= inet_csk_ca(sk
);
140 s64 rhz
= lp
->remote_hz
<< 6; /* remote HZ << 6 */
143 /* not yet record reference time
144 * go away!! record it before come back!! */
145 if (lp
->remote_ref_time
== 0 || lp
->local_ref_time
== 0)
148 /* we can't calc remote HZ with no different!! */
149 if (tp
->rx_opt
.rcv_tsval
== lp
->remote_ref_time
150 || tp
->rx_opt
.rcv_tsecr
== lp
->local_ref_time
)
153 m
= HZ
* (tp
->rx_opt
.rcv_tsval
-
154 lp
->remote_ref_time
) / (tp
->rx_opt
.rcv_tsecr
-
160 m
-= rhz
>> 6; /* m is now error in remote HZ est */
161 rhz
+= m
; /* 63/64 old + 1/64 new */
166 /* record time for successful remote HZ calc */
168 lp
->flag
|= LP_VALID_RHZ
;
170 lp
->flag
&= ~LP_VALID_RHZ
;
172 /* record reference time stamp */
173 lp
->remote_ref_time
= tp
->rx_opt
.rcv_tsval
;
174 lp
->local_ref_time
= tp
->rx_opt
.rcv_tsecr
;
180 * tcp_lp_owd_calculator
182 * Calculate one way delay (in relative format).
183 * Original implement OWD as minus of remote time difference to local time
184 * difference directly. As this time difference just simply equal to RTT, when
185 * the network status is stable, remote RTT will equal to local RTT, and result
187 * It seems to be a bug and so we fixed it.
189 static u32
tcp_lp_owd_calculator(struct sock
*sk
)
191 struct tcp_sock
*tp
= tcp_sk(sk
);
192 struct lp
*lp
= inet_csk_ca(sk
);
195 lp
->remote_hz
= tcp_lp_remote_hz_estimator(sk
);
197 if (lp
->flag
& LP_VALID_RHZ
) {
199 tp
->rx_opt
.rcv_tsval
* (LP_RESOL
/ lp
->remote_hz
) -
200 tp
->rx_opt
.rcv_tsecr
* (LP_RESOL
/ HZ
);
206 lp
->flag
|= LP_VALID_OWD
;
208 lp
->flag
&= ~LP_VALID_OWD
;
216 * Implementation or rtt_sample.
217 * Will take the following action,
219 * 2. record the min/max OWD,
220 * 3. calc smoothed OWD (SOWD).
221 * Most ideas come from the original TCP-LP implementation.
223 static void tcp_lp_rtt_sample(struct sock
*sk
, u32 usrtt
)
225 struct lp
*lp
= inet_csk_ca(sk
);
226 s64 mowd
= tcp_lp_owd_calculator(sk
);
228 /* sorry that we don't have valid data */
229 if (!(lp
->flag
& LP_VALID_RHZ
) || !(lp
->flag
& LP_VALID_OWD
))
232 /* record the next min owd */
233 if (mowd
< lp
->owd_min
)
236 /* always forget the max of the max
237 * we just set owd_max as one below it */
238 if (mowd
> lp
->owd_max
) {
239 if (mowd
> lp
->owd_max_rsv
) {
240 if (lp
->owd_max_rsv
== 0)
243 lp
->owd_max
= lp
->owd_max_rsv
;
244 lp
->owd_max_rsv
= mowd
;
249 /* calc for smoothed owd */
251 mowd
-= lp
->sowd
>> 3; /* m is now error in owd est */
252 lp
->sowd
+= mowd
; /* owd = 7/8 owd + 1/8 new */
254 lp
->sowd
= mowd
<< 3; /* take the measured time be owd */
260 * Implementation of pkts_acked.
261 * Deal with active drop under Early Congestion Indication.
262 * Only drop to half and 1 will be handle, because we hope to use back
263 * newReno in increase case.
264 * We work it out by following the idea from TCP-LP's paper directly
266 static void tcp_lp_pkts_acked(struct sock
*sk
, u32 num_acked
)
268 struct tcp_sock
*tp
= tcp_sk(sk
);
269 struct lp
*lp
= inet_csk_ca(sk
);
272 if (tcp_time_stamp
> tp
->rx_opt
.rcv_tsecr
)
273 lp
->inference
= 3 * (tcp_time_stamp
- tp
->rx_opt
.rcv_tsecr
);
275 /* test if within inference */
276 if (lp
->last_drop
&& (tcp_time_stamp
- lp
->last_drop
< lp
->inference
))
277 lp
->flag
|= LP_WITHIN_INF
;
279 lp
->flag
&= ~LP_WITHIN_INF
;
281 /* test if within threshold */
283 lp
->owd_min
+ 15 * (lp
->owd_max
- lp
->owd_min
) / 100)
284 lp
->flag
|= LP_WITHIN_THR
;
286 lp
->flag
&= ~LP_WITHIN_THR
;
288 pr_debug("TCP-LP: %05o|%5u|%5u|%15u|%15u|%15u\n", lp
->flag
,
289 tp
->snd_cwnd
, lp
->remote_hz
, lp
->owd_min
, lp
->owd_max
,
292 if (lp
->flag
& LP_WITHIN_THR
)
295 /* FIXME: try to reset owd_min and owd_max here
296 * so decrease the chance the min/max is no longer suitable
297 * and will usually within threshold when whithin inference */
298 lp
->owd_min
= lp
->sowd
>> 3;
299 lp
->owd_max
= lp
->sowd
>> 2;
300 lp
->owd_max_rsv
= lp
->sowd
>> 2;
302 /* happened within inference
303 * drop snd_cwnd into 1 */
304 if (lp
->flag
& LP_WITHIN_INF
)
307 /* happened after inference
308 * cut snd_cwnd into half */
310 tp
->snd_cwnd
= max(tp
->snd_cwnd
>> 1U, 1U);
312 /* record this drop time */
313 lp
->last_drop
= tcp_time_stamp
;
316 static struct tcp_congestion_ops tcp_lp
= {
318 .ssthresh
= tcp_reno_ssthresh
,
319 .cong_avoid
= tcp_lp_cong_avoid
,
320 .min_cwnd
= tcp_reno_min_cwnd
,
321 .rtt_sample
= tcp_lp_rtt_sample
,
322 .pkts_acked
= tcp_lp_pkts_acked
,
324 .owner
= THIS_MODULE
,
328 static int __init
tcp_lp_register(void)
330 BUILD_BUG_ON(sizeof(struct lp
) > ICSK_CA_PRIV_SIZE
);
331 return tcp_register_congestion_control(&tcp_lp
);
334 static void __exit
tcp_lp_unregister(void)
336 tcp_unregister_congestion_control(&tcp_lp
);
339 module_init(tcp_lp_register
);
340 module_exit(tcp_lp_unregister
);
342 MODULE_AUTHOR("Wong Hoi Sing Edison, Hung Hing Lun Mike");
343 MODULE_LICENSE("GPL");
344 MODULE_DESCRIPTION("TCP Low Priority");