tcp_lp.c 8.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342
  1. /*
  2. * TCP Low Priority (TCP-LP)
  3. *
  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.
  7. *
  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
  12. * within cong_avoid.
  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.
  21. *
  22. * Original Author:
  23. * Aleksandar Kuzmanovic <akuzma@northwestern.edu>
  24. * Available from:
  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/
  28. *
  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/
  34. */
  35. #include <linux/module.h>
  36. #include <net/tcp.h>
  37. /* resolution of owd */
  38. #define LP_RESOL 1000
  39. /**
  40. * enum tcp_lp_state
  41. * @LP_VALID_RHZ: is remote HZ valid?
  42. * @LP_VALID_OWD: is OWD valid?
  43. * @LP_WITHIN_THR: are we within threshold?
  44. * @LP_WITHIN_INF: are we within inference?
  45. *
  46. * TCP-LP's state flags.
  47. * We create this set of state flag mainly for debugging.
  48. */
  49. enum tcp_lp_state {
  50. LP_VALID_RHZ = (1 << 0),
  51. LP_VALID_OWD = (1 << 1),
  52. LP_WITHIN_THR = (1 << 3),
  53. LP_WITHIN_INF = (1 << 4),
  54. };
  55. /**
  56. * struct lp
  57. * @flag: TCP-LP state flag
  58. * @sowd: smoothed OWD << 3
  59. * @owd_min: min OWD
  60. * @owd_max: max OWD
  61. * @owd_max_rsv: resrved max owd
  62. * @remote_hz: estimated remote HZ
  63. * @remote_ref_time: remote reference time
  64. * @local_ref_time: local reference time
  65. * @last_drop: time for last active drop
  66. * @inference: current inference
  67. *
  68. * TCP-LP's private struct.
  69. * We get the idea from original TCP-LP implementation where only left those we
  70. * found are really useful.
  71. */
  72. struct lp {
  73. u32 flag;
  74. u32 sowd;
  75. u32 owd_min;
  76. u32 owd_max;
  77. u32 owd_max_rsv;
  78. u32 remote_hz;
  79. u32 remote_ref_time;
  80. u32 local_ref_time;
  81. u32 last_drop;
  82. u32 inference;
  83. };
  84. /**
  85. * tcp_lp_init
  86. *
  87. * Init all required variables.
  88. * Clone the handling from Vegas module implementation.
  89. */
  90. static void tcp_lp_init(struct sock *sk)
  91. {
  92. struct lp *lp = inet_csk_ca(sk);
  93. lp->flag = 0;
  94. lp->sowd = 0;
  95. lp->owd_min = 0xffffffff;
  96. lp->owd_max = 0;
  97. lp->owd_max_rsv = 0;
  98. lp->remote_hz = 0;
  99. lp->remote_ref_time = 0;
  100. lp->local_ref_time = 0;
  101. lp->last_drop = 0;
  102. lp->inference = 0;
  103. }
  104. /**
  105. * tcp_lp_cong_avoid
  106. *
  107. * Implementation of cong_avoid.
  108. * Will only call newReno CA when away from inference.
  109. * From TCP-LP's paper, this will be handled in additive increasement.
  110. */
  111. static void tcp_lp_cong_avoid(struct sock *sk, u32 ack, u32 rtt, u32 in_flight,
  112. int flag)
  113. {
  114. struct lp *lp = inet_csk_ca(sk);
  115. if (!(lp->flag & LP_WITHIN_INF))
  116. tcp_reno_cong_avoid(sk, ack, rtt, in_flight, flag);
  117. }
  118. /**
  119. * tcp_lp_remote_hz_estimator
  120. *
  121. * Estimate remote HZ.
  122. * We keep on updating the estimated value, where original TCP-LP
  123. * implementation only guest it for once and use forever.
  124. */
  125. static u32 tcp_lp_remote_hz_estimator(struct sock *sk)
  126. {
  127. struct tcp_sock *tp = tcp_sk(sk);
  128. struct lp *lp = inet_csk_ca(sk);
  129. s64 rhz = lp->remote_hz << 6; /* remote HZ << 6 */
  130. s64 m = 0;
  131. /* not yet record reference time
  132. * go away!! record it before come back!! */
  133. if (lp->remote_ref_time == 0 || lp->local_ref_time == 0)
  134. goto out;
  135. /* we can't calc remote HZ with no different!! */
  136. if (tp->rx_opt.rcv_tsval == lp->remote_ref_time
  137. || tp->rx_opt.rcv_tsecr == lp->local_ref_time)
  138. goto out;
  139. m = HZ * (tp->rx_opt.rcv_tsval -
  140. lp->remote_ref_time) / (tp->rx_opt.rcv_tsecr -
  141. lp->local_ref_time);
  142. if (m < 0)
  143. m = -m;
  144. if (rhz > 0) {
  145. m -= rhz >> 6; /* m is now error in remote HZ est */
  146. rhz += m; /* 63/64 old + 1/64 new */
  147. } else
  148. rhz = m << 6;
  149. out:
  150. /* record time for successful remote HZ calc */
  151. if ((rhz >> 6) > 0)
  152. lp->flag |= LP_VALID_RHZ;
  153. else
  154. lp->flag &= ~LP_VALID_RHZ;
  155. /* record reference time stamp */
  156. lp->remote_ref_time = tp->rx_opt.rcv_tsval;
  157. lp->local_ref_time = tp->rx_opt.rcv_tsecr;
  158. return rhz >> 6;
  159. }
  160. /**
  161. * tcp_lp_owd_calculator
  162. *
  163. * Calculate one way delay (in relative format).
  164. * Original implement OWD as minus of remote time difference to local time
  165. * difference directly. As this time difference just simply equal to RTT, when
  166. * the network status is stable, remote RTT will equal to local RTT, and result
  167. * OWD into zero.
  168. * It seems to be a bug and so we fixed it.
  169. */
  170. static u32 tcp_lp_owd_calculator(struct sock *sk)
  171. {
  172. struct tcp_sock *tp = tcp_sk(sk);
  173. struct lp *lp = inet_csk_ca(sk);
  174. s64 owd = 0;
  175. lp->remote_hz = tcp_lp_remote_hz_estimator(sk);
  176. if (lp->flag & LP_VALID_RHZ) {
  177. owd =
  178. tp->rx_opt.rcv_tsval * (LP_RESOL / lp->remote_hz) -
  179. tp->rx_opt.rcv_tsecr * (LP_RESOL / HZ);
  180. if (owd < 0)
  181. owd = -owd;
  182. }
  183. if (owd > 0)
  184. lp->flag |= LP_VALID_OWD;
  185. else
  186. lp->flag &= ~LP_VALID_OWD;
  187. return owd;
  188. }
  189. /**
  190. * tcp_lp_rtt_sample
  191. *
  192. * Implementation or rtt_sample.
  193. * Will take the following action,
  194. * 1. calc OWD,
  195. * 2. record the min/max OWD,
  196. * 3. calc smoothed OWD (SOWD).
  197. * Most ideas come from the original TCP-LP implementation.
  198. */
  199. static void tcp_lp_rtt_sample(struct sock *sk, u32 usrtt)
  200. {
  201. struct lp *lp = inet_csk_ca(sk);
  202. s64 mowd = tcp_lp_owd_calculator(sk);
  203. /* sorry that we don't have valid data */
  204. if (!(lp->flag & LP_VALID_RHZ) || !(lp->flag & LP_VALID_OWD))
  205. return;
  206. /* record the next min owd */
  207. if (mowd < lp->owd_min)
  208. lp->owd_min = mowd;
  209. /* always forget the max of the max
  210. * we just set owd_max as one below it */
  211. if (mowd > lp->owd_max) {
  212. if (mowd > lp->owd_max_rsv) {
  213. if (lp->owd_max_rsv == 0)
  214. lp->owd_max = mowd;
  215. else
  216. lp->owd_max = lp->owd_max_rsv;
  217. lp->owd_max_rsv = mowd;
  218. } else
  219. lp->owd_max = mowd;
  220. }
  221. /* calc for smoothed owd */
  222. if (lp->sowd != 0) {
  223. mowd -= lp->sowd >> 3; /* m is now error in owd est */
  224. lp->sowd += mowd; /* owd = 7/8 owd + 1/8 new */
  225. } else
  226. lp->sowd = mowd << 3; /* take the measured time be owd */
  227. }
  228. /**
  229. * tcp_lp_pkts_acked
  230. *
  231. * Implementation of pkts_acked.
  232. * Deal with active drop under Early Congestion Indication.
  233. * Only drop to half and 1 will be handle, because we hope to use back
  234. * newReno in increase case.
  235. * We work it out by following the idea from TCP-LP's paper directly
  236. */
  237. static void tcp_lp_pkts_acked(struct sock *sk, u32 num_acked)
  238. {
  239. struct tcp_sock *tp = tcp_sk(sk);
  240. struct lp *lp = inet_csk_ca(sk);
  241. /* calc inference */
  242. if (tcp_time_stamp > tp->rx_opt.rcv_tsecr)
  243. lp->inference = 3 * (tcp_time_stamp - tp->rx_opt.rcv_tsecr);
  244. /* test if within inference */
  245. if (lp->last_drop && (tcp_time_stamp - lp->last_drop < lp->inference))
  246. lp->flag |= LP_WITHIN_INF;
  247. else
  248. lp->flag &= ~LP_WITHIN_INF;
  249. /* test if within threshold */
  250. if (lp->sowd >> 3 <
  251. lp->owd_min + 15 * (lp->owd_max - lp->owd_min) / 100)
  252. lp->flag |= LP_WITHIN_THR;
  253. else
  254. lp->flag &= ~LP_WITHIN_THR;
  255. pr_debug("TCP-LP: %05o|%5u|%5u|%15u|%15u|%15u\n", lp->flag,
  256. tp->snd_cwnd, lp->remote_hz, lp->owd_min, lp->owd_max,
  257. lp->sowd >> 3);
  258. if (lp->flag & LP_WITHIN_THR)
  259. return;
  260. /* FIXME: try to reset owd_min and owd_max here
  261. * so decrease the chance the min/max is no longer suitable
  262. * and will usually within threshold when whithin inference */
  263. lp->owd_min = lp->sowd >> 3;
  264. lp->owd_max = lp->sowd >> 2;
  265. lp->owd_max_rsv = lp->sowd >> 2;
  266. /* happened within inference
  267. * drop snd_cwnd into 1 */
  268. if (lp->flag & LP_WITHIN_INF)
  269. tp->snd_cwnd = 1U;
  270. /* happened after inference
  271. * cut snd_cwnd into half */
  272. else
  273. tp->snd_cwnd = max(tp->snd_cwnd >> 1U, 1U);
  274. /* record this drop time */
  275. lp->last_drop = tcp_time_stamp;
  276. }
  277. static struct tcp_congestion_ops tcp_lp = {
  278. .init = tcp_lp_init,
  279. .ssthresh = tcp_reno_ssthresh,
  280. .cong_avoid = tcp_lp_cong_avoid,
  281. .min_cwnd = tcp_reno_min_cwnd,
  282. .rtt_sample = tcp_lp_rtt_sample,
  283. .pkts_acked = tcp_lp_pkts_acked,
  284. .owner = THIS_MODULE,
  285. .name = "lp"
  286. };
  287. static int __init tcp_lp_register(void)
  288. {
  289. BUILD_BUG_ON(sizeof(struct lp) > ICSK_CA_PRIV_SIZE);
  290. return tcp_register_congestion_control(&tcp_lp);
  291. }
  292. static void __exit tcp_lp_unregister(void)
  293. {
  294. tcp_unregister_congestion_control(&tcp_lp);
  295. }
  296. module_init(tcp_lp_register);
  297. module_exit(tcp_lp_unregister);
  298. MODULE_AUTHOR("Wong Hoi Sing Edison, Hung Hing Lun Mike");
  299. MODULE_LICENSE("GPL");
  300. MODULE_DESCRIPTION("TCP Low Priority");