15ef81475SAngelo P. Castellani /* 25ef81475SAngelo P. Castellani * 35ef81475SAngelo P. Castellani * YeAH TCP 45ef81475SAngelo P. Castellani * 55ef81475SAngelo P. Castellani * For further details look at: 649564e55SWeilong Chen * https://web.archive.org/web/20080316215752/http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf 75ef81475SAngelo P. Castellani * 85ef81475SAngelo P. Castellani */ 97752237eSStephen Hemminger #include <linux/mm.h> 107752237eSStephen Hemminger #include <linux/module.h> 117752237eSStephen Hemminger #include <linux/skbuff.h> 127752237eSStephen Hemminger #include <linux/inet_diag.h> 135ef81475SAngelo P. Castellani 147752237eSStephen Hemminger #include <net/tcp.h> 155ef81475SAngelo P. Castellani 167752237eSStephen Hemminger #include "tcp_vegas.h" 175ef81475SAngelo P. Castellani 1849564e55SWeilong Chen #define TCP_YEAH_ALPHA 80 /* number of packets queued at the bottleneck */ 1949564e55SWeilong Chen #define TCP_YEAH_GAMMA 1 /* fraction of queue to be removed per rtt */ 2049564e55SWeilong Chen #define TCP_YEAH_DELTA 3 /* log minimum fraction of cwnd to be removed on loss */ 2149564e55SWeilong Chen #define TCP_YEAH_EPSILON 1 /* log maximum fraction to be removed on early decongestion */ 2249564e55SWeilong Chen #define TCP_YEAH_PHY 8 /* maximum delta from base */ 2349564e55SWeilong Chen #define TCP_YEAH_RHO 16 /* minimum number of consecutive rtt to consider competition on loss */ 2449564e55SWeilong Chen #define TCP_YEAH_ZETA 50 /* minimum number of state switches to reset reno_count */ 255ef81475SAngelo P. Castellani 265ef81475SAngelo P. Castellani #define TCP_SCALABLE_AI_CNT 100U 275ef81475SAngelo P. Castellani 285ef81475SAngelo P. Castellani /* YeAH variables */ 295ef81475SAngelo P. Castellani struct yeah { 307752237eSStephen Hemminger struct vegas vegas; /* must be first */ 315ef81475SAngelo P. Castellani 325ef81475SAngelo P. Castellani /* YeAH */ 335ef81475SAngelo P. Castellani u32 lastQ; 345ef81475SAngelo P. Castellani u32 doing_reno_now; 355ef81475SAngelo P. Castellani 365ef81475SAngelo P. Castellani u32 reno_count; 375ef81475SAngelo P. Castellani u32 fast_count; 385ef81475SAngelo P. Castellani 395ef81475SAngelo P. Castellani u32 pkts_acked; 405ef81475SAngelo P. Castellani }; 415ef81475SAngelo P. Castellani 425ef81475SAngelo P. Castellani static void tcp_yeah_init(struct sock *sk) 435ef81475SAngelo P. Castellani { 445ef81475SAngelo P. Castellani struct tcp_sock *tp = tcp_sk(sk); 455ef81475SAngelo P. Castellani struct yeah *yeah = inet_csk_ca(sk); 465ef81475SAngelo P. Castellani 475ef81475SAngelo P. Castellani tcp_vegas_init(sk); 485ef81475SAngelo P. Castellani 495ef81475SAngelo P. Castellani yeah->doing_reno_now = 0; 505ef81475SAngelo P. Castellani yeah->lastQ = 0; 515ef81475SAngelo P. Castellani 525ef81475SAngelo P. Castellani yeah->reno_count = 2; 535ef81475SAngelo P. Castellani 545ef81475SAngelo P. Castellani /* Ensure the MD arithmetic works. This is somewhat pedantic, 555ef81475SAngelo P. Castellani * since I don't think we will see a cwnd this large. :) */ 565ef81475SAngelo P. Castellani tp->snd_cwnd_clamp = min_t(u32, tp->snd_cwnd_clamp, 0xffffffff/128); 575ef81475SAngelo P. Castellani } 585ef81475SAngelo P. Castellani 5930cfd0baSStephen Hemminger static void tcp_yeah_pkts_acked(struct sock *sk, u32 pkts_acked, s32 rtt_us) 605ef81475SAngelo P. Castellani { 615ef81475SAngelo P. Castellani const struct inet_connection_sock *icsk = inet_csk(sk); 625ef81475SAngelo P. Castellani struct yeah *yeah = inet_csk_ca(sk); 635ef81475SAngelo P. Castellani 645ef81475SAngelo P. Castellani if (icsk->icsk_ca_state == TCP_CA_Open) 655ef81475SAngelo P. Castellani yeah->pkts_acked = pkts_acked; 66164891aaSStephen Hemminger 6730cfd0baSStephen Hemminger tcp_vegas_pkts_acked(sk, pkts_acked, rtt_us); 685ef81475SAngelo P. Castellani } 695ef81475SAngelo P. Castellani 7024901551SEric Dumazet static void tcp_yeah_cong_avoid(struct sock *sk, u32 ack, u32 acked) 715ef81475SAngelo P. Castellani { 725ef81475SAngelo P. Castellani struct tcp_sock *tp = tcp_sk(sk); 735ef81475SAngelo P. Castellani struct yeah *yeah = inet_csk_ca(sk); 745ef81475SAngelo P. Castellani 7524901551SEric Dumazet if (!tcp_is_cwnd_limited(sk)) 765ef81475SAngelo P. Castellani return; 775ef81475SAngelo P. Castellani 787752237eSStephen Hemminger if (tp->snd_cwnd <= tp->snd_ssthresh) 799f9843a7SYuchung Cheng tcp_slow_start(tp, acked); 807752237eSStephen Hemminger 817752237eSStephen Hemminger else if (!yeah->doing_reno_now) { 825ef81475SAngelo P. Castellani /* Scalable */ 835ef81475SAngelo P. Castellani 845ef81475SAngelo P. Castellani tp->snd_cwnd_cnt += yeah->pkts_acked; 855ef81475SAngelo P. Castellani if (tp->snd_cwnd_cnt > min(tp->snd_cwnd, TCP_SCALABLE_AI_CNT)) { 865ef81475SAngelo P. Castellani if (tp->snd_cwnd < tp->snd_cwnd_clamp) 875ef81475SAngelo P. Castellani tp->snd_cwnd++; 885ef81475SAngelo P. Castellani tp->snd_cwnd_cnt = 0; 895ef81475SAngelo P. Castellani } 905ef81475SAngelo P. Castellani 915ef81475SAngelo P. Castellani yeah->pkts_acked = 1; 925ef81475SAngelo P. Castellani 935ef81475SAngelo P. Castellani } else { 945ef81475SAngelo P. Castellani /* Reno */ 95e73ebb08SNeal Cardwell tcp_cong_avoid_ai(tp, tp->snd_cwnd, 1); 965ef81475SAngelo P. Castellani } 975ef81475SAngelo P. Castellani 987752237eSStephen Hemminger /* The key players are v_vegas.beg_snd_una and v_beg_snd_nxt. 995ef81475SAngelo P. Castellani * 1005ef81475SAngelo P. Castellani * These are so named because they represent the approximate values 1015ef81475SAngelo P. Castellani * of snd_una and snd_nxt at the beginning of the current RTT. More 1025ef81475SAngelo P. Castellani * precisely, they represent the amount of data sent during the RTT. 1035ef81475SAngelo P. Castellani * At the end of the RTT, when we receive an ACK for v_beg_snd_nxt, 1047752237eSStephen Hemminger * we will calculate that (v_beg_snd_nxt - v_vegas.beg_snd_una) outstanding 1055ef81475SAngelo P. Castellani * bytes of data have been ACKed during the course of the RTT, giving 1065ef81475SAngelo P. Castellani * an "actual" rate of: 1075ef81475SAngelo P. Castellani * 1087752237eSStephen Hemminger * (v_beg_snd_nxt - v_vegas.beg_snd_una) / (rtt duration) 1095ef81475SAngelo P. Castellani * 1107752237eSStephen Hemminger * Unfortunately, v_vegas.beg_snd_una is not exactly equal to snd_una, 1115ef81475SAngelo P. Castellani * because delayed ACKs can cover more than one segment, so they 1125ef81475SAngelo P. Castellani * don't line up yeahly with the boundaries of RTTs. 1135ef81475SAngelo P. Castellani * 1145ef81475SAngelo P. Castellani * Another unfortunate fact of life is that delayed ACKs delay the 1155ef81475SAngelo P. Castellani * advance of the left edge of our send window, so that the number 1165ef81475SAngelo P. Castellani * of bytes we send in an RTT is often less than our cwnd will allow. 1175ef81475SAngelo P. Castellani * So we keep track of our cwnd separately, in v_beg_snd_cwnd. 1185ef81475SAngelo P. Castellani */ 1195ef81475SAngelo P. Castellani 1207752237eSStephen Hemminger if (after(ack, yeah->vegas.beg_snd_nxt)) { 1215ef81475SAngelo P. Castellani /* We do the Vegas calculations only if we got enough RTT 1225ef81475SAngelo P. Castellani * samples that we can be reasonably sure that we got 1235ef81475SAngelo P. Castellani * at least one RTT sample that wasn't from a delayed ACK. 1245ef81475SAngelo P. Castellani * If we only had 2 samples total, 1255ef81475SAngelo P. Castellani * then that means we're getting only 1 ACK per RTT, which 1265ef81475SAngelo P. Castellani * means they're almost certainly delayed ACKs. 1275ef81475SAngelo P. Castellani * If we have 3 samples, we should be OK. 1285ef81475SAngelo P. Castellani */ 1295ef81475SAngelo P. Castellani 1307752237eSStephen Hemminger if (yeah->vegas.cntRTT > 2) { 13143e68392SStephen Hemminger u32 rtt, queue; 13243e68392SStephen Hemminger u64 bw; 1335ef81475SAngelo P. Castellani 1345ef81475SAngelo P. Castellani /* We have enough RTT samples, so, using the Vegas 1355ef81475SAngelo P. Castellani * algorithm, we determine if we should increase or 1365ef81475SAngelo P. Castellani * decrease cwnd, and by how much. 1375ef81475SAngelo P. Castellani */ 1385ef81475SAngelo P. Castellani 1395ef81475SAngelo P. Castellani /* Pluck out the RTT we are using for the Vegas 1405ef81475SAngelo P. Castellani * calculations. This is the min RTT seen during the 1415ef81475SAngelo P. Castellani * last RTT. Taking the min filters out the effects 1425ef81475SAngelo P. Castellani * of delayed ACKs, at the cost of noticing congestion 1435ef81475SAngelo P. Castellani * a bit later. 1445ef81475SAngelo P. Castellani */ 1457752237eSStephen Hemminger rtt = yeah->vegas.minRTT; 1465ef81475SAngelo P. Castellani 14743e68392SStephen Hemminger /* Compute excess number of packets above bandwidth 14843e68392SStephen Hemminger * Avoid doing full 64 bit divide. 14943e68392SStephen Hemminger */ 15043e68392SStephen Hemminger bw = tp->snd_cwnd; 1517752237eSStephen Hemminger bw *= rtt - yeah->vegas.baseRTT; 15243e68392SStephen Hemminger do_div(bw, rtt); 15343e68392SStephen Hemminger queue = bw; 1545ef81475SAngelo P. Castellani 15543e68392SStephen Hemminger if (queue > TCP_YEAH_ALPHA || 1567752237eSStephen Hemminger rtt - yeah->vegas.baseRTT > (yeah->vegas.baseRTT / TCP_YEAH_PHY)) { 1579d4fb27dSJoe Perches if (queue > TCP_YEAH_ALPHA && 1589d4fb27dSJoe Perches tp->snd_cwnd > yeah->reno_count) { 1595ef81475SAngelo P. Castellani u32 reduction = min(queue / TCP_YEAH_GAMMA , 1605ef81475SAngelo P. Castellani tp->snd_cwnd >> TCP_YEAH_EPSILON); 1615ef81475SAngelo P. Castellani 1625ef81475SAngelo P. Castellani tp->snd_cwnd -= reduction; 1635ef81475SAngelo P. Castellani 16443e68392SStephen Hemminger tp->snd_cwnd = max(tp->snd_cwnd, 16543e68392SStephen Hemminger yeah->reno_count); 1665ef81475SAngelo P. Castellani 1675ef81475SAngelo P. Castellani tp->snd_ssthresh = tp->snd_cwnd; 1685ef81475SAngelo P. Castellani } 1695ef81475SAngelo P. Castellani 1705ef81475SAngelo P. Castellani if (yeah->reno_count <= 2) 1715ef81475SAngelo P. Castellani yeah->reno_count = max(tp->snd_cwnd>>1, 2U); 1725ef81475SAngelo P. Castellani else 1735ef81475SAngelo P. Castellani yeah->reno_count++; 1745ef81475SAngelo P. Castellani 17543e68392SStephen Hemminger yeah->doing_reno_now = min(yeah->doing_reno_now + 1, 17643e68392SStephen Hemminger 0xffffffU); 1775ef81475SAngelo P. Castellani } else { 1785ef81475SAngelo P. Castellani yeah->fast_count++; 1795ef81475SAngelo P. Castellani 1805ef81475SAngelo P. Castellani if (yeah->fast_count > TCP_YEAH_ZETA) { 1815ef81475SAngelo P. Castellani yeah->reno_count = 2; 1825ef81475SAngelo P. Castellani yeah->fast_count = 0; 1835ef81475SAngelo P. Castellani } 1845ef81475SAngelo P. Castellani 1855ef81475SAngelo P. Castellani yeah->doing_reno_now = 0; 1865ef81475SAngelo P. Castellani } 1875ef81475SAngelo P. Castellani 1885ef81475SAngelo P. Castellani yeah->lastQ = queue; 1895ef81475SAngelo P. Castellani } 1905ef81475SAngelo P. Castellani 1915ef81475SAngelo P. Castellani /* Save the extent of the current window so we can use this 1925ef81475SAngelo P. Castellani * at the end of the next RTT. 1935ef81475SAngelo P. Castellani */ 1947752237eSStephen Hemminger yeah->vegas.beg_snd_una = yeah->vegas.beg_snd_nxt; 1957752237eSStephen Hemminger yeah->vegas.beg_snd_nxt = tp->snd_nxt; 1967752237eSStephen Hemminger yeah->vegas.beg_snd_cwnd = tp->snd_cwnd; 1975ef81475SAngelo P. Castellani 1985ef81475SAngelo P. Castellani /* Wipe the slate clean for the next RTT. */ 1997752237eSStephen Hemminger yeah->vegas.cntRTT = 0; 2007752237eSStephen Hemminger yeah->vegas.minRTT = 0x7fffffff; 2015ef81475SAngelo P. Castellani } 2025ef81475SAngelo P. Castellani } 2035ef81475SAngelo P. Castellani 204688d1945Sstephen hemminger static u32 tcp_yeah_ssthresh(struct sock *sk) 205688d1945Sstephen hemminger { 2065ef81475SAngelo P. Castellani const struct tcp_sock *tp = tcp_sk(sk); 2075ef81475SAngelo P. Castellani struct yeah *yeah = inet_csk_ca(sk); 2085ef81475SAngelo P. Castellani u32 reduction; 2095ef81475SAngelo P. Castellani 2105ef81475SAngelo P. Castellani if (yeah->doing_reno_now < TCP_YEAH_RHO) { 2115ef81475SAngelo P. Castellani reduction = yeah->lastQ; 2125ef81475SAngelo P. Castellani 2135ef81475SAngelo P. Castellani reduction = min(reduction, max(tp->snd_cwnd>>1, 2U)); 2145ef81475SAngelo P. Castellani 2155ef81475SAngelo P. Castellani reduction = max(reduction, tp->snd_cwnd >> TCP_YEAH_DELTA); 2165ef81475SAngelo P. Castellani } else 2175ef81475SAngelo P. Castellani reduction = max(tp->snd_cwnd>>1, 2U); 2185ef81475SAngelo P. Castellani 2195ef81475SAngelo P. Castellani yeah->fast_count = 0; 2205ef81475SAngelo P. Castellani yeah->reno_count = max(yeah->reno_count>>1, 2U); 2215ef81475SAngelo P. Castellani 2225ef81475SAngelo P. Castellani return tp->snd_cwnd - reduction; 2235ef81475SAngelo P. Castellani } 2245ef81475SAngelo P. Castellani 225a252bebeSStephen Hemminger static struct tcp_congestion_ops tcp_yeah __read_mostly = { 2265ef81475SAngelo P. Castellani .init = tcp_yeah_init, 2275ef81475SAngelo P. Castellani .ssthresh = tcp_yeah_ssthresh, 2285ef81475SAngelo P. Castellani .cong_avoid = tcp_yeah_cong_avoid, 2295ef81475SAngelo P. Castellani .set_state = tcp_vegas_state, 2305ef81475SAngelo P. Castellani .cwnd_event = tcp_vegas_cwnd_event, 2315ef81475SAngelo P. Castellani .get_info = tcp_vegas_get_info, 2325ef81475SAngelo P. Castellani .pkts_acked = tcp_yeah_pkts_acked, 2335ef81475SAngelo P. Castellani 2345ef81475SAngelo P. Castellani .owner = THIS_MODULE, 2355ef81475SAngelo P. Castellani .name = "yeah", 2365ef81475SAngelo P. Castellani }; 2375ef81475SAngelo P. Castellani 2385ef81475SAngelo P. Castellani static int __init tcp_yeah_register(void) 2395ef81475SAngelo P. Castellani { 2405ef81475SAngelo P. Castellani BUG_ON(sizeof(struct yeah) > ICSK_CA_PRIV_SIZE); 2415ef81475SAngelo P. Castellani tcp_register_congestion_control(&tcp_yeah); 2425ef81475SAngelo P. Castellani return 0; 2435ef81475SAngelo P. Castellani } 2445ef81475SAngelo P. Castellani 2455ef81475SAngelo P. Castellani static void __exit tcp_yeah_unregister(void) 2465ef81475SAngelo P. Castellani { 2475ef81475SAngelo P. Castellani tcp_unregister_congestion_control(&tcp_yeah); 2485ef81475SAngelo P. Castellani } 2495ef81475SAngelo P. Castellani 2505ef81475SAngelo P. Castellani module_init(tcp_yeah_register); 2515ef81475SAngelo P. Castellani module_exit(tcp_yeah_unregister); 2525ef81475SAngelo P. Castellani 2535ef81475SAngelo P. Castellani MODULE_AUTHOR("Angelo P. Castellani"); 2545ef81475SAngelo P. Castellani MODULE_LICENSE("GPL"); 2555ef81475SAngelo P. Castellani MODULE_DESCRIPTION("YeAH TCP"); 256