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/config.h>
39 #include <linux/module.h>
42 /* resolution of owd */
47 * @LP_VALID_RHZ: is remote HZ valid?
48 * @LP_VALID_OWD: is OWD valid?
49 * @LP_WITHIN_THR: are we within threshold?
50 * @LP_WITHIN_INF: are we within inference?
52 * TCP-LP's state flags.
53 * We create this set of state flag mainly for debugging.
56 LP_VALID_RHZ
= (1 << 0),
57 LP_VALID_OWD
= (1 << 1),
58 LP_WITHIN_THR
= (1 << 3),
59 LP_WITHIN_INF
= (1 << 4),
64 * @flag: TCP-LP state flag
65 * @sowd: smoothed OWD << 3
68 * @owd_max_rsv: resrved max owd
69 * @remote_hz: estimated remote HZ
70 * @remote_ref_time: remote reference time
71 * @local_ref_time: local reference time
72 * @last_drop: time for last active drop
73 * @inference: current inference
75 * TCP-LP's private struct.
76 * We get the idea from original TCP-LP implementation where only left those we
77 * found are really useful.
95 * Init all required variables.
96 * Clone the handling from Vegas module implementation.
98 static void tcp_lp_init(struct sock
*sk
)
100 struct lp
*lp
= inet_csk_ca(sk
);
104 lp
->owd_min
= 0xffffffff;
108 lp
->remote_ref_time
= 0;
109 lp
->local_ref_time
= 0;
117 * Implementation of cong_avoid.
118 * Will only call newReno CA when away from inference.
119 * From TCP-LP's paper, this will be handled in additive increasement.
121 static void tcp_lp_cong_avoid(struct sock
*sk
, u32 ack
, u32 rtt
, u32 in_flight
,
124 struct lp
*lp
= inet_csk_ca(sk
);
126 if (!(lp
->flag
& LP_WITHIN_INF
))
127 tcp_reno_cong_avoid(sk
, ack
, rtt
, in_flight
, flag
);
131 * tcp_lp_remote_hz_estimator
133 * Estimate remote HZ.
134 * We keep on updating the estimated value, where original TCP-LP
135 * implementation only guest it for once and use forever.
137 static u32
tcp_lp_remote_hz_estimator(struct sock
*sk
)
139 struct tcp_sock
*tp
= tcp_sk(sk
);
140 struct lp
*lp
= inet_csk_ca(sk
);
141 s64 rhz
= lp
->remote_hz
<< 6; /* remote HZ << 6 */
144 /* not yet record reference time
145 * go away!! record it before come back!! */
146 if (lp
->remote_ref_time
== 0 || lp
->local_ref_time
== 0)
149 /* we can't calc remote HZ with no different!! */
150 if (tp
->rx_opt
.rcv_tsval
== lp
->remote_ref_time
151 || tp
->rx_opt
.rcv_tsecr
== lp
->local_ref_time
)
154 m
= HZ
* (tp
->rx_opt
.rcv_tsval
-
155 lp
->remote_ref_time
) / (tp
->rx_opt
.rcv_tsecr
-
161 m
-= rhz
>> 6; /* m is now error in remote HZ est */
162 rhz
+= m
; /* 63/64 old + 1/64 new */
167 /* record time for successful remote HZ calc */
169 lp
->flag
|= LP_VALID_RHZ
;
171 lp
->flag
&= ~LP_VALID_RHZ
;
173 /* record reference time stamp */
174 lp
->remote_ref_time
= tp
->rx_opt
.rcv_tsval
;
175 lp
->local_ref_time
= tp
->rx_opt
.rcv_tsecr
;
181 * tcp_lp_owd_calculator
183 * Calculate one way delay (in relative format).
184 * Original implement OWD as minus of remote time difference to local time
185 * difference directly. As this time difference just simply equal to RTT, when
186 * the network status is stable, remote RTT will equal to local RTT, and result
188 * It seems to be a bug and so we fixed it.
190 static u32
tcp_lp_owd_calculator(struct sock
*sk
)
192 struct tcp_sock
*tp
= tcp_sk(sk
);
193 struct lp
*lp
= inet_csk_ca(sk
);
196 lp
->remote_hz
= tcp_lp_remote_hz_estimator(sk
);
198 if (lp
->flag
& LP_VALID_RHZ
) {
200 tp
->rx_opt
.rcv_tsval
* (LP_RESOL
/ lp
->remote_hz
) -
201 tp
->rx_opt
.rcv_tsecr
* (LP_RESOL
/ HZ
);
207 lp
->flag
|= LP_VALID_OWD
;
209 lp
->flag
&= ~LP_VALID_OWD
;
217 * Implementation or rtt_sample.
218 * Will take the following action,
220 * 2. record the min/max OWD,
221 * 3. calc smoothed OWD (SOWD).
222 * Most ideas come from the original TCP-LP implementation.
224 static void tcp_lp_rtt_sample(struct sock
*sk
, u32 usrtt
)
226 struct lp
*lp
= inet_csk_ca(sk
);
227 s64 mowd
= tcp_lp_owd_calculator(sk
);
229 /* sorry that we don't have valid data */
230 if (!(lp
->flag
& LP_VALID_RHZ
) || !(lp
->flag
& LP_VALID_OWD
))
233 /* record the next min owd */
234 if (mowd
< lp
->owd_min
)
237 /* always forget the max of the max
238 * we just set owd_max as one below it */
239 if (mowd
> lp
->owd_max
) {
240 if (mowd
> lp
->owd_max_rsv
) {
241 if (lp
->owd_max_rsv
== 0)
244 lp
->owd_max
= lp
->owd_max_rsv
;
245 lp
->owd_max_rsv
= mowd
;
250 /* calc for smoothed owd */
252 mowd
-= lp
->sowd
>> 3; /* m is now error in owd est */
253 lp
->sowd
+= mowd
; /* owd = 7/8 owd + 1/8 new */
255 lp
->sowd
= mowd
<< 3; /* take the measured time be owd */
261 * Implementation of pkts_acked.
262 * Deal with active drop under Early Congestion Indication.
263 * Only drop to half and 1 will be handle, because we hope to use back
264 * newReno in increase case.
265 * We work it out by following the idea from TCP-LP's paper directly
267 static void tcp_lp_pkts_acked(struct sock
*sk
, u32 num_acked
)
269 struct tcp_sock
*tp
= tcp_sk(sk
);
270 struct lp
*lp
= inet_csk_ca(sk
);
273 if (tcp_time_stamp
> tp
->rx_opt
.rcv_tsecr
)
274 lp
->inference
= 3 * (tcp_time_stamp
- tp
->rx_opt
.rcv_tsecr
);
276 /* test if within inference */
277 if (lp
->last_drop
&& (tcp_time_stamp
- lp
->last_drop
< lp
->inference
))
278 lp
->flag
|= LP_WITHIN_INF
;
280 lp
->flag
&= ~LP_WITHIN_INF
;
282 /* test if within threshold */
284 lp
->owd_min
+ 15 * (lp
->owd_max
- lp
->owd_min
) / 100)
285 lp
->flag
|= LP_WITHIN_THR
;
287 lp
->flag
&= ~LP_WITHIN_THR
;
289 pr_debug("TCP-LP: %05o|%5u|%5u|%15u|%15u|%15u\n", lp
->flag
,
290 tp
->snd_cwnd
, lp
->remote_hz
, lp
->owd_min
, lp
->owd_max
,
293 if (lp
->flag
& LP_WITHIN_THR
)
296 /* FIXME: try to reset owd_min and owd_max here
297 * so decrease the chance the min/max is no longer suitable
298 * and will usually within threshold when whithin inference */
299 lp
->owd_min
= lp
->sowd
>> 3;
300 lp
->owd_max
= lp
->sowd
>> 2;
301 lp
->owd_max_rsv
= lp
->sowd
>> 2;
303 /* happened within inference
304 * drop snd_cwnd into 1 */
305 if (lp
->flag
& LP_WITHIN_INF
)
308 /* happened after inference
309 * cut snd_cwnd into half */
311 tp
->snd_cwnd
= max(tp
->snd_cwnd
>> 1U, 1U);
313 /* record this drop time */
314 lp
->last_drop
= tcp_time_stamp
;
317 static struct tcp_congestion_ops tcp_lp
= {
319 .ssthresh
= tcp_reno_ssthresh
,
320 .cong_avoid
= tcp_lp_cong_avoid
,
321 .min_cwnd
= tcp_reno_min_cwnd
,
322 .rtt_sample
= tcp_lp_rtt_sample
,
323 .pkts_acked
= tcp_lp_pkts_acked
,
325 .owner
= THIS_MODULE
,
329 static int __init
tcp_lp_register(void)
331 BUG_ON(sizeof(struct lp
) > ICSK_CA_PRIV_SIZE
);
332 return tcp_register_congestion_control(&tcp_lp
);
335 static void __exit
tcp_lp_unregister(void)
337 tcp_unregister_congestion_control(&tcp_lp
);
340 module_init(tcp_lp_register
);
341 module_exit(tcp_lp_unregister
);
343 MODULE_AUTHOR("Wong Hoi Sing Edison, Hung Hing Lun Mike");
344 MODULE_LICENSE("GPL");
345 MODULE_DESCRIPTION("TCP Low Priority");