15ef81475SAngelo P. Castellani /* 25ef81475SAngelo P. Castellani * 35ef81475SAngelo P. Castellani * YeAH TCP 45ef81475SAngelo P. Castellani * 55ef81475SAngelo P. Castellani * For further details look at: 65ef81475SAngelo P. Castellani * 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 185ef81475SAngelo P. Castellani #define TCP_YEAH_ALPHA 80 //lin number of packets queued at the bottleneck 195ef81475SAngelo P. Castellani #define TCP_YEAH_GAMMA 1 //lin fraction of queue to be removed per rtt 205ef81475SAngelo P. Castellani #define TCP_YEAH_DELTA 3 //log minimum fraction of cwnd to be removed on loss 215ef81475SAngelo P. Castellani #define TCP_YEAH_EPSILON 1 //log maximum fraction to be removed on early decongestion 225ef81475SAngelo P. Castellani #define TCP_YEAH_PHY 8 //lin maximum delta from base 235ef81475SAngelo P. Castellani #define TCP_YEAH_RHO 16 //lin minumum number of consecutive rtt to consider competition on loss 245ef81475SAngelo P. Castellani #define TCP_YEAH_ZETA 50 //lin minimum number of state switchs 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 } 595ef81475SAngelo P. Castellani 605ef81475SAngelo P. Castellani 61164891aaSStephen Hemminger static void tcp_yeah_pkts_acked(struct sock *sk, u32 pkts_acked, ktime_t last) 625ef81475SAngelo P. Castellani { 635ef81475SAngelo P. Castellani const struct inet_connection_sock *icsk = inet_csk(sk); 645ef81475SAngelo P. Castellani struct yeah *yeah = inet_csk_ca(sk); 655ef81475SAngelo P. Castellani 665ef81475SAngelo P. Castellani if (icsk->icsk_ca_state == TCP_CA_Open) 675ef81475SAngelo P. Castellani yeah->pkts_acked = pkts_acked; 68164891aaSStephen Hemminger 69164891aaSStephen Hemminger tcp_vegas_pkts_acked(sk, pkts_acked, last); 705ef81475SAngelo P. Castellani } 715ef81475SAngelo P. Castellani 725ef81475SAngelo P. Castellani static void tcp_yeah_cong_avoid(struct sock *sk, u32 ack, 735ef81475SAngelo P. Castellani u32 seq_rtt, u32 in_flight, int flag) 745ef81475SAngelo P. Castellani { 755ef81475SAngelo P. Castellani struct tcp_sock *tp = tcp_sk(sk); 765ef81475SAngelo P. Castellani struct yeah *yeah = inet_csk_ca(sk); 775ef81475SAngelo P. Castellani 785ef81475SAngelo P. Castellani if (!tcp_is_cwnd_limited(sk, in_flight)) 795ef81475SAngelo P. Castellani return; 805ef81475SAngelo P. Castellani 817752237eSStephen Hemminger if (tp->snd_cwnd <= tp->snd_ssthresh) 825ef81475SAngelo P. Castellani tcp_slow_start(tp); 837752237eSStephen Hemminger 847752237eSStephen Hemminger else if (!yeah->doing_reno_now) { 855ef81475SAngelo P. Castellani /* Scalable */ 865ef81475SAngelo P. Castellani 875ef81475SAngelo P. Castellani tp->snd_cwnd_cnt+=yeah->pkts_acked; 885ef81475SAngelo P. Castellani if (tp->snd_cwnd_cnt > min(tp->snd_cwnd, TCP_SCALABLE_AI_CNT)){ 895ef81475SAngelo P. Castellani if (tp->snd_cwnd < tp->snd_cwnd_clamp) 905ef81475SAngelo P. Castellani tp->snd_cwnd++; 915ef81475SAngelo P. Castellani tp->snd_cwnd_cnt = 0; 925ef81475SAngelo P. Castellani } 935ef81475SAngelo P. Castellani 945ef81475SAngelo P. Castellani yeah->pkts_acked = 1; 955ef81475SAngelo P. Castellani 965ef81475SAngelo P. Castellani } else { 975ef81475SAngelo P. Castellani /* Reno */ 985ef81475SAngelo P. Castellani 995ef81475SAngelo P. Castellani if (tp->snd_cwnd_cnt < tp->snd_cwnd) 1005ef81475SAngelo P. Castellani tp->snd_cwnd_cnt++; 1015ef81475SAngelo P. Castellani 1025ef81475SAngelo P. Castellani if (tp->snd_cwnd_cnt >= tp->snd_cwnd) { 1035ef81475SAngelo P. Castellani tp->snd_cwnd++; 1045ef81475SAngelo P. Castellani tp->snd_cwnd_cnt = 0; 1055ef81475SAngelo P. Castellani } 1065ef81475SAngelo P. Castellani } 1075ef81475SAngelo P. Castellani 1087752237eSStephen Hemminger /* The key players are v_vegas.beg_snd_una and v_beg_snd_nxt. 1095ef81475SAngelo P. Castellani * 1105ef81475SAngelo P. Castellani * These are so named because they represent the approximate values 1115ef81475SAngelo P. Castellani * of snd_una and snd_nxt at the beginning of the current RTT. More 1125ef81475SAngelo P. Castellani * precisely, they represent the amount of data sent during the RTT. 1135ef81475SAngelo P. Castellani * At the end of the RTT, when we receive an ACK for v_beg_snd_nxt, 1147752237eSStephen Hemminger * we will calculate that (v_beg_snd_nxt - v_vegas.beg_snd_una) outstanding 1155ef81475SAngelo P. Castellani * bytes of data have been ACKed during the course of the RTT, giving 1165ef81475SAngelo P. Castellani * an "actual" rate of: 1175ef81475SAngelo P. Castellani * 1187752237eSStephen Hemminger * (v_beg_snd_nxt - v_vegas.beg_snd_una) / (rtt duration) 1195ef81475SAngelo P. Castellani * 1207752237eSStephen Hemminger * Unfortunately, v_vegas.beg_snd_una is not exactly equal to snd_una, 1215ef81475SAngelo P. Castellani * because delayed ACKs can cover more than one segment, so they 1225ef81475SAngelo P. Castellani * don't line up yeahly with the boundaries of RTTs. 1235ef81475SAngelo P. Castellani * 1245ef81475SAngelo P. Castellani * Another unfortunate fact of life is that delayed ACKs delay the 1255ef81475SAngelo P. Castellani * advance of the left edge of our send window, so that the number 1265ef81475SAngelo P. Castellani * of bytes we send in an RTT is often less than our cwnd will allow. 1275ef81475SAngelo P. Castellani * So we keep track of our cwnd separately, in v_beg_snd_cwnd. 1285ef81475SAngelo P. Castellani */ 1295ef81475SAngelo P. Castellani 1307752237eSStephen Hemminger if (after(ack, yeah->vegas.beg_snd_nxt)) { 1315ef81475SAngelo P. Castellani 1325ef81475SAngelo P. Castellani /* We do the Vegas calculations only if we got enough RTT 1335ef81475SAngelo P. Castellani * samples that we can be reasonably sure that we got 1345ef81475SAngelo P. Castellani * at least one RTT sample that wasn't from a delayed ACK. 1355ef81475SAngelo P. Castellani * If we only had 2 samples total, 1365ef81475SAngelo P. Castellani * then that means we're getting only 1 ACK per RTT, which 1375ef81475SAngelo P. Castellani * means they're almost certainly delayed ACKs. 1385ef81475SAngelo P. Castellani * If we have 3 samples, we should be OK. 1395ef81475SAngelo P. Castellani */ 1405ef81475SAngelo P. Castellani 1417752237eSStephen Hemminger if (yeah->vegas.cntRTT > 2) { 14243e68392SStephen Hemminger u32 rtt, queue; 14343e68392SStephen Hemminger u64 bw; 1445ef81475SAngelo P. Castellani 1455ef81475SAngelo P. Castellani /* We have enough RTT samples, so, using the Vegas 1465ef81475SAngelo P. Castellani * algorithm, we determine if we should increase or 1475ef81475SAngelo P. Castellani * decrease cwnd, and by how much. 1485ef81475SAngelo P. Castellani */ 1495ef81475SAngelo P. Castellani 1505ef81475SAngelo P. Castellani /* Pluck out the RTT we are using for the Vegas 1515ef81475SAngelo P. Castellani * calculations. This is the min RTT seen during the 1525ef81475SAngelo P. Castellani * last RTT. Taking the min filters out the effects 1535ef81475SAngelo P. Castellani * of delayed ACKs, at the cost of noticing congestion 1545ef81475SAngelo P. Castellani * a bit later. 1555ef81475SAngelo P. Castellani */ 1567752237eSStephen Hemminger rtt = yeah->vegas.minRTT; 1575ef81475SAngelo P. Castellani 15843e68392SStephen Hemminger /* Compute excess number of packets above bandwidth 15943e68392SStephen Hemminger * Avoid doing full 64 bit divide. 16043e68392SStephen Hemminger */ 16143e68392SStephen Hemminger bw = tp->snd_cwnd; 1627752237eSStephen Hemminger bw *= rtt - yeah->vegas.baseRTT; 16343e68392SStephen Hemminger do_div(bw, rtt); 16443e68392SStephen Hemminger queue = bw; 1655ef81475SAngelo P. Castellani 16643e68392SStephen Hemminger if (queue > TCP_YEAH_ALPHA || 1677752237eSStephen Hemminger rtt - yeah->vegas.baseRTT > (yeah->vegas.baseRTT / TCP_YEAH_PHY)) { 16843e68392SStephen Hemminger if (queue > TCP_YEAH_ALPHA 16943e68392SStephen Hemminger && tp->snd_cwnd > yeah->reno_count) { 1705ef81475SAngelo P. Castellani u32 reduction = min(queue / TCP_YEAH_GAMMA , 1715ef81475SAngelo P. Castellani tp->snd_cwnd >> TCP_YEAH_EPSILON); 1725ef81475SAngelo P. Castellani 1735ef81475SAngelo P. Castellani tp->snd_cwnd -= reduction; 1745ef81475SAngelo P. Castellani 17543e68392SStephen Hemminger tp->snd_cwnd = max(tp->snd_cwnd, 17643e68392SStephen Hemminger yeah->reno_count); 1775ef81475SAngelo P. Castellani 1785ef81475SAngelo P. Castellani tp->snd_ssthresh = tp->snd_cwnd; 1795ef81475SAngelo P. Castellani } 1805ef81475SAngelo P. Castellani 1815ef81475SAngelo P. Castellani if (yeah->reno_count <= 2) 1825ef81475SAngelo P. Castellani yeah->reno_count = max(tp->snd_cwnd>>1, 2U); 1835ef81475SAngelo P. Castellani else 1845ef81475SAngelo P. Castellani yeah->reno_count++; 1855ef81475SAngelo P. Castellani 18643e68392SStephen Hemminger yeah->doing_reno_now = min(yeah->doing_reno_now + 1, 18743e68392SStephen Hemminger 0xffffffU); 1885ef81475SAngelo P. Castellani } else { 1895ef81475SAngelo P. Castellani yeah->fast_count++; 1905ef81475SAngelo P. Castellani 1915ef81475SAngelo P. Castellani if (yeah->fast_count > TCP_YEAH_ZETA) { 1925ef81475SAngelo P. Castellani yeah->reno_count = 2; 1935ef81475SAngelo P. Castellani yeah->fast_count = 0; 1945ef81475SAngelo P. Castellani } 1955ef81475SAngelo P. Castellani 1965ef81475SAngelo P. Castellani yeah->doing_reno_now = 0; 1975ef81475SAngelo P. Castellani } 1985ef81475SAngelo P. Castellani 1995ef81475SAngelo P. Castellani yeah->lastQ = queue; 2005ef81475SAngelo P. Castellani 2015ef81475SAngelo P. Castellani } 2025ef81475SAngelo P. Castellani 2035ef81475SAngelo P. Castellani /* Save the extent of the current window so we can use this 2045ef81475SAngelo P. Castellani * at the end of the next RTT. 2055ef81475SAngelo P. Castellani */ 2067752237eSStephen Hemminger yeah->vegas.beg_snd_una = yeah->vegas.beg_snd_nxt; 2077752237eSStephen Hemminger yeah->vegas.beg_snd_nxt = tp->snd_nxt; 2087752237eSStephen Hemminger yeah->vegas.beg_snd_cwnd = tp->snd_cwnd; 2095ef81475SAngelo P. Castellani 2105ef81475SAngelo P. Castellani /* Wipe the slate clean for the next RTT. */ 2117752237eSStephen Hemminger yeah->vegas.cntRTT = 0; 2127752237eSStephen Hemminger yeah->vegas.minRTT = 0x7fffffff; 2135ef81475SAngelo P. Castellani } 2145ef81475SAngelo P. Castellani } 2155ef81475SAngelo P. Castellani 2165ef81475SAngelo P. Castellani static u32 tcp_yeah_ssthresh(struct sock *sk) { 2175ef81475SAngelo P. Castellani const struct tcp_sock *tp = tcp_sk(sk); 2185ef81475SAngelo P. Castellani struct yeah *yeah = inet_csk_ca(sk); 2195ef81475SAngelo P. Castellani u32 reduction; 2205ef81475SAngelo P. Castellani 2215ef81475SAngelo P. Castellani if (yeah->doing_reno_now < TCP_YEAH_RHO) { 2225ef81475SAngelo P. Castellani reduction = yeah->lastQ; 2235ef81475SAngelo P. Castellani 2245ef81475SAngelo P. Castellani reduction = min( reduction, max(tp->snd_cwnd>>1, 2U) ); 2255ef81475SAngelo P. Castellani 2265ef81475SAngelo P. Castellani reduction = max( reduction, tp->snd_cwnd >> TCP_YEAH_DELTA); 2275ef81475SAngelo P. Castellani } else 2285ef81475SAngelo P. Castellani reduction = max(tp->snd_cwnd>>1,2U); 2295ef81475SAngelo P. Castellani 2305ef81475SAngelo P. Castellani yeah->fast_count = 0; 2315ef81475SAngelo P. Castellani yeah->reno_count = max(yeah->reno_count>>1, 2U); 2325ef81475SAngelo P. Castellani 2335ef81475SAngelo P. Castellani return tp->snd_cwnd - reduction; 2345ef81475SAngelo P. Castellani } 2355ef81475SAngelo P. Castellani 2365ef81475SAngelo P. Castellani static struct tcp_congestion_ops tcp_yeah = { 237164891aaSStephen Hemminger .flags = TCP_CONG_RTT_STAMP, 2385ef81475SAngelo P. Castellani .init = tcp_yeah_init, 2395ef81475SAngelo P. Castellani .ssthresh = tcp_yeah_ssthresh, 2405ef81475SAngelo P. Castellani .cong_avoid = tcp_yeah_cong_avoid, 2415ef81475SAngelo P. Castellani .min_cwnd = tcp_reno_min_cwnd, 2425ef81475SAngelo P. Castellani .set_state = tcp_vegas_state, 2435ef81475SAngelo P. Castellani .cwnd_event = tcp_vegas_cwnd_event, 2445ef81475SAngelo P. Castellani .get_info = tcp_vegas_get_info, 2455ef81475SAngelo P. Castellani .pkts_acked = tcp_yeah_pkts_acked, 2465ef81475SAngelo P. Castellani 2475ef81475SAngelo P. Castellani .owner = THIS_MODULE, 2485ef81475SAngelo P. Castellani .name = "yeah", 2495ef81475SAngelo P. Castellani }; 2505ef81475SAngelo P. Castellani 2515ef81475SAngelo P. Castellani static int __init tcp_yeah_register(void) 2525ef81475SAngelo P. Castellani { 2535ef81475SAngelo P. Castellani BUG_ON(sizeof(struct yeah) > ICSK_CA_PRIV_SIZE); 2545ef81475SAngelo P. Castellani tcp_register_congestion_control(&tcp_yeah); 2555ef81475SAngelo P. Castellani return 0; 2565ef81475SAngelo P. Castellani } 2575ef81475SAngelo P. Castellani 2585ef81475SAngelo P. Castellani static void __exit tcp_yeah_unregister(void) 2595ef81475SAngelo P. Castellani { 2605ef81475SAngelo P. Castellani tcp_unregister_congestion_control(&tcp_yeah); 2615ef81475SAngelo P. Castellani } 2625ef81475SAngelo P. Castellani 2635ef81475SAngelo P. Castellani module_init(tcp_yeah_register); 2645ef81475SAngelo P. Castellani module_exit(tcp_yeah_unregister); 2655ef81475SAngelo P. Castellani 2665ef81475SAngelo P. Castellani MODULE_AUTHOR("Angelo P. Castellani"); 2675ef81475SAngelo P. Castellani MODULE_LICENSE("GPL"); 2685ef81475SAngelo P. Castellani MODULE_DESCRIPTION("YeAH TCP"); 269