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 6130cfd0baSStephen Hemminger static void tcp_yeah_pkts_acked(struct sock *sk, u32 pkts_acked, s32 rtt_us) 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 6930cfd0baSStephen Hemminger tcp_vegas_pkts_acked(sk, pkts_acked, rtt_us); 705ef81475SAngelo P. Castellani } 715ef81475SAngelo P. Castellani 72c3a05c60SIlpo Järvinen static void tcp_yeah_cong_avoid(struct sock *sk, u32 ack, u32 in_flight) 735ef81475SAngelo P. Castellani { 745ef81475SAngelo P. Castellani struct tcp_sock *tp = tcp_sk(sk); 755ef81475SAngelo P. Castellani struct yeah *yeah = inet_csk_ca(sk); 765ef81475SAngelo P. Castellani 775ef81475SAngelo P. Castellani if (!tcp_is_cwnd_limited(sk, in_flight)) 785ef81475SAngelo P. Castellani return; 795ef81475SAngelo P. Castellani 807752237eSStephen Hemminger if (tp->snd_cwnd <= tp->snd_ssthresh) 815ef81475SAngelo P. Castellani tcp_slow_start(tp); 827752237eSStephen Hemminger 837752237eSStephen Hemminger else if (!yeah->doing_reno_now) { 845ef81475SAngelo P. Castellani /* Scalable */ 855ef81475SAngelo P. Castellani 865ef81475SAngelo P. Castellani tp->snd_cwnd_cnt += yeah->pkts_acked; 875ef81475SAngelo P. Castellani if (tp->snd_cwnd_cnt > min(tp->snd_cwnd, TCP_SCALABLE_AI_CNT)){ 885ef81475SAngelo P. Castellani if (tp->snd_cwnd < tp->snd_cwnd_clamp) 895ef81475SAngelo P. Castellani tp->snd_cwnd++; 905ef81475SAngelo P. Castellani tp->snd_cwnd_cnt = 0; 915ef81475SAngelo P. Castellani } 925ef81475SAngelo P. Castellani 935ef81475SAngelo P. Castellani yeah->pkts_acked = 1; 945ef81475SAngelo P. Castellani 955ef81475SAngelo P. Castellani } else { 965ef81475SAngelo P. Castellani /* Reno */ 97758ce5c8SIlpo Järvinen tcp_cong_avoid_ai(tp, tp->snd_cwnd); 985ef81475SAngelo P. Castellani } 995ef81475SAngelo P. Castellani 1007752237eSStephen Hemminger /* The key players are v_vegas.beg_snd_una and v_beg_snd_nxt. 1015ef81475SAngelo P. Castellani * 1025ef81475SAngelo P. Castellani * These are so named because they represent the approximate values 1035ef81475SAngelo P. Castellani * of snd_una and snd_nxt at the beginning of the current RTT. More 1045ef81475SAngelo P. Castellani * precisely, they represent the amount of data sent during the RTT. 1055ef81475SAngelo P. Castellani * At the end of the RTT, when we receive an ACK for v_beg_snd_nxt, 1067752237eSStephen Hemminger * we will calculate that (v_beg_snd_nxt - v_vegas.beg_snd_una) outstanding 1075ef81475SAngelo P. Castellani * bytes of data have been ACKed during the course of the RTT, giving 1085ef81475SAngelo P. Castellani * an "actual" rate of: 1095ef81475SAngelo P. Castellani * 1107752237eSStephen Hemminger * (v_beg_snd_nxt - v_vegas.beg_snd_una) / (rtt duration) 1115ef81475SAngelo P. Castellani * 1127752237eSStephen Hemminger * Unfortunately, v_vegas.beg_snd_una is not exactly equal to snd_una, 1135ef81475SAngelo P. Castellani * because delayed ACKs can cover more than one segment, so they 1145ef81475SAngelo P. Castellani * don't line up yeahly with the boundaries of RTTs. 1155ef81475SAngelo P. Castellani * 1165ef81475SAngelo P. Castellani * Another unfortunate fact of life is that delayed ACKs delay the 1175ef81475SAngelo P. Castellani * advance of the left edge of our send window, so that the number 1185ef81475SAngelo P. Castellani * of bytes we send in an RTT is often less than our cwnd will allow. 1195ef81475SAngelo P. Castellani * So we keep track of our cwnd separately, in v_beg_snd_cwnd. 1205ef81475SAngelo P. Castellani */ 1215ef81475SAngelo P. Castellani 1227752237eSStephen Hemminger if (after(ack, yeah->vegas.beg_snd_nxt)) { 1235ef81475SAngelo P. Castellani 1245ef81475SAngelo P. Castellani /* We do the Vegas calculations only if we got enough RTT 1255ef81475SAngelo P. Castellani * samples that we can be reasonably sure that we got 1265ef81475SAngelo P. Castellani * at least one RTT sample that wasn't from a delayed ACK. 1275ef81475SAngelo P. Castellani * If we only had 2 samples total, 1285ef81475SAngelo P. Castellani * then that means we're getting only 1 ACK per RTT, which 1295ef81475SAngelo P. Castellani * means they're almost certainly delayed ACKs. 1305ef81475SAngelo P. Castellani * If we have 3 samples, we should be OK. 1315ef81475SAngelo P. Castellani */ 1325ef81475SAngelo P. Castellani 1337752237eSStephen Hemminger if (yeah->vegas.cntRTT > 2) { 13443e68392SStephen Hemminger u32 rtt, queue; 13543e68392SStephen Hemminger u64 bw; 1365ef81475SAngelo P. Castellani 1375ef81475SAngelo P. Castellani /* We have enough RTT samples, so, using the Vegas 1385ef81475SAngelo P. Castellani * algorithm, we determine if we should increase or 1395ef81475SAngelo P. Castellani * decrease cwnd, and by how much. 1405ef81475SAngelo P. Castellani */ 1415ef81475SAngelo P. Castellani 1425ef81475SAngelo P. Castellani /* Pluck out the RTT we are using for the Vegas 1435ef81475SAngelo P. Castellani * calculations. This is the min RTT seen during the 1445ef81475SAngelo P. Castellani * last RTT. Taking the min filters out the effects 1455ef81475SAngelo P. Castellani * of delayed ACKs, at the cost of noticing congestion 1465ef81475SAngelo P. Castellani * a bit later. 1475ef81475SAngelo P. Castellani */ 1487752237eSStephen Hemminger rtt = yeah->vegas.minRTT; 1495ef81475SAngelo P. Castellani 15043e68392SStephen Hemminger /* Compute excess number of packets above bandwidth 15143e68392SStephen Hemminger * Avoid doing full 64 bit divide. 15243e68392SStephen Hemminger */ 15343e68392SStephen Hemminger bw = tp->snd_cwnd; 1547752237eSStephen Hemminger bw *= rtt - yeah->vegas.baseRTT; 15543e68392SStephen Hemminger do_div(bw, rtt); 15643e68392SStephen Hemminger queue = bw; 1575ef81475SAngelo P. Castellani 15843e68392SStephen Hemminger if (queue > TCP_YEAH_ALPHA || 1597752237eSStephen Hemminger rtt - yeah->vegas.baseRTT > (yeah->vegas.baseRTT / TCP_YEAH_PHY)) { 1609d4fb27dSJoe Perches if (queue > TCP_YEAH_ALPHA && 1619d4fb27dSJoe Perches tp->snd_cwnd > yeah->reno_count) { 1625ef81475SAngelo P. Castellani u32 reduction = min(queue / TCP_YEAH_GAMMA , 1635ef81475SAngelo P. Castellani tp->snd_cwnd >> TCP_YEAH_EPSILON); 1645ef81475SAngelo P. Castellani 1655ef81475SAngelo P. Castellani tp->snd_cwnd -= reduction; 1665ef81475SAngelo P. Castellani 16743e68392SStephen Hemminger tp->snd_cwnd = max(tp->snd_cwnd, 16843e68392SStephen Hemminger yeah->reno_count); 1695ef81475SAngelo P. Castellani 1705ef81475SAngelo P. Castellani tp->snd_ssthresh = tp->snd_cwnd; 1715ef81475SAngelo P. Castellani } 1725ef81475SAngelo P. Castellani 1735ef81475SAngelo P. Castellani if (yeah->reno_count <= 2) 1745ef81475SAngelo P. Castellani yeah->reno_count = max(tp->snd_cwnd>>1, 2U); 1755ef81475SAngelo P. Castellani else 1765ef81475SAngelo P. Castellani yeah->reno_count++; 1775ef81475SAngelo P. Castellani 17843e68392SStephen Hemminger yeah->doing_reno_now = min(yeah->doing_reno_now + 1, 17943e68392SStephen Hemminger 0xffffffU); 1805ef81475SAngelo P. Castellani } else { 1815ef81475SAngelo P. Castellani yeah->fast_count++; 1825ef81475SAngelo P. Castellani 1835ef81475SAngelo P. Castellani if (yeah->fast_count > TCP_YEAH_ZETA) { 1845ef81475SAngelo P. Castellani yeah->reno_count = 2; 1855ef81475SAngelo P. Castellani yeah->fast_count = 0; 1865ef81475SAngelo P. Castellani } 1875ef81475SAngelo P. Castellani 1885ef81475SAngelo P. Castellani yeah->doing_reno_now = 0; 1895ef81475SAngelo P. Castellani } 1905ef81475SAngelo P. Castellani 1915ef81475SAngelo P. Castellani yeah->lastQ = queue; 1925ef81475SAngelo P. Castellani 1935ef81475SAngelo P. Castellani } 1945ef81475SAngelo P. Castellani 1955ef81475SAngelo P. Castellani /* Save the extent of the current window so we can use this 1965ef81475SAngelo P. Castellani * at the end of the next RTT. 1975ef81475SAngelo P. Castellani */ 1987752237eSStephen Hemminger yeah->vegas.beg_snd_una = yeah->vegas.beg_snd_nxt; 1997752237eSStephen Hemminger yeah->vegas.beg_snd_nxt = tp->snd_nxt; 2007752237eSStephen Hemminger yeah->vegas.beg_snd_cwnd = tp->snd_cwnd; 2015ef81475SAngelo P. Castellani 2025ef81475SAngelo P. Castellani /* Wipe the slate clean for the next RTT. */ 2037752237eSStephen Hemminger yeah->vegas.cntRTT = 0; 2047752237eSStephen Hemminger yeah->vegas.minRTT = 0x7fffffff; 2055ef81475SAngelo P. Castellani } 2065ef81475SAngelo P. Castellani } 2075ef81475SAngelo P. Castellani 2085ef81475SAngelo P. Castellani static u32 tcp_yeah_ssthresh(struct sock *sk) { 2095ef81475SAngelo P. Castellani const struct tcp_sock *tp = tcp_sk(sk); 2105ef81475SAngelo P. Castellani struct yeah *yeah = inet_csk_ca(sk); 2115ef81475SAngelo P. Castellani u32 reduction; 2125ef81475SAngelo P. Castellani 2135ef81475SAngelo P. Castellani if (yeah->doing_reno_now < TCP_YEAH_RHO) { 2145ef81475SAngelo P. Castellani reduction = yeah->lastQ; 2155ef81475SAngelo P. Castellani 2165ef81475SAngelo P. Castellani reduction = min( reduction, max(tp->snd_cwnd>>1, 2U) ); 2175ef81475SAngelo P. Castellani 2185ef81475SAngelo P. Castellani reduction = max( reduction, tp->snd_cwnd >> TCP_YEAH_DELTA); 2195ef81475SAngelo P. Castellani } else 2205ef81475SAngelo P. Castellani reduction = max(tp->snd_cwnd>>1, 2U); 2215ef81475SAngelo P. Castellani 2225ef81475SAngelo P. Castellani yeah->fast_count = 0; 2235ef81475SAngelo P. Castellani yeah->reno_count = max(yeah->reno_count>>1, 2U); 2245ef81475SAngelo P. Castellani 2255ef81475SAngelo P. Castellani return tp->snd_cwnd - reduction; 2265ef81475SAngelo P. Castellani } 2275ef81475SAngelo P. Castellani 228*a252bebeSStephen Hemminger static struct tcp_congestion_ops tcp_yeah __read_mostly = { 229164891aaSStephen Hemminger .flags = TCP_CONG_RTT_STAMP, 2305ef81475SAngelo P. Castellani .init = tcp_yeah_init, 2315ef81475SAngelo P. Castellani .ssthresh = tcp_yeah_ssthresh, 2325ef81475SAngelo P. Castellani .cong_avoid = tcp_yeah_cong_avoid, 2335ef81475SAngelo P. Castellani .min_cwnd = tcp_reno_min_cwnd, 2345ef81475SAngelo P. Castellani .set_state = tcp_vegas_state, 2355ef81475SAngelo P. Castellani .cwnd_event = tcp_vegas_cwnd_event, 2365ef81475SAngelo P. Castellani .get_info = tcp_vegas_get_info, 2375ef81475SAngelo P. Castellani .pkts_acked = tcp_yeah_pkts_acked, 2385ef81475SAngelo P. Castellani 2395ef81475SAngelo P. Castellani .owner = THIS_MODULE, 2405ef81475SAngelo P. Castellani .name = "yeah", 2415ef81475SAngelo P. Castellani }; 2425ef81475SAngelo P. Castellani 2435ef81475SAngelo P. Castellani static int __init tcp_yeah_register(void) 2445ef81475SAngelo P. Castellani { 2455ef81475SAngelo P. Castellani BUG_ON(sizeof(struct yeah) > ICSK_CA_PRIV_SIZE); 2465ef81475SAngelo P. Castellani tcp_register_congestion_control(&tcp_yeah); 2475ef81475SAngelo P. Castellani return 0; 2485ef81475SAngelo P. Castellani } 2495ef81475SAngelo P. Castellani 2505ef81475SAngelo P. Castellani static void __exit tcp_yeah_unregister(void) 2515ef81475SAngelo P. Castellani { 2525ef81475SAngelo P. Castellani tcp_unregister_congestion_control(&tcp_yeah); 2535ef81475SAngelo P. Castellani } 2545ef81475SAngelo P. Castellani 2555ef81475SAngelo P. Castellani module_init(tcp_yeah_register); 2565ef81475SAngelo P. Castellani module_exit(tcp_yeah_unregister); 2575ef81475SAngelo P. Castellani 2585ef81475SAngelo P. Castellani MODULE_AUTHOR("Angelo P. Castellani"); 2595ef81475SAngelo P. Castellani MODULE_LICENSE("GPL"); 2605ef81475SAngelo P. Castellani MODULE_DESCRIPTION("YeAH TCP"); 261