tcp_westwood.c 8.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306
  1. /*
  2. * TCP Westwood+: end-to-end bandwidth estimation for TCP
  3. *
  4. * Angelo Dell'Aera: author of the first version of TCP Westwood+ in Linux 2.4
  5. *
  6. * Support at http://c3lab.poliba.it/index.php/Westwood
  7. * Main references in literature:
  8. *
  9. * - Mascolo S, Casetti, M. Gerla et al.
  10. * "TCP Westwood: bandwidth estimation for TCP" Proc. ACM Mobicom 2001
  11. *
  12. * - A. Grieco, s. Mascolo
  13. * "Performance evaluation of New Reno, Vegas, Westwood+ TCP" ACM Computer
  14. * Comm. Review, 2004
  15. *
  16. * - A. Dell'Aera, L. Grieco, S. Mascolo.
  17. * "Linux 2.4 Implementation of Westwood+ TCP with Rate-Halving :
  18. * A Performance Evaluation Over the Internet" (ICC 2004), Paris, June 2004
  19. *
  20. * Westwood+ employs end-to-end bandwidth measurement to set cwnd and
  21. * ssthresh after packet loss. The probing phase is as the original Reno.
  22. */
  23. #include <linux/mm.h>
  24. #include <linux/module.h>
  25. #include <linux/skbuff.h>
  26. #include <linux/inet_diag.h>
  27. #include <net/tcp.h>
  28. /* TCP Westwood structure */
  29. struct westwood {
  30. u32 bw_ns_est; /* first bandwidth estimation..not too smoothed 8) */
  31. u32 bw_est; /* bandwidth estimate */
  32. u32 rtt_win_sx; /* here starts a new evaluation... */
  33. u32 bk;
  34. u32 snd_una; /* used for evaluating the number of acked bytes */
  35. u32 cumul_ack;
  36. u32 accounted;
  37. u32 rtt;
  38. u32 rtt_min; /* minimum observed RTT */
  39. u8 first_ack; /* flag which infers that this is the first ack */
  40. u8 reset_rtt_min; /* Reset RTT min to next RTT sample*/
  41. };
  42. /* TCP Westwood functions and constants */
  43. #define TCP_WESTWOOD_RTT_MIN (HZ/20) /* 50ms */
  44. #define TCP_WESTWOOD_INIT_RTT (20*HZ) /* maybe too conservative?! */
  45. /*
  46. * @tcp_westwood_create
  47. * This function initializes fields used in TCP Westwood+,
  48. * it is called after the initial SYN, so the sequence numbers
  49. * are correct but new passive connections we have no
  50. * information about RTTmin at this time so we simply set it to
  51. * TCP_WESTWOOD_INIT_RTT. This value was chosen to be too conservative
  52. * since in this way we're sure it will be updated in a consistent
  53. * way as soon as possible. It will reasonably happen within the first
  54. * RTT period of the connection lifetime.
  55. */
  56. static void tcp_westwood_init(struct sock *sk)
  57. {
  58. struct westwood *w = inet_csk_ca(sk);
  59. w->bk = 0;
  60. w->bw_ns_est = 0;
  61. w->bw_est = 0;
  62. w->accounted = 0;
  63. w->cumul_ack = 0;
  64. w->reset_rtt_min = 1;
  65. w->rtt_min = w->rtt = TCP_WESTWOOD_INIT_RTT;
  66. w->rtt_win_sx = tcp_time_stamp;
  67. w->snd_una = tcp_sk(sk)->snd_una;
  68. w->first_ack = 1;
  69. }
  70. /*
  71. * @westwood_do_filter
  72. * Low-pass filter. Implemented using constant coefficients.
  73. */
  74. static inline u32 westwood_do_filter(u32 a, u32 b)
  75. {
  76. return (((7 * a) + b) >> 3);
  77. }
  78. static void westwood_filter(struct westwood *w, u32 delta)
  79. {
  80. /* If the filter is empty fill it with the first sample of bandwidth */
  81. if (w->bw_ns_est == 0 && w->bw_est == 0) {
  82. w->bw_ns_est = w->bk / delta;
  83. w->bw_est = w->bw_ns_est;
  84. } else {
  85. w->bw_ns_est = westwood_do_filter(w->bw_ns_est, w->bk / delta);
  86. w->bw_est = westwood_do_filter(w->bw_est, w->bw_ns_est);
  87. }
  88. }
  89. /*
  90. * @westwood_pkts_acked
  91. * Called after processing group of packets.
  92. * but all westwood needs is the last sample of srtt.
  93. */
  94. static void tcp_westwood_pkts_acked(struct sock *sk, u32 cnt)
  95. {
  96. struct westwood *w = inet_csk_ca(sk);
  97. if (cnt > 0)
  98. w->rtt = tcp_sk(sk)->srtt >> 3;
  99. }
  100. /*
  101. * @westwood_update_window
  102. * It updates RTT evaluation window if it is the right moment to do
  103. * it. If so it calls filter for evaluating bandwidth.
  104. */
  105. static void westwood_update_window(struct sock *sk)
  106. {
  107. struct westwood *w = inet_csk_ca(sk);
  108. s32 delta = tcp_time_stamp - w->rtt_win_sx;
  109. /* Initialize w->snd_una with the first acked sequence number in order
  110. * to fix mismatch between tp->snd_una and w->snd_una for the first
  111. * bandwidth sample
  112. */
  113. if (w->first_ack) {
  114. w->snd_una = tcp_sk(sk)->snd_una;
  115. w->first_ack = 0;
  116. }
  117. /*
  118. * See if a RTT-window has passed.
  119. * Be careful since if RTT is less than
  120. * 50ms we don't filter but we continue 'building the sample'.
  121. * This minimum limit was chosen since an estimation on small
  122. * time intervals is better to avoid...
  123. * Obviously on a LAN we reasonably will always have
  124. * right_bound = left_bound + WESTWOOD_RTT_MIN
  125. */
  126. if (w->rtt && delta > max_t(u32, w->rtt, TCP_WESTWOOD_RTT_MIN)) {
  127. westwood_filter(w, delta);
  128. w->bk = 0;
  129. w->rtt_win_sx = tcp_time_stamp;
  130. }
  131. }
  132. static inline void update_rtt_min(struct westwood *w)
  133. {
  134. if (w->reset_rtt_min) {
  135. w->rtt_min = w->rtt;
  136. w->reset_rtt_min = 0;
  137. } else
  138. w->rtt_min = min(w->rtt, w->rtt_min);
  139. }
  140. /*
  141. * @westwood_fast_bw
  142. * It is called when we are in fast path. In particular it is called when
  143. * header prediction is successful. In such case in fact update is
  144. * straight forward and doesn't need any particular care.
  145. */
  146. static inline void westwood_fast_bw(struct sock *sk)
  147. {
  148. const struct tcp_sock *tp = tcp_sk(sk);
  149. struct westwood *w = inet_csk_ca(sk);
  150. westwood_update_window(sk);
  151. w->bk += tp->snd_una - w->snd_una;
  152. w->snd_una = tp->snd_una;
  153. update_rtt_min(w);
  154. }
  155. /*
  156. * @westwood_acked_count
  157. * This function evaluates cumul_ack for evaluating bk in case of
  158. * delayed or partial acks.
  159. */
  160. static inline u32 westwood_acked_count(struct sock *sk)
  161. {
  162. const struct tcp_sock *tp = tcp_sk(sk);
  163. struct westwood *w = inet_csk_ca(sk);
  164. w->cumul_ack = tp->snd_una - w->snd_una;
  165. /* If cumul_ack is 0 this is a dupack since it's not moving
  166. * tp->snd_una.
  167. */
  168. if (!w->cumul_ack) {
  169. w->accounted += tp->mss_cache;
  170. w->cumul_ack = tp->mss_cache;
  171. }
  172. if (w->cumul_ack > tp->mss_cache) {
  173. /* Partial or delayed ack */
  174. if (w->accounted >= w->cumul_ack) {
  175. w->accounted -= w->cumul_ack;
  176. w->cumul_ack = tp->mss_cache;
  177. } else {
  178. w->cumul_ack -= w->accounted;
  179. w->accounted = 0;
  180. }
  181. }
  182. w->snd_una = tp->snd_una;
  183. return w->cumul_ack;
  184. }
  185. /*
  186. * TCP Westwood
  187. * Here limit is evaluated as Bw estimation*RTTmin (for obtaining it
  188. * in packets we use mss_cache). Rttmin is guaranteed to be >= 2
  189. * so avoids ever returning 0.
  190. */
  191. static u32 tcp_westwood_bw_rttmin(const struct sock *sk)
  192. {
  193. const struct tcp_sock *tp = tcp_sk(sk);
  194. const struct westwood *w = inet_csk_ca(sk);
  195. return max_t(u32, (w->bw_est * w->rtt_min) / tp->mss_cache, 2);
  196. }
  197. static void tcp_westwood_event(struct sock *sk, enum tcp_ca_event event)
  198. {
  199. struct tcp_sock *tp = tcp_sk(sk);
  200. struct westwood *w = inet_csk_ca(sk);
  201. switch(event) {
  202. case CA_EVENT_FAST_ACK:
  203. westwood_fast_bw(sk);
  204. break;
  205. case CA_EVENT_COMPLETE_CWR:
  206. tp->snd_cwnd = tp->snd_ssthresh = tcp_westwood_bw_rttmin(sk);
  207. break;
  208. case CA_EVENT_FRTO:
  209. tp->snd_ssthresh = tcp_westwood_bw_rttmin(sk);
  210. /* Update RTT_min when next ack arrives */
  211. w->reset_rtt_min = 1;
  212. break;
  213. case CA_EVENT_SLOW_ACK:
  214. westwood_update_window(sk);
  215. w->bk += westwood_acked_count(sk);
  216. update_rtt_min(w);
  217. break;
  218. default:
  219. /* don't care */
  220. break;
  221. }
  222. }
  223. /* Extract info for Tcp socket info provided via netlink. */
  224. static void tcp_westwood_info(struct sock *sk, u32 ext,
  225. struct sk_buff *skb)
  226. {
  227. const struct westwood *ca = inet_csk_ca(sk);
  228. if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) {
  229. struct rtattr *rta;
  230. struct tcpvegas_info *info;
  231. rta = __RTA_PUT(skb, INET_DIAG_VEGASINFO, sizeof(*info));
  232. info = RTA_DATA(rta);
  233. info->tcpv_enabled = 1;
  234. info->tcpv_rttcnt = 0;
  235. info->tcpv_rtt = jiffies_to_usecs(ca->rtt);
  236. info->tcpv_minrtt = jiffies_to_usecs(ca->rtt_min);
  237. rtattr_failure: ;
  238. }
  239. }
  240. static struct tcp_congestion_ops tcp_westwood = {
  241. .init = tcp_westwood_init,
  242. .ssthresh = tcp_reno_ssthresh,
  243. .cong_avoid = tcp_reno_cong_avoid,
  244. .min_cwnd = tcp_westwood_bw_rttmin,
  245. .cwnd_event = tcp_westwood_event,
  246. .get_info = tcp_westwood_info,
  247. .pkts_acked = tcp_westwood_pkts_acked,
  248. .owner = THIS_MODULE,
  249. .name = "westwood"
  250. };
  251. static int __init tcp_westwood_register(void)
  252. {
  253. BUILD_BUG_ON(sizeof(struct westwood) > ICSK_CA_PRIV_SIZE);
  254. return tcp_register_congestion_control(&tcp_westwood);
  255. }
  256. static void __exit tcp_westwood_unregister(void)
  257. {
  258. tcp_unregister_congestion_control(&tcp_westwood);
  259. }
  260. module_init(tcp_westwood_register);
  261. module_exit(tcp_westwood_unregister);
  262. MODULE_AUTHOR("Stephen Hemminger, Angelo Dell'Aera");
  263. MODULE_LICENSE("GPL");
  264. MODULE_DESCRIPTION("TCP Westwood+");