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. Available from:
7 * http://www.ece.rice.edu/~akuzma/Doc/akuzma/TCP-LP.pdf
10 * Aleksandar Kuzmanovic <akuzma@northwestern.edu>
12 * See http://www-ece.rice.edu/networks/TCP-LP/ for their implementation.
13 * As of 2.6.13, Linux supports pluggable congestion control algorithms.
14 * Due to the limitation of the API, we take the following changes from
15 * the original TCP-LP implementation:
16 * o We use newReno in most core CA handling. Only add some checking
18 * o Error correcting in remote HZ, therefore remote HZ will be keeped
19 * on checking and updating.
20 * o Handling calculation of One-Way-Delay (OWD) within rtt_sample, sicne
21 * OWD have a similar meaning as RTT. Also correct the buggy formular.
22 * o Handle reaction for Early Congestion Indication (ECI) within
23 * pkts_acked, as mentioned within pseudo code.
24 * o OWD is handled in relative format, where local time stamp will in
25 * tcp_time_stamp format.
27 * Port from 2.4.19 to 2.6.16 as module by:
28 * Wong Hoi Sing Edison <hswong3i@gmail.com>
29 * Hung Hing Lun <hlhung3i@gmail.com>
31 * Version: $Id: tcp_lp.c,v 1.22 2006-05-02 18:18:19 hswong3i Exp $
34 #include <linux/config.h>
35 #include <linux/module.h>
38 /* resolution of owd */
43 * @LP_VALID_RHZ: is remote HZ valid?
44 * @LP_VALID_OWD: is OWD valid?
45 * @LP_WITHIN_THR: are we within threshold?
46 * @LP_WITHIN_INF: are we within inference?
48 * TCP-LP's state flags.
49 * We create this set of state flag mainly for debugging.
52 LP_VALID_RHZ
= (1 << 0),
53 LP_VALID_OWD
= (1 << 1),
54 LP_WITHIN_THR
= (1 << 3),
55 LP_WITHIN_INF
= (1 << 4),
60 * @flag: TCP-LP state flag
61 * @sowd: smoothed OWD << 3
64 * @owd_max_rsv: resrved max owd
65 * @remote_hz: estimated remote HZ
66 * @remote_ref_time: remote reference time
67 * @local_ref_time: local reference time
68 * @last_drop: time for last active drop
69 * @inference: current inference
71 * TCP-LP's private struct.
72 * We get the idea from original TCP-LP implementation where only left those we
73 * found are really useful.
91 * Init all required variables.
92 * Clone the handling from Vegas module implementation.
94 static void tcp_lp_init(struct sock
*sk
)
96 struct lp
*lp
= inet_csk_ca(sk
);
100 lp
->owd_min
= 0xffffffff;
104 lp
->remote_ref_time
= 0;
105 lp
->local_ref_time
= 0;
113 * Implementation of cong_avoid.
114 * Will only call newReno CA when away from inference.
115 * From TCP-LP's paper, this will be handled in additive increasement.
117 static void tcp_lp_cong_avoid(struct sock
*sk
, u32 ack
, u32 rtt
, u32 in_flight
,
120 struct lp
*lp
= inet_csk_ca(sk
);
122 if (!(lp
->flag
& LP_WITHIN_INF
))
123 tcp_reno_cong_avoid(sk
, ack
, rtt
, in_flight
, flag
);
127 * tcp_lp_remote_hz_estimator
129 * Estimate remote HZ.
130 * We keep on updating the estimated value, where original TCP-LP
131 * implementation only guest it for once and use forever.
133 static u32
tcp_lp_remote_hz_estimator(struct sock
*sk
)
135 struct tcp_sock
*tp
= tcp_sk(sk
);
136 struct lp
*lp
= inet_csk_ca(sk
);
137 s64 rhz
= lp
->remote_hz
<< 6; /* remote HZ << 6 */
140 /* not yet record reference time
141 * go away!! record it before come back!! */
142 if (lp
->remote_ref_time
== 0 || lp
->local_ref_time
== 0)
145 /* we can't calc remote HZ with no different!! */
146 if (tp
->rx_opt
.rcv_tsval
== lp
->remote_ref_time
147 || tp
->rx_opt
.rcv_tsecr
== lp
->local_ref_time
)
150 m
= HZ
* (tp
->rx_opt
.rcv_tsval
-
151 lp
->remote_ref_time
) / (tp
->rx_opt
.rcv_tsecr
-
157 m
-= rhz
>> 6; /* m is now error in remote HZ est */
158 rhz
+= m
; /* 63/64 old + 1/64 new */
162 /* record time for successful remote HZ calc */
163 lp
->flag
|= LP_VALID_RHZ
;
166 /* record reference time stamp */
167 lp
->remote_ref_time
= tp
->rx_opt
.rcv_tsval
;
168 lp
->local_ref_time
= tp
->rx_opt
.rcv_tsecr
;
174 * tcp_lp_owd_calculator
176 * Calculate one way delay (in relative format).
177 * Original implement OWD as minus of remote time difference to local time
178 * difference directly. As this time difference just simply equal to RTT, when
179 * the network status is stable, remote RTT will equal to local RTT, and result
181 * It seems to be a bug and so we fixed it.
183 static u32
tcp_lp_owd_calculator(struct sock
*sk
)
185 struct tcp_sock
*tp
= tcp_sk(sk
);
186 struct lp
*lp
= inet_csk_ca(sk
);
189 lp
->remote_hz
= tcp_lp_remote_hz_estimator(sk
);
191 if (lp
->flag
& LP_VALID_RHZ
) {
193 tp
->rx_opt
.rcv_tsval
* (LP_RESOL
/ lp
->remote_hz
) -
194 tp
->rx_opt
.rcv_tsecr
* (LP_RESOL
/ HZ
);
200 lp
->flag
|= LP_VALID_OWD
;
202 lp
->flag
&= ~LP_VALID_OWD
;
210 * Implementation or rtt_sample.
211 * Will take the following action,
213 * 2. record the min/max OWD,
214 * 3. calc smoothed OWD (SOWD).
215 * Most ideas come from the original TCP-LP implementation.
217 static void tcp_lp_rtt_sample(struct sock
*sk
, u32 usrtt
)
219 struct lp
*lp
= inet_csk_ca(sk
);
220 s64 mowd
= tcp_lp_owd_calculator(sk
);
222 /* sorry that we don't have valid data */
223 if (!(lp
->flag
& LP_VALID_RHZ
) || !(lp
->flag
& LP_VALID_OWD
))
226 /* record the next min owd */
227 if (mowd
< lp
->owd_min
)
230 /* always forget the max of the max
231 * we just set owd_max as one below it */
232 if (mowd
> lp
->owd_max
) {
233 if (mowd
> lp
->owd_max_rsv
) {
234 if (lp
->owd_max_rsv
== 0)
237 lp
->owd_max
= lp
->owd_max_rsv
;
238 lp
->owd_max_rsv
= mowd
;
243 /* calc for smoothed owd */
245 mowd
-= lp
->sowd
>> 3; /* m is now error in owd est */
246 lp
->sowd
+= mowd
; /* owd = 7/8 owd + 1/8 new */
248 lp
->sowd
= mowd
<< 3; /* take the measured time be owd */
254 * Implementation of pkts_acked.
255 * Deal with active drop under Early Congestion Indication.
256 * Only drop to half and 1 will be handle, because we hope to use back
257 * newReno in increase case.
258 * We work it out by following the idea from TCP-LP's paper directly
260 static void tcp_lp_pkts_acked(struct sock
*sk
, u32 num_acked
)
262 struct tcp_sock
*tp
= tcp_sk(sk
);
263 struct lp
*lp
= inet_csk_ca(sk
);
266 if (tcp_time_stamp
> tp
->rx_opt
.rcv_tsecr
)
267 lp
->inference
= 3 * (tcp_time_stamp
- tp
->rx_opt
.rcv_tsecr
);
269 /* test if within inference */
270 if (lp
->last_drop
&& (tcp_time_stamp
- lp
->last_drop
< lp
->inference
))
271 lp
->flag
|= LP_WITHIN_INF
;
273 lp
->flag
&= ~LP_WITHIN_INF
;
275 /* test if within threshold */
277 lp
->owd_min
+ 15 * (lp
->owd_max
- lp
->owd_min
) / 100)
278 lp
->flag
|= LP_WITHIN_THR
;
280 lp
->flag
&= ~LP_WITHIN_THR
;
282 pr_debug("TCP-LP: %05o|%5u|%5u|%15u|%15u|%15u\n", lp
->flag
,
283 tp
->snd_cwnd
, lp
->remote_hz
, lp
->owd_min
, lp
->owd_max
,
286 if (lp
->flag
& LP_WITHIN_THR
)
289 /* FIXME: try to reset owd_min and owd_max here
290 * so decrease the chance the min/max is no longer suitable
291 * and will usually within threshold when whithin inference */
292 lp
->owd_min
= lp
->sowd
>> 3;
293 lp
->owd_max
= lp
->sowd
>> 2;
294 lp
->owd_max_rsv
= lp
->sowd
>> 2;
296 /* happened within inference
297 * drop snd_cwnd into 1 */
298 if (lp
->flag
& LP_WITHIN_INF
)
301 /* happened after inference
302 * cut snd_cwnd into half */
304 tp
->snd_cwnd
= max(tp
->snd_cwnd
>> 1U, 1U);
306 /* record this drop time */
307 lp
->last_drop
= tcp_time_stamp
;
310 static struct tcp_congestion_ops tcp_lp
= {
312 .ssthresh
= tcp_reno_ssthresh
,
313 .cong_avoid
= tcp_lp_cong_avoid
,
314 .min_cwnd
= tcp_reno_min_cwnd
,
315 .rtt_sample
= tcp_lp_rtt_sample
,
316 .pkts_acked
= tcp_lp_pkts_acked
,
318 .owner
= THIS_MODULE
,
322 static int __init
tcp_lp_register(void)
324 BUG_ON(sizeof(struct lp
) > ICSK_CA_PRIV_SIZE
);
325 return tcp_register_congestion_control(&tcp_lp
);
328 static void __exit
tcp_lp_unregister(void)
330 tcp_unregister_congestion_control(&tcp_lp
);
333 module_init(tcp_lp_register
);
334 module_exit(tcp_lp_unregister
);
336 MODULE_AUTHOR("Wong Hoi Sing Edison, Hung Hing Lun");
337 MODULE_LICENSE("GPL");
338 MODULE_DESCRIPTION("TCP Low Priority");