Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 1 | /* |
| 2 | * |
| 3 | * YeAH TCP |
| 4 | * |
| 5 | * For further details look at: |
Weilong Chen | 49564e5 | 2013-12-23 14:37:32 +0800 | [diff] [blame] | 6 | * https://web.archive.org/web/20080316215752/http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 7 | * |
| 8 | */ |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 9 | #include <linux/mm.h> |
| 10 | #include <linux/module.h> |
| 11 | #include <linux/skbuff.h> |
| 12 | #include <linux/inet_diag.h> |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 13 | |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 14 | #include <net/tcp.h> |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 15 | |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 16 | #include "tcp_vegas.h" |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 17 | |
Weilong Chen | 49564e5 | 2013-12-23 14:37:32 +0800 | [diff] [blame] | 18 | #define TCP_YEAH_ALPHA 80 /* number of packets queued at the bottleneck */ |
| 19 | #define TCP_YEAH_GAMMA 1 /* fraction of queue to be removed per rtt */ |
| 20 | #define TCP_YEAH_DELTA 3 /* log minimum fraction of cwnd to be removed on loss */ |
| 21 | #define TCP_YEAH_EPSILON 1 /* log maximum fraction to be removed on early decongestion */ |
| 22 | #define TCP_YEAH_PHY 8 /* maximum delta from base */ |
| 23 | #define TCP_YEAH_RHO 16 /* minimum number of consecutive rtt to consider competition on loss */ |
| 24 | #define TCP_YEAH_ZETA 50 /* minimum number of state switches to reset reno_count */ |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 25 | |
| 26 | #define TCP_SCALABLE_AI_CNT 100U |
| 27 | |
| 28 | /* YeAH variables */ |
| 29 | struct yeah { |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 30 | struct vegas vegas; /* must be first */ |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 31 | |
| 32 | /* YeAH */ |
| 33 | u32 lastQ; |
| 34 | u32 doing_reno_now; |
| 35 | |
| 36 | u32 reno_count; |
| 37 | u32 fast_count; |
| 38 | |
| 39 | u32 pkts_acked; |
| 40 | }; |
| 41 | |
| 42 | static void tcp_yeah_init(struct sock *sk) |
| 43 | { |
| 44 | struct tcp_sock *tp = tcp_sk(sk); |
| 45 | struct yeah *yeah = inet_csk_ca(sk); |
| 46 | |
| 47 | tcp_vegas_init(sk); |
| 48 | |
| 49 | yeah->doing_reno_now = 0; |
| 50 | yeah->lastQ = 0; |
| 51 | |
| 52 | yeah->reno_count = 2; |
| 53 | |
| 54 | /* Ensure the MD arithmetic works. This is somewhat pedantic, |
| 55 | * since I don't think we will see a cwnd this large. :) */ |
| 56 | tp->snd_cwnd_clamp = min_t(u32, tp->snd_cwnd_clamp, 0xffffffff/128); |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 57 | } |
| 58 | |
Lawrence Brakmo | 756ee17 | 2016-05-11 10:02:13 -0700 | [diff] [blame] | 59 | static void tcp_yeah_pkts_acked(struct sock *sk, |
| 60 | const struct ack_sample *sample) |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 61 | { |
| 62 | const struct inet_connection_sock *icsk = inet_csk(sk); |
| 63 | struct yeah *yeah = inet_csk_ca(sk); |
| 64 | |
| 65 | if (icsk->icsk_ca_state == TCP_CA_Open) |
Lawrence Brakmo | 756ee17 | 2016-05-11 10:02:13 -0700 | [diff] [blame] | 66 | yeah->pkts_acked = sample->pkts_acked; |
Stephen Hemminger | 164891a | 2007-04-23 22:26:16 -0700 | [diff] [blame] | 67 | |
Lawrence Brakmo | 756ee17 | 2016-05-11 10:02:13 -0700 | [diff] [blame] | 68 | tcp_vegas_pkts_acked(sk, sample); |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 69 | } |
| 70 | |
Eric Dumazet | 2490155 | 2014-05-02 21:18:05 -0700 | [diff] [blame] | 71 | static void tcp_yeah_cong_avoid(struct sock *sk, u32 ack, u32 acked) |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 72 | { |
| 73 | struct tcp_sock *tp = tcp_sk(sk); |
| 74 | struct yeah *yeah = inet_csk_ca(sk); |
| 75 | |
Eric Dumazet | 2490155 | 2014-05-02 21:18:05 -0700 | [diff] [blame] | 76 | if (!tcp_is_cwnd_limited(sk)) |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 77 | return; |
| 78 | |
Artem Germanov | db7196a | 2016-09-07 10:49:36 -0700 | [diff] [blame] | 79 | if (tcp_in_slow_start(tp)) |
Yuchung Cheng | 9f9843a7 | 2013-10-31 11:07:31 -0700 | [diff] [blame] | 80 | tcp_slow_start(tp, acked); |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 81 | |
| 82 | else if (!yeah->doing_reno_now) { |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 83 | /* Scalable */ |
| 84 | |
Jianjun Kong | 5a5f3a8 | 2008-11-03 00:24:34 -0800 | [diff] [blame] | 85 | tp->snd_cwnd_cnt += yeah->pkts_acked; |
stephen hemminger | 688d194 | 2014-08-29 23:32:05 -0700 | [diff] [blame] | 86 | if (tp->snd_cwnd_cnt > min(tp->snd_cwnd, TCP_SCALABLE_AI_CNT)) { |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 87 | if (tp->snd_cwnd < tp->snd_cwnd_clamp) |
| 88 | tp->snd_cwnd++; |
| 89 | tp->snd_cwnd_cnt = 0; |
| 90 | } |
| 91 | |
| 92 | yeah->pkts_acked = 1; |
| 93 | |
| 94 | } else { |
| 95 | /* Reno */ |
Neal Cardwell | e73ebb0 | 2015-01-28 20:01:35 -0500 | [diff] [blame] | 96 | tcp_cong_avoid_ai(tp, tp->snd_cwnd, 1); |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 97 | } |
| 98 | |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 99 | /* The key players are v_vegas.beg_snd_una and v_beg_snd_nxt. |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 100 | * |
| 101 | * These are so named because they represent the approximate values |
| 102 | * of snd_una and snd_nxt at the beginning of the current RTT. More |
| 103 | * precisely, they represent the amount of data sent during the RTT. |
| 104 | * At the end of the RTT, when we receive an ACK for v_beg_snd_nxt, |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 105 | * we will calculate that (v_beg_snd_nxt - v_vegas.beg_snd_una) outstanding |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 106 | * bytes of data have been ACKed during the course of the RTT, giving |
| 107 | * an "actual" rate of: |
| 108 | * |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 109 | * (v_beg_snd_nxt - v_vegas.beg_snd_una) / (rtt duration) |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 110 | * |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 111 | * Unfortunately, v_vegas.beg_snd_una is not exactly equal to snd_una, |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 112 | * because delayed ACKs can cover more than one segment, so they |
| 113 | * don't line up yeahly with the boundaries of RTTs. |
| 114 | * |
| 115 | * Another unfortunate fact of life is that delayed ACKs delay the |
| 116 | * advance of the left edge of our send window, so that the number |
| 117 | * of bytes we send in an RTT is often less than our cwnd will allow. |
| 118 | * So we keep track of our cwnd separately, in v_beg_snd_cwnd. |
| 119 | */ |
| 120 | |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 121 | if (after(ack, yeah->vegas.beg_snd_nxt)) { |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 122 | /* We do the Vegas calculations only if we got enough RTT |
| 123 | * samples that we can be reasonably sure that we got |
| 124 | * at least one RTT sample that wasn't from a delayed ACK. |
| 125 | * If we only had 2 samples total, |
| 126 | * then that means we're getting only 1 ACK per RTT, which |
| 127 | * means they're almost certainly delayed ACKs. |
| 128 | * If we have 3 samples, we should be OK. |
| 129 | */ |
| 130 | |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 131 | if (yeah->vegas.cntRTT > 2) { |
Stephen Hemminger | 43e6839 | 2007-03-06 20:21:20 -0800 | [diff] [blame] | 132 | u32 rtt, queue; |
| 133 | u64 bw; |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 134 | |
| 135 | /* We have enough RTT samples, so, using the Vegas |
| 136 | * algorithm, we determine if we should increase or |
| 137 | * decrease cwnd, and by how much. |
| 138 | */ |
| 139 | |
| 140 | /* Pluck out the RTT we are using for the Vegas |
| 141 | * calculations. This is the min RTT seen during the |
| 142 | * last RTT. Taking the min filters out the effects |
| 143 | * of delayed ACKs, at the cost of noticing congestion |
| 144 | * a bit later. |
| 145 | */ |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 146 | rtt = yeah->vegas.minRTT; |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 147 | |
Stephen Hemminger | 43e6839 | 2007-03-06 20:21:20 -0800 | [diff] [blame] | 148 | /* Compute excess number of packets above bandwidth |
| 149 | * Avoid doing full 64 bit divide. |
| 150 | */ |
| 151 | bw = tp->snd_cwnd; |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 152 | bw *= rtt - yeah->vegas.baseRTT; |
Stephen Hemminger | 43e6839 | 2007-03-06 20:21:20 -0800 | [diff] [blame] | 153 | do_div(bw, rtt); |
| 154 | queue = bw; |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 155 | |
Stephen Hemminger | 43e6839 | 2007-03-06 20:21:20 -0800 | [diff] [blame] | 156 | if (queue > TCP_YEAH_ALPHA || |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 157 | rtt - yeah->vegas.baseRTT > (yeah->vegas.baseRTT / TCP_YEAH_PHY)) { |
Joe Perches | 9d4fb27 | 2009-11-23 10:41:23 -0800 | [diff] [blame] | 158 | if (queue > TCP_YEAH_ALPHA && |
| 159 | tp->snd_cwnd > yeah->reno_count) { |
Stephen Hemminger | 43e6839 | 2007-03-06 20:21:20 -0800 | [diff] [blame] | 160 | u32 reduction = min(queue / TCP_YEAH_GAMMA , |
| 161 | tp->snd_cwnd >> TCP_YEAH_EPSILON); |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 162 | |
| 163 | tp->snd_cwnd -= reduction; |
| 164 | |
Stephen Hemminger | 43e6839 | 2007-03-06 20:21:20 -0800 | [diff] [blame] | 165 | tp->snd_cwnd = max(tp->snd_cwnd, |
| 166 | yeah->reno_count); |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 167 | |
| 168 | tp->snd_ssthresh = tp->snd_cwnd; |
Stephen Hemminger | 43e6839 | 2007-03-06 20:21:20 -0800 | [diff] [blame] | 169 | } |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 170 | |
| 171 | if (yeah->reno_count <= 2) |
Stephen Hemminger | 43e6839 | 2007-03-06 20:21:20 -0800 | [diff] [blame] | 172 | yeah->reno_count = max(tp->snd_cwnd>>1, 2U); |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 173 | else |
| 174 | yeah->reno_count++; |
| 175 | |
Stephen Hemminger | 43e6839 | 2007-03-06 20:21:20 -0800 | [diff] [blame] | 176 | yeah->doing_reno_now = min(yeah->doing_reno_now + 1, |
| 177 | 0xffffffU); |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 178 | } else { |
| 179 | yeah->fast_count++; |
| 180 | |
| 181 | if (yeah->fast_count > TCP_YEAH_ZETA) { |
| 182 | yeah->reno_count = 2; |
| 183 | yeah->fast_count = 0; |
| 184 | } |
| 185 | |
| 186 | yeah->doing_reno_now = 0; |
| 187 | } |
| 188 | |
| 189 | yeah->lastQ = queue; |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 190 | } |
| 191 | |
| 192 | /* Save the extent of the current window so we can use this |
| 193 | * at the end of the next RTT. |
| 194 | */ |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 195 | yeah->vegas.beg_snd_una = yeah->vegas.beg_snd_nxt; |
| 196 | yeah->vegas.beg_snd_nxt = tp->snd_nxt; |
| 197 | yeah->vegas.beg_snd_cwnd = tp->snd_cwnd; |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 198 | |
| 199 | /* Wipe the slate clean for the next RTT. */ |
Stephen Hemminger | 7752237 | 2007-04-23 22:28:23 -0700 | [diff] [blame] | 200 | yeah->vegas.cntRTT = 0; |
| 201 | yeah->vegas.minRTT = 0x7fffffff; |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 202 | } |
| 203 | } |
| 204 | |
stephen hemminger | 688d194 | 2014-08-29 23:32:05 -0700 | [diff] [blame] | 205 | static u32 tcp_yeah_ssthresh(struct sock *sk) |
| 206 | { |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 207 | const struct tcp_sock *tp = tcp_sk(sk); |
| 208 | struct yeah *yeah = inet_csk_ca(sk); |
| 209 | u32 reduction; |
| 210 | |
| 211 | if (yeah->doing_reno_now < TCP_YEAH_RHO) { |
| 212 | reduction = yeah->lastQ; |
| 213 | |
Weilong Chen | 0c9a67d | 2013-12-23 14:37:27 +0800 | [diff] [blame] | 214 | reduction = min(reduction, max(tp->snd_cwnd>>1, 2U)); |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 215 | |
Weilong Chen | 0c9a67d | 2013-12-23 14:37:27 +0800 | [diff] [blame] | 216 | reduction = max(reduction, tp->snd_cwnd >> TCP_YEAH_DELTA); |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 217 | } else |
Jianjun Kong | 5a5f3a8 | 2008-11-03 00:24:34 -0800 | [diff] [blame] | 218 | reduction = max(tp->snd_cwnd>>1, 2U); |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 219 | |
| 220 | yeah->fast_count = 0; |
| 221 | yeah->reno_count = max(yeah->reno_count>>1, 2U); |
| 222 | |
Neal Cardwell | 83d15e7 | 2016-01-11 13:42:43 -0500 | [diff] [blame] | 223 | return max_t(int, tp->snd_cwnd - reduction, 2); |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 224 | } |
| 225 | |
Stephen Hemminger | a252beb | 2011-03-10 00:40:17 -0800 | [diff] [blame] | 226 | static struct tcp_congestion_ops tcp_yeah __read_mostly = { |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 227 | .init = tcp_yeah_init, |
| 228 | .ssthresh = tcp_yeah_ssthresh, |
| 229 | .cong_avoid = tcp_yeah_cong_avoid, |
Angelo P. Castellani | 5ef8147 | 2007-02-22 00:23:05 -0800 | [diff] [blame] | 230 | .set_state = tcp_vegas_state, |
| 231 | .cwnd_event = tcp_vegas_cwnd_event, |
| 232 | .get_info = tcp_vegas_get_info, |
| 233 | .pkts_acked = tcp_yeah_pkts_acked, |
| 234 | |
| 235 | .owner = THIS_MODULE, |
| 236 | .name = "yeah", |
| 237 | }; |
| 238 | |
| 239 | static int __init tcp_yeah_register(void) |
| 240 | { |
| 241 | BUG_ON(sizeof(struct yeah) > ICSK_CA_PRIV_SIZE); |
| 242 | tcp_register_congestion_control(&tcp_yeah); |
| 243 | return 0; |
| 244 | } |
| 245 | |
| 246 | static void __exit tcp_yeah_unregister(void) |
| 247 | { |
| 248 | tcp_unregister_congestion_control(&tcp_yeah); |
| 249 | } |
| 250 | |
| 251 | module_init(tcp_yeah_register); |
| 252 | module_exit(tcp_yeah_unregister); |
| 253 | |
| 254 | MODULE_AUTHOR("Angelo P. Castellani"); |
| 255 | MODULE_LICENSE("GPL"); |
| 256 | MODULE_DESCRIPTION("YeAH TCP"); |